{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T22:57:57Z","timestamp":1780786677866,"version":"3.54.1"},"reference-count":20,"publisher":"Oxford University Press (OUP)","issue":"24","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008,12,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Background: The computation of the statistical properties of motif occurrences has an obviously relevant application: patterns that are significantly over- or under-represented in genomes or proteins are interesting candidates for biological roles. However, the problem is computationally hard; as a result, virtually all the existing motif finders use fast but approximate scoring functions, in spite of the fact that they have been shown to produce systematically incorrect results. A few interesting exact approaches are known, but they are very slow and hence not practical in the case of realistic sequences.<\/jats:p>\n               <jats:p>Results: We give an exact solution, solely based on deterministic finite-state automata (DFA), to the problem of finding the whole relevant part of the probability distribution function of a simple-word motif in a homogeneous (biological) sequence. Out of that, the z-value can always be computed, while the P-value can be obtained either when it is not too extreme with respect to the number of floating-point digits available in the implementation, or when the number of pattern occurrences is moderately low. In particular, the time complexity of the algorithms for Markov models of moderate order (0\u2264m\u22642) is far better than that of Nuel, which was the fastest similar exact algorithm known to date; in many cases, even approximate methods are outperformed.<\/jats:p>\n               <jats:p>Conclusions: DFA are a standard tool of computer science for the study of patterns; previous works in biology propose algorithms involving automata, but there they are used, respectively, as a first step to write a generating function, or to build a finite Markov-chain imbedding (FMCI). In contrast, we directly rely on DFA to perform the calculations; thus we manage to obtain an algorithm which is both easily interpretable and efficient. This approach can be used for exact statistical studies of very long genomes and protein sequences, as we illustrate with some examples on the scale of the human genome.<\/jats:p>\n               <jats:p>Contact: \u00a0paolo.ribeca@gmail.com<\/jats:p>","DOI":"10.1093\/bioinformatics\/btn525","type":"journal-article","created":{"date-parts":[[2008,10,10]],"date-time":"2008-10-10T00:34:47Z","timestamp":1223598887000},"page":"2839-2848","source":"Crossref","is-referenced-by-count":25,"title":["Faster exact Markovian probability functions for motif occurrences: a DFA-only approach"],"prefix":"10.1093","volume":"24","author":[{"given":"Paolo","family":"Ribeca","sequence":"first","affiliation":[{"name":"Bioinformatics and Genomics Unit, Center for Genomic Regulation, C\/ Dr.Aiguader 88, E08003 Barcelona, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Emanuele","family":"Raineri","sequence":"additional","affiliation":[{"name":"Bioinformatics and Genomics Unit, Center for Genomic Regulation, C\/ Dr.Aiguader 88, E08003 Barcelona, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2008,10,9]]},"reference":[{"key":"2023020212310095500_B1","volume-title":"Compilers: Principles, Techniques, and Tools.","author":"Aho","year":"2006","edition":"2nd edn"},{"key":"2023020212310095500_B2","first-page":"28","article-title":"Fitting a mixture model by expectation maximization to discover motifs in biopolymers","volume-title":"Proceedings of the Second International Conference on Intelligent Systems for Molecular Biology.","author":"Bailey","year":"1994"},{"key":"2023020212310095500_B3","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1038\/nmeth1061","article-title":"Trawler: de novo regulatory motif discovery pipeline for chromatin immunoprecipitation","volume":"4","author":"Ettwiller","year":"2007","journal-title":"Nat. Methods"},{"key":"2023020212310095500_B4","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1109\/JPROC.2004.840301","article-title":"The design and implementation of FFTW3","volume":"93","author":"Frigo","year":"2005","journal-title":"Proc. IEEE"},{"key":"2023020212310095500_B5","volume-title":"Concrete Mathematics.","author":"Graham","year":"1994"},{"key":"2023020212310095500_B6","doi-asserted-by":"crossref","first-page":"1614","DOI":"10.1371\/journal.pgen.0030153","article-title":"Identification of DNA motifs implicated in maintenance of bacterial core genomes by predictive modeling","volume":"3","author":"Halpern","year":"2007","journal-title":"PLoS Genet."},{"key":"2023020212310095500_B7","doi-asserted-by":"crossref","first-page":"1501","DOI":"10.1006\/jmbi.1994.1104","article-title":"Hidden Markov models in computational biology: Application to protein modeling","volume":"235","author":"Krogh","year":"1994","journal-title":"J. Mol. Biol."},{"key":"2023020212310095500_B8","author":"Leroy","year":"2008"},{"key":"2023020212310095500_B9","doi-asserted-by":"crossref","first-page":"S161","DOI":"10.1093\/bioinformatics\/18.suppl_2.S161","article-title":"Proteome analysis based on motif statistics","volume":"18","author":"Nicod\u00e8me","year":"2002","journal-title":"Bioinformatics"},{"key":"2023020212310095500_B10","doi-asserted-by":"crossref","DOI":"10.1186\/1748-7188-1-5","article-title":"EffectiveP-value computations using finite Markov chain imbedding (FMCI): application to local score and to pattern statistics","volume":"1","author":"Nuel","year":"2006","journal-title":"Algorithms Mol. Biol"},{"key":"2023020212310095500_B11","doi-asserted-by":"crossref","DOI":"10.2202\/1544-6115.1219","article-title":"Numerical solutions for pattern statistics on Markov chains","volume":"5","author":"Nuel","year":"2006","journal-title":"Stat. Appl. Genet. Mol. Biol"},{"key":"2023020212310095500_B12","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1239\/jap\/1208358964","article-title":"Pattern Markov chains: optimal Markov chain embedding through deterministic finite automata","volume":"45","author":"Nuel","year":"2007","journal-title":"J. Appl. Prob."},{"key":"2023020212310095500_B13","author":"Nuel","year":"2008"},{"key":"2023020212310095500_B14","volume-title":"Numerical Recipes in C.","author":"Press","year":"2002"},{"key":"2023020212310095500_B15","author":"Ribeca","year":"2008"},{"key":"2023020212310095500_B16","volume-title":"DNA, Words and Models: Statistics of Exceptional Words.","author":"Robin","year":"2005"},{"key":"2023020212310095500_B17","doi-asserted-by":"crossref","DOI":"10.1186\/1471-2105-8-84","article-title":"Statistical tests to compare motif count exceptionalities","volume":"8","author":"Robin","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"2023020212310095500_B18","doi-asserted-by":"crossref","first-page":"D444","DOI":"10.1093\/nar\/gkj013","article-title":"The YEASTRACT database: a tool for the analysis of transcription regulatory associations in Saccharomices cerevisiae","volume":"34","author":"Teixeira","year":"2006","journal-title":"Nucleic Acids Res."},{"key":"2023020212310095500_B19","doi-asserted-by":"crossref","first-page":"10559","DOI":"10.1073\/pnas.0610776104","article-title":"Chromosomal periodicity of evolutionarily conserved gene pairs","volume":"104","author":"Wright","year":"2007","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023020212310095500_B20","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1093\/bioinformatics\/btl662","article-title":"Computing exactP-values for DNA motifs","volume":"23","author":"Zhang","year":"2007","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/24\/2839\/49056491\/bioinformatics_24_24_2839.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/24\/2839\/49056491\/bioinformatics_24_24_2839.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T15:17:33Z","timestamp":1675351053000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/24\/24\/2839\/196199"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10,9]]},"references-count":20,"journal-issue":{"issue":"24","published-print":{"date-parts":[[2008,12,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btn525","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2008,12,15]]},"published":{"date-parts":[[2008,10,9]]}}}