A sequential Monte Carlo EM approach to the transcription factor binding site identification problem.
BACKGROUND
A significant and stubbornly intractable problem in genome sequence analysis has been the de novo identification of transcription factor binding sites in promoter regions. Although theoretically pleasing, probabilistic methods have faced difficulties due to model mismatch and the nature of the biological sequence. These problems result in inference in a high dimensional, highly multimodal space, and consequently often display only local convergence and hence unsatisfactory performance.
In this article, we derive and demonstrate a novel method utilizing a sequential Monte Carlo-based expectation-maximization (EM) optimization to improve performance in this scenario. The Monte Carlo element should increase the robustness of the algorithm compared to classical EM. Furthermore, the parallel nature of the sequential Monte Carlo algorithm should be more robust than Gibbs sampling approaches to multimodality problems.


RESULTS
We demonstrate the superior performance of this algorithm on both semi-synthetic and real data from Escherichia coli.


BACKGROUND
http://sigproc-eng.cam.ac.uk/ approximately ej230/smc_em_tfbsid.tar.gz
Jackson
Edmund S
ES
Signal Processing Laboratory, Department of Engineering, Cambridge University, UK. ej230@cam.ac.uk
Fitzgerald
William J
WJ
D000465:Algorithms; D001483:Base Sequence; D001665:Binding Sites; D016013:Likelihood Functions; D008957:Models, Genetic; D015233:Models, Statistical; D008969:Molecular Sequence Data; D009010:Monte Carlo Method; D010363:Pattern Recognition, Automated / Q000379:methods; D011485:Protein Binding; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D014157:Transcription Factors / Q000737:chemistry* / Q000235:genetics*
D014157:Transcription Factors