title: PairMotif+: a fast and effective algorithm for de novo motif discovery in DNA sequences.
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.
authors.affiliation: School of Computer Science and Technology, Xidian University, Xi'an 710071, China.
authors.forename: Qiang
authors.initials: Q
authors.lastname: Yu
authors.forename: Hongwei
authors.initials: H
authors.lastname: Huo
authors.forename: Yipu
authors.initials: Y
authors.lastname: Zhang
authors.forename: Hongzhi
authors.initials: H
authors.lastname: Guo
authors.forename: Haitao
authors.initials: H
authors.lastname: Guo
mesh_terms: D000465:Algorithms; D001483:Base Sequence / Q000235:genetics; D019295:Computational Biology / Q000379:methods*
keywords: Motif search; Pattern-driven algorithms.; Transcription factor binding sites