Name
Abstract | ||
|---|---|---|
Motif discovery methods play pivotal roles in deciphering the genetic regulatory codes (i.e., motifs) in genomes as well as in locating conserved domains in protein sequences. The Expectation Maximization (EM) algorithm is one of the most popular methods used in de novo motif discovery. Based on the position weight matrix (PWM) updating technique, this paper presents a Monte Carlo version of the EM motif-finding algorithm that carries out stochastic sampling in local alignment space to overcome the conventional EM's main drawback of being trapped in a local optimum. 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 until convergence. A log-likelihood profiling technique together with the top-k strategy is introduced to cope with the phase shifts and multiple modal issues in motif discovery problem. A novel grouping motif alignment (GMA) algorithm is designed to select motifs by clustering a population of candidate local alignments and successfully applied to subtle motif discovery. MCEMDA compares favorably to other popular PWM-based and word enumerative motif algorithms tested using simulated (l, d)-motif cases, documented prokaryotic, and eukaryotic DNA motif sequences. Finally, MCEMDA is applied to detect large blocks of conserved domains using protein benchmarks and exhibits its excellent capacity while compared with other multiple sequence alignment methods. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/TCBB.2008.103 | IEEE/ACM Trans. Comput. Biology Bioinform. |
Keywords | Field | DocType |
bioinformatics,expectation maximization,position weight matrix,pulse width modulation,stochastic processes,proteins,molecular biophysics,clustering algorithms,em algorithm,transcription regulation,statistical computing,phase shift,local alignment,sequences,monte carlo methods,genomics,monte carlo simulation,multiple sequence alignment,protein sequence,genetics,transcriptional regulation,monte carlo | Population,Eukaryotic Linear Motif resource,Computer science,Position weight matrix,Artificial intelligence,Cluster analysis,Multiple sequence alignment,Monte Carlo method,Local optimum,Algorithm,Smith–Waterman algorithm,Bioinformatics,Machine learning | Journal |
Volume | Issue | ISSN |
6 | 3 | 1545-5963 |
Citations | PageRank | References |
8 | 0.54 | 24 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chengpeng Bi | 1 | 131 | 11.29 |