ISSN: 1449-2288International Journal of Biological Sciences
Global reach, higher impact
Int J Biol Sci 2013; 9(4):412-424. doi:10.7150/ijbs.5786 This issue Cite
Research Paper
PairMotif+: A Fast and Effective Algorithm for De Novo Motif Discovery in DNA sequences
School of Computer Science and Technology, Xidian University, Xi'an, 710071, China.
Abstract
The planted (l, d) motif search is one of the most widely studied problems in bioinformatics, which plays an important role in the identification of transcription factor binding sites in DNA sequences. However, it is still a challenging task to identify highly degenerate motifs, since current algorithms either output the exact results with a high computational cost or accomplish the computation in a short time but very often fall into a local optimum. In order to make a better trade-off between accuracy and efficiency, we propose a new pattern-driven algorithm, named PairMotif+. At first, some pairs of l-mers are extracted from input sequences according to probabilistic analysis and statistical method so that one or more pairs of motif instances are included in them. Then an approximate strategy for refining pairs of l-mers with high accuracy is adopted in order to avoid the verification of most candidate motifs. Experimental results on the simulated data show that PairMotif+ can solve various (l, d) problems within an hour on a PC with 2.67 GHz processor, and has a better identification accuracy than the compared algorithms MEME, AlignACE and VINE. Also, the validity of the proposed algorithm is tested on multiple real data sets.
Keywords: Motif search, Transcription factor binding sites, Pattern-driven algorithms.
Citation styles
