RecMotif: a Novel Fast Algorithm for Weak Motif Discovery

Overview

Journal BMC Bioinformatics

Publisher Biomed Central

Specialty Biology

Date 2010 Dec 22

PMID 21172058

Citations 8

Authors

He Quan Sun

Malcolm Yoke Hean Low

Wen Jing Hsu

Jagath C Rajapakse

Affiliations

Soon will be listed here.

Abstract

Background: Weak motif discovery in DNA sequences is an important but unresolved problem in computational biology. Previous algorithms that aimed to solve the problem usually require a large amount of memory or execution time. In this paper, we proposed a fast and memory efficient algorithm, RecMotif, which guarantees to discover all motifs with specific (l, d) settings (where l is the motif length and d is the maximum number of mutations between a motif instance and the true motif).

Results: Comparisons with several recently proposed algorithms have shown that RecMotif is more scalable for handling longer and weaker motifs. For instance, it can solve the open challenge cases such as (40, 14) within 5 hours while the other algorithms compared failed due to either longer execution times or shortage of memory space. For real biological sequences, such as E.coli CRP, RecMotif is able to accurately discover the motif instances with (l, d) as (18, 6) in less than 1 second, which is faster than the other algorithms compared.

Conclusions: RecMotif is a novel algorithm that requires only a space complexity of O(m²n) (where m is the number of sequences in the data and n is the length of the sequences).

Citing Articles

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.

RefSelect: a reference sequence selection algorithm for planted (l, d) motif search.

Yu Q, Huo H, Zhao R, Feng D, Vitter J, Huan J BMC Bioinformatics. 2016; 17 Suppl 9:266.

PMID: 27454113 PMC: 4959363. DOI: 10.1186/s12859-016-1130-6.

Extracting DNA words based on the sequence features: non-uniform distribution and integrity.

Li Z, Cao H, Cui Y, Zhang Y Theor Biol Med Model. 2016; 13:2.

PMID: 26811154 PMC: 4727310. DOI: 10.1186/s12976-016-0028-3.

A new exhaustive method and strategy for finding motifs in ChIP-enriched regions.

Jia C, Carson M, Wang Y, Lin Y, Lu H PLoS One. 2014; 9(1):e86044.

PMID: 24475069 PMC: 3901781. DOI: 10.1371/journal.pone.0086044.

References

Wang G, Yu T, Zhang W . WordSpy: identifying transcription factor binding motifs by building a dictionary and learning a grammar. Nucleic Acids Res. 2005; 33(Web Server issue):W412-6. PMC: 1160252. DOI: 10.1093/nar/gki492. View

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

Stormo G, Hartzell 3rd G . Identifying protein-binding sites from unaligned DNA fragments. Proc Natl Acad Sci U S A. 1989; 86(4):1183-7. PMC: 286650. DOI: 10.1073/pnas.86.4.1183. View

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

Wijaya E, Yiu S, Son N, Kanagasabai R, Sung W . MotifVoter: a novel ensemble method for fine-grained integration of generic motif finders. Bioinformatics. 2008; 24(20):2288-95. DOI: 10.1093/bioinformatics/btn420. View

Bussemaker H, Li H, Siggia E . Building a dictionary for genomes: identification of presumptive regulatory sites by statistical analysis. Proc Natl Acad Sci U S A. 2000; 97(18):10096-100. PMC: 27717. DOI: 10.1073/pnas.180265397. 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

Keich U, Pevzner P . Finding motifs in the twilight zone. Bioinformatics. 2002; 18(10):1374-81. DOI: 10.1093/bioinformatics/18.10.1374. View

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

10.

Roth F, Hughes J, Estep P, Church G . Finding DNA regulatory motifs within unaligned noncoding sequences clustered by whole-genome mRNA quantitation. Nat Biotechnol. 1998; 16(10):939-45. DOI: 10.1038/nbt1098-939. View

11.

Liang S . cWINNOWER algorithm for finding fuzzy DNA motifs. Proc IEEE Comput Soc Bioinform Conf. 2006; 2:260-5. View

12.

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

13.

Hertz G, Stormo G . Identifying DNA and protein patterns with statistically significant alignments of multiple sequences. Bioinformatics. 1999; 15(7-8):563-77. DOI: 10.1093/bioinformatics/15.7.563. View

14.

Hertz G, Hartzell 3rd G, Stormo G . Identification of consensus patterns in unaligned DNA sequences known to be functionally related. Comput Appl Biosci. 1990; 6(2):81-92. DOI: 10.1093/bioinformatics/6.2.81. View

15.

Price A, Ramabhadran S, Pevzner P . Finding subtle motifs by branching from sample strings. Bioinformatics. 2003; 19 Suppl 2:ii149-55. DOI: 10.1093/bioinformatics/btg1072. View

16.

Yao Z, Weinberg Z, Ruzzo W . CMfinder--a covariance model based RNA motif finding algorithm. Bioinformatics. 2005; 22(4):445-52. DOI: 10.1093/bioinformatics/btk008. View

17.

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

18.

Sinha S, Tompa M . YMF: A program for discovery of novel transcription factor binding sites by statistical overrepresentation. Nucleic Acids Res. 2003; 31(13):3586-8. PMC: 169024. DOI: 10.1093/nar/gkg618. View

19.

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

20.

Yang X, Rajapakse J . Graphical approach to weak motif recognition. Genome Inform. 2005; 15(2):52-62. View