Abstract | ||
---|---|---|
The Expectation Maximization (EM) motif-finding algorithm is one of the most popular de novo motif discovery methods. However, the EM algorithm largely depends on its initialization and can be easily trapped in local optima. This paper implements a Monte Carlo version of the EM algorithm that performs multiple sequence local alignment to overcome the drawbacks inherent in conventional EM motif-finding algorithms. The newly implemented algorithm is named as Monte Carlo EM Motif Discovery Algorithm (MCEMDA). MCEMDA starts from an initial model, and then it iteratively performs Monte Carlo simulation and parameter update steps until convergence. MCEMDA is compared with other popular motif-finding algorithms using simulated, prokaryotic and eukaryotic motif sequences. Results show that MCEMDA outperforms other algorithms. MCEMDA successfully discovers a helix-turnhelix motif in protein sequences as well. It provides a general framework for motif-finding algorithm development. A website of this program will be available at http://motif.cmh.edu. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1007/978-3-540-72031-7_42 | ISBRA |
Keywords | Field | DocType |
monte carlo simulation,multiple sequence,motif discovery method,algorithm development,popular motif-finding algorithm,conventional em motif-finding algorithm,motif-finding algorithm,monte carlo em motif,em algorithm,local alignment,helix-turnhelix motif,eukaryotic motif sequence,monte carlo,transcriptional regulation,helix turn helix,protein sequence,expectation maximization | Markov chain Monte Carlo,Computer science,Artificial intelligence,Monte Carlo method,Expectation–maximization algorithm,Local optimum,Hybrid Monte Carlo,Algorithm,Quasi-Monte Carlo method,Smith–Waterman algorithm,Bioinformatics,Initialization,Machine learning | Conference |
Volume | ISSN | Citations |
4463 | 0302-9743 | 2 |
PageRank | References | Authors |
0.39 | 10 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Chengpeng Bi | 1 | 131 | 11.29 |