PairMotif: A New Pattern-driven Algorithm for Planted (l, D) DNA Motif Search

Overview

Journal PLoS One

Specialties General Medicine
Science

Date 2012 Nov 3

PMID 23119020

Citations 14

Authors

Qiang Yu

Hongwei Huo

Yipu Zhang

Hongzhi Guo

Affiliations

Soon will be listed here.

Abstract

Motif search is a fundamental problem in bioinformatics with an important application in locating transcription factor binding sites (TFBSs) in DNA sequences. The exact algorithms can report all (l, d) motifs and find the best one under a specific objective function. However, it is still a challenging task to identify weak motifs, since either a large amount of memory or execution time is required by current exact algorithms. A new exact algorithm, PairMotif, is proposed for planted (l, d) motif search (PMS) in this paper. To effectively reduce both candidate motifs and scanned l-mers, multiple pairs of l-mers with relatively large distances are selected from input sequences to restrict the search space. Comparisons with several recently proposed algorithms show that PairMotif requires less storage space and runs faster on most PMS instances. Particularly, among the algorithms compared, only PairMotif can solve the weak instance (27, 9) within 10 hours. Moreover, the performance of PairMotif is stable over the sequence length, which allows it to identify motifs in longer sequences. For the real biological data, experimental results demonstrate the validity of the proposed algorithm.

Citing Articles

A Review on Planted (, d) Motif Discovery Algorithms for Medical Diagnose.

Mohanty S, Pattnaik P, Al-Absi A, Kang D Sensors (Basel). 2022; 22(3).

PMID: 35161949 PMC: 8838483. DOI: 10.3390/s22031204.

A Clustering Approach for Motif Discovery in ChIP-Seq Dataset.

Sun C, Yang Y, Wang H, Wang W Entropy (Basel). 2020; 21(8).

PMID: 33267515 PMC: 7515331. DOI: 10.3390/e21080802.

Novel algorithms for LDD motif search.

Xiao P, Schiller M, Rajasekaran S BMC Genomics. 2019; 20(Suppl 5):424.

PMID: 31167665 PMC: 6551235. DOI: 10.1186/s12864-019-5701-6.

Review of Different Sequence Motif Finding Algorithms.

Hashim F, Mabrouk M, Al-Atabany W Avicenna J Med Biotechnol. 2019; 11(2):130-148.

PMID: 31057715 PMC: 6490410.

SamSelect: a sample sequence selection algorithm for quorum planted motif search on large DNA datasets.

Yu Q, Wei D, Huo H BMC Bioinformatics. 2018; 19(1):228.

PMID: 29914360 PMC: 6006848. DOI: 10.1186/s12859-018-2242-y.

References

Fratkin E, Naughton B, Brutlag D, Batzoglou S . MotifCut: regulatory motifs finding with maximum density subgraphs. Bioinformatics. 2006; 22(14):e150-7. DOI: 10.1093/bioinformatics/btl243. View

Li N, Tompa M . Analysis of computational approaches for motif discovery. Algorithms Mol Biol. 2006; 1:8. PMC: 1540429. DOI: 10.1186/1748-7188-1-8. View

Bi C . A Monte Carlo EM algorithm for de novo motif discovery in biomolecular sequences. IEEE/ACM Trans Comput Biol Bioinform. 2009; 6(3):370-86. DOI: 10.1109/TCBB.2008.103. View

Eskin E, Pevzner P . Finding composite regulatory patterns in DNA sequences. Bioinformatics. 2002; 18 Suppl 1:S354-63. DOI: 10.1093/bioinformatics/18.suppl_1.s354. View

Dinh H, Rajasekaran S, Kundeti V . PMS5: an efficient exact algorithm for the (ℓ, d)-motif finding problem. BMC Bioinformatics. 2011; 12:410. PMC: 3269969. DOI: 10.1186/1471-2105-12-410. View

Buhler J, Tompa M . Finding motifs using random projections. J Comput Biol. 2002; 9(2):225-42. DOI: 10.1089/10665270252935430. View

Marsan L, Sagot M . Algorithms for extracting structured motifs using a suffix tree with an application to promoter and regulatory site consensus identification. J Comput Biol. 2000; 7(3-4):345-62. DOI: 10.1089/106652700750050826. View

Das M, Dai H . A survey of DNA motif finding algorithms. BMC Bioinformatics. 2007; 8 Suppl 7:S21. PMC: 2099490. DOI: 10.1186/1471-2105-8-S7-S21. View

Ho E, Jakubowski C, Gunderson S . iTriplet, a rule-based nucleic acid sequence motif finder. Algorithms Mol Biol. 2009; 4:14. PMC: 2784457. DOI: 10.1186/1748-7188-4-14. View

10.

Miller A, Print C, Nielsen P, Crampin E . A Bayesian search for transcriptional motifs. PLoS One. 2010; 5(11):e13897. PMC: 2987817. DOI: 10.1371/journal.pone.0013897. View

11.

Huang C, Lee W, Hsieh S . An improved heuristic algorithm for finding motif signals in DNA sequences. IEEE/ACM Trans Comput Biol Bioinform. 2010; 8(4):959-75. DOI: 10.1109/TCBB.2010.92. View

12.

Davila J, Balla S, Rajasekaran S . Fast and practical algorithms for planted (l, d) motif search. IEEE/ACM Trans Comput Biol Bioinform. 2007; 4(4):544-52. DOI: 10.1109/TCBB.2007.70241. View

13.

Liu X, Brutlag D, Liu J . BioProspector: discovering conserved DNA motifs in upstream regulatory regions of co-expressed genes. Pac Symp Biocomput. 2001; :127-38. View

14.

Bulyk M, Johnson P, Church G . Nucleotides of transcription factor binding sites exert interdependent effects on the binding affinities of transcription factors. Nucleic Acids Res. 2002; 30(5):1255-61. PMC: 101241. DOI: 10.1093/nar/30.5.1255. View

15.

Rajasekaran S, Dinh H . A speedup technique for (l, d)-motif finding algorithms. BMC Res Notes. 2011; 4:54. PMC: 3063805. DOI: 10.1186/1756-0500-4-54. View

16.

Pavesi G, Mauri G, Pesole G . An algorithm for finding signals of unknown length in DNA sequences. Bioinformatics. 2001; 17 Suppl 1:S207-14. DOI: 10.1093/bioinformatics/17.suppl_1.s207. View

17.

Bailey T, Elkan C . Fitting a mixture model by expectation maximization to discover motifs in biopolymers. Proc Int Conf Intell Syst Mol Biol. 1994; 2:28-36. View

18.

Tompa M, Li N, Bailey T, Church G, De Moor B, Eskin E . Assessing computational tools for the discovery of transcription factor binding sites. Nat Biotechnol. 2005; 23(1):137-44. DOI: 10.1038/nbt1053. View

19.

Lawrence C, Altschul S, Boguski M, Liu J, Neuwald A, Wootton J . Detecting subtle sequence signals: a Gibbs sampling strategy for multiple alignment. Science. 1993; 262(5131):208-14. DOI: 10.1126/science.8211139. View

20.

Pevzner P, Sze S . Combinatorial approaches to finding subtle signals in DNA sequences. Proc Int Conf Intell Syst Mol Biol. 2000; 8:269-78. View