Fast and Exact Quantification of Motif Occurrences in Biological Sequences

Overview

Journal BMC Bioinformatics

Publisher Biomed Central

Specialty Biology

Date 2021 Sep 19

PMID 34537012

Citations 3

Authors

Mattia Prosperi

Simone Marini

Christina Boucher

Affiliations

Soon will be listed here.

Abstract

Background: Identification of motifs and quantification of their occurrences are important for the study of genetic diseases, gene evolution, transcription sites, and other biological mechanisms. Exact formulae for estimating count distributions of motifs under Markovian assumptions have high computational complexity and are impractical to be used on large motif sets. Approximated formulae, e.g. based on compound Poisson, are faster, but reliable p value calculation remains challenging. Here, we introduce 'motif_prob', a fast implementation of an exact formula for motif count distribution through progressive approximation with arbitrary precision. Our implementation speeds up the exact calculation, usually impractical, making it feasible and posit to substitute currently employed heuristics.

Results: We implement motif_prob in both Perl and C+ + languages, using an efficient error-bound iterative process for the exact formula, providing comparison with state-of-the-art tools (e.g. MoSDi) in terms of precision, run time benchmarks, along with a real-world use case on bacterial motif characterization. Our software is able to process a million of motifs (13-31 bases) over genome lengths of 5 million bases within the minute on a regular laptop, and the run times for both the Perl and C+ + code are several orders of magnitude smaller (50-1000× faster) than MoSDi, even when using their fast compound Poisson approximation (60-120× faster). In the real-world use cases, we first show the consistency of motif_prob with MoSDi, and then how the p-value quantification is crucial for enrichment quantification when bacteria have different GC content, using motifs found in antimicrobial resistance genes. The software and the code sources are available under the MIT license at https://github.com/DataIntellSystLab/motif_prob .

Conclusions: The motif_prob software is a multi-platform and efficient open source solution for calculating exact frequency distributions of motifs. It can be integrated with motif discovery/characterization tools for quantifying enrichment and deviation from expected frequency ranges with exact p values, without loss in data processing efficiency.

Citing Articles

Optimizing resource utilization for large scale problems through architecture aware scheduling.

Elsawwaf A, Aly G, Faheem H, Fayez M Sci Rep. 2024; 14(1):26356.

PMID: 39487166 PMC: 11530424. DOI: 10.1038/s41598-024-75711-8.

An average-case efficient two-stage algorithm for enumerating all longest common substrings of minimum length between genome pairs.

Prosperi M, Marini S, Boucher C Proc (IEEE Int Conf Healthc Inform). 2024; 2024:93-102.

PMID: 39308639 PMC: 11412151. DOI: 10.1109/ichi61247.2024.00020.

OCTOPUS: Disk-based, Multiplatform, Mobile-friendly Metagenomics Classifier.

Marini S, Barquero A, Wadhwani A, Bian J, Ruiz J, Boucher C bioRxiv. 2024; .

PMID: 38559026 PMC: 10979967. DOI: 10.1101/2024.03.15.585215.

References

Hildebrand F, Meyer A, Eyre-Walker A . Evidence of selection upon genomic GC-content in bacteria. PLoS Genet. 2010; 6(9):e1001107. PMC: 2936529. DOI: 10.1371/journal.pgen.1001107. View

Fogel G, Weekes D, Varga G, Dow E, Harlow H, Onyia J . Discovery of sequence motifs related to coexpression of genes using evolutionary computation. Nucleic Acids Res. 2004; 32(13):3826-35. PMC: 506801. DOI: 10.1093/nar/gkh713. View

Luu P, Scholer H, Arauzo-Bravo M . Disclosing the crosstalk among DNA methylation, transcription factors, and histone marks in human pluripotent cells through discovery of DNA methylation motifs. Genome Res. 2013; 23(12):2013-29. PMC: 3847772. DOI: 10.1101/gr.155960.113. View

Dang L, Tondl M, Chiu M, Revote J, Paten B, Tano V . TrawlerWeb: an online de novo motif discovery tool for next-generation sequencing datasets. BMC Genomics. 2018; 19(1):238. PMC: 5887194. DOI: 10.1186/s12864-018-4630-0. View

Robin S, Daudin J, Richard H, Sagot M, Schbath S . Occurrence probability of structured motifs in random sequences. J Comput Biol. 2003; 9(6):761-73. DOI: 10.1089/10665270260518254. View

Doster E, Lakin S, Dean C, Wolfe C, Young J, Boucher C . MEGARes 2.0: a database for classification of antimicrobial drug, biocide and metal resistance determinants in metagenomic sequence data. Nucleic Acids Res. 2019; 48(D1):D561-D569. PMC: 7145535. DOI: 10.1093/nar/gkz1010. View

Bejerano G, Friedman N, Tishby N . Efficient exact p-value computation for small sample, sparse, and surprising categorical data. J Comput Biol. 2005; 11(5):867-86. DOI: 10.1089/cmb.2004.11.867. View

Marschall T, Rahmann S . Efficient exact motif discovery. Bioinformatics. 2009; 25(12):i356-64. PMC: 2687942. DOI: 10.1093/bioinformatics/btp188. View

Pavesi G, Mereghetti P, Mauri G, Pesole G . Weeder Web: discovery of transcription factor binding sites in a set of sequences from co-regulated genes. Nucleic Acids Res. 2004; 32(Web Server issue):W199-203. PMC: 441603. DOI: 10.1093/nar/gkh465. View

10.

Gupta S, Stamatoyannopoulos J, Bailey T, Noble W . Quantifying similarity between motifs. Genome Biol. 2007; 8(2):R24. PMC: 1852410. DOI: 10.1186/gb-2007-8-2-r24. View

11.

Bailey T, Boden M, Buske F, Frith M, Grant C, Clementi L . MEME SUITE: tools for motif discovery and searching. Nucleic Acids Res. 2009; 37(Web Server issue):W202-8. PMC: 2703892. DOI: 10.1093/nar/gkp335. View

12.

Gatchel J, Zoghbi H . Diseases of unstable repeat expansion: mechanisms and common principles. Nat Rev Genet. 2005; 6(10):743-55. DOI: 10.1038/nrg1691. View

13.

Lladser M, Betterton M, Knight R . Multiple pattern matching: a Markov chain approach. J Math Biol. 2007; 56(1-2):51-92. DOI: 10.1007/s00285-007-0109-3. View

14.

Li Y, Ni P, Zhang S, Li G, Su Z . ProSampler: an ultrafast and accurate motif finder in large ChIP-seq datasets for combinatory motif discovery. Bioinformatics. 2019; 35(22):4632-4639. PMC: 6853706. DOI: 10.1093/bioinformatics/btz290. View

15.

Pape U, Rahmann S, Sun F, Vingron M . Compound poisson approximation of the number of occurrences of a position frequency matrix (PFM) on both strands. J Comput Biol. 2008; 15(6):547-64. PMC: 2607244. DOI: 10.1089/cmb.2007.0084. View

16.

Thomas-Chollier M, Herrmann C, Defrance M, Sand O, Thieffry D, van Helden J . RSAT peak-motifs: motif analysis in full-size ChIP-seq datasets. Nucleic Acids Res. 2011; 40(4):e31. PMC: 3287167. DOI: 10.1093/nar/gkr1104. View

17.

Bailey T . DREME: motif discovery in transcription factor ChIP-seq data. Bioinformatics. 2011; 27(12):1653-9. PMC: 3106199. DOI: 10.1093/bioinformatics/btr261. 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.

Ibironke O, McGuinness L, Lu S, Wang Y, Hussain S, Weisel C . Species-level evaluation of the human respiratory microbiome. Gigascience. 2020; 9(4). PMC: 7162353. DOI: 10.1093/gigascience/giaa038. View

20.

Hashim F, Mabrouk M, Al-Atabany W . Review of Different Sequence Motif Finding Algorithms. Avicenna J Med Biotechnol. 2019; 11(2):130-148. PMC: 6490410. View