{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T14:46:15Z","timestamp":1790261175403,"version":"4.1.0"},"reference-count":26,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":2685,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,6,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: The motif discovery problem consists of finding over-represented patterns in a collection of biosequences. It is one of the classical sequence analysis problems, but still has not been satisfactorily solved in an exact and efficient manner. This is partly due to the large number of possibilities of defining the motif search space and the notion of over-representation. Even for well-defined formalizations, the problem is frequently solved in an ad hoc manner with heuristics that do not guarantee to find the best motif.<\/jats:p>\n               <jats:p>Results: We show how to solve the motif discovery problem (almost) exactly on a practically relevant space of IUPAC generalized string patterns, using the p-value with respect to an i.i.d. model or a Markov model as the measure of over-representation. In particular, (i) we use a highly accurate compound Poisson approximation for the null distribution of the number of motif occurrences. We show how to compute the exact clump size distribution using a recently introduced device called probabilistic arithmetic automaton (PAA). (ii) We define two p-value scores for over-representation, the first one based on the total number of motif occurrences, the second one based on the number of sequences in a collection with at least one occurrence. (iii) We describe an algorithm to discover the optimal pattern with respect to either of the scores. The method exploits monotonicity properties of the compound Poisson approximation and is by orders of magnitude faster than exhaustive enumeration of IUPAC strings (11.8 h compared with an extrapolated runtime of 4.8 years). (iv) We justify the use of the proposed scores for motif discovery by showing our method to outperform other motif discovery algorithms (e.g. MEME, Weeder) on benchmark datasets. We also propose new motifs on Mycobacterium tuberculosis.<\/jats:p>\n               <jats:p>Availability and Implementation: The method has been implemented in Java. It can be obtained from http:\/\/ls11-www.cs.tu-dortmund.de\/people\/marschal\/paa_md\/<\/jats:p>\n               <jats:p>Contact: \u00a0tobias.marschall@tu-dortmund.de; sven.rahmann@tu-dortmund.de<\/jats:p>","DOI":"10.1093\/bioinformatics\/btp188","type":"journal-article","created":{"date-parts":[[2009,5,28]],"date-time":"2009-05-28T15:48:54Z","timestamp":1243525734000},"page":"i356-i364","source":"Crossref","is-referenced-by-count":46,"title":["Efficient exact motif discovery"],"prefix":"10.1093","volume":"25","author":[{"given":"Tobias","family":"Marschall","sequence":"first","affiliation":[{"name":"Bioinformatics for High-Throughput Technologies at the Chair of Algorithm Engineering, Computer Science Department, TU Dortmund, D-44221 Dortmund, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sven","family":"Rahmann","sequence":"additional","affiliation":[{"name":"Bioinformatics for High-Throughput Technologies at the Chair of Algorithm Engineering, Computer Science Department, TU Dortmund, D-44221 Dortmund, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2009,5,27]]},"reference":[{"key":"2023013112010952800_B1","first-page":"28","article-title":"Fitting a mixture model by expectation maximization to discover motifs in biopolymer","volume-title":"Proceedings of the Second International Conference on Intelligent Systems for Molecular Biology (ISMB).","author":"Bailey","year":"1994"},{"key":"2023013112010952800_B2","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1186\/1748-7188-2-13","article-title":"Exact P-value calculation for heterotypic clusters of regulatory motifs and its application in computational annotation of cis-regulatory modules","volume":"2","author":"Boeva","year":"2007","journal-title":"Algorithm Mol. Biol."},{"key":"2023013112010952800_B3","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-3124-8","volume-title":"Markov Chains.","author":"Br\u00e9maud","year":"1999"},{"key":"2023013112010952800_B4","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids.","author":"Durbin","year":"1998"},{"key":"2023013112010952800_B5","doi-asserted-by":"crossref","first-page":"R104","DOI":"10.1186\/gb-2005-6-12-r104","article-title":"The discovery, positioning and verification of a set of transcription-associated motifs in vertebrates","volume":"6","author":"Ettwiller","year":"2005","journal-title":"Genome Biol."},{"key":"2023013112010952800_B6","doi-asserted-by":"crossref","first-page":"2303","DOI":"10.1093\/bioinformatics\/btn444","article-title":"Seeder: discriminative seeding DNA motif discovery","volume":"24","author":"Fauteux","year":"2008","journal-title":"Bioinformatics"},{"key":"2023013112010952800_B7","doi-asserted-by":"crossref","first-page":"e150","DOI":"10.1093\/bioinformatics\/btl243","article-title":"MotifCut: regulatory motifs finding with maximum density subgraphs","volume":"22","author":"Fratkin","year":"2006","journal-title":"Bioinformatics"},{"key":"2023013112010952800_B8","doi-asserted-by":"crossref","first-page":"1325","DOI":"10.1093\/bioinformatics\/btn198","article-title":"Eukaryotic transcription factor binding sites\u2013modeling and integrative search methods","volume":"24","author":"Hannenhalli","year":"2008","journal-title":"Bioinformatics"},{"key":"2023013112010952800_B9","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1186\/1748-7188-1-8","article-title":"Analysis of computational approaches for motif discovery","volume":"1","author":"Li","year":"2006","journal-title":"Algorithms Mol. Biol."},{"key":"2023013112010952800_B10","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/s00285-007-0109-3","article-title":"Multiple pattern matching: a Markov chain approach","volume":"56","author":"Lladser","year":"2008","journal-title":"J. Math. Biol."},{"key":"2023013112010952800_B11","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/978-3-540-69068-9_11","article-title":"Probabilistic arithmetic automata and their application to pattern matching statistics","volume-title":"Proceedings of the 19th Annual Symposium on Combinatorial Pattern Matching (CPM).","author":"Marschall","year":"2008"},{"key":"2023013112010952800_B12","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1016\/S0304-3975(01)00264-X","article-title":"Motif statistics","volume":"287","author":"Nicod\u00e8me","year":"2002","journal-title":"Theor. Comput. Sci."},{"key":"2023013112010952800_B13","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":"2008","journal-title":"J. Appl. Probab."},{"key":"2023013112010952800_B14","doi-asserted-by":"crossref","first-page":"W199","DOI":"10.1093\/nar\/gkh465","article-title":"Weeder Web: discovery of transcription factor binding sites in a set of sequences from co-regulated genes","volume":"32","author":"Pavesi","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023013112010952800_B15","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/S0166-218X(00)00195-5","article-title":"A unifed approach to word occurrence probabilities","volume":"104","author":"R\u00e9gnier","year":"2000","journal-title":"Discrete Appl. Math."},{"key":"2023013112010952800_B16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1089\/10665270050081360","article-title":"Probabilistic and statistical properties of words: an overview","volume":"7","author":"Reinert","year":"2000","journal-title":"J. Comput. Biol."},{"key":"2023013112010952800_B17","volume-title":"DNA, Words and Models. Statistics of Exceptional Words.","author":"Robin","year":"2005"},{"key":"2023013112010952800_B18","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1239\/aap\/1175266472","article-title":"Improved compound Poisson approximation for the number of occurrences of multiple words in a stationary Markov chain","volume":"39","author":"Roquain","year":"2007","journal-title":"Adv. Appl. Prob."},{"key":"2023013112010952800_B19","first-page":"374","article-title":"Spelling approximate repeated or common motifs using a suffix tree","volume-title":"LATIN '98: Proceedings of the Third Latin American Symposium on Theoretical Informatics, LNCS 1380.","author":"Sagot","year":"1998"},{"key":"2023013112010952800_B20","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1186\/1745-6150-1-11","article-title":"A survey of motif discovery methods in an integrated framework","volume":"1","author":"Sandve","year":"2006","journal-title":"Biol. Direct"},{"key":"2023013112010952800_B21","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1186\/1471-2105-8-193","article-title":"Improved benchmarks for computational motif discovery","volume":"8","author":"Sandve","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"2023013112010952800_B22","first-page":"1","article-title":"Compound poisson approximation of word counts in DNA sequences","volume":"1","author":"Schbath","year":"1995","journal-title":"ESAIM: Prob. Stat."},{"key":"2023013112010952800_B23","doi-asserted-by":"crossref","first-page":"3586","DOI":"10.1093\/nar\/gkg618","article-title":"YMF: a program for discovery of novel transcription factor binding sites by statistical overrepresentation","volume":"31","author":"Sinha","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023013112010952800_B24","doi-asserted-by":"crossref","first-page":"868","DOI":"10.1016\/j.dam.2005.07.016","article-title":"Waiting times for clumps of patterns and for structured motifs in random sequences","volume":"155","author":"Stefanov","year":"2007","journal-title":"Discrete Appl. Math."},{"key":"2023013112010952800_B25","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1038\/nbt1053","article-title":"Assessing computational tools for the discovery of transcription factor binding sites","volume":"23","author":"Tompa","year":"2005","journal-title":"Nat. Biotechnol."},{"key":"2023013112010952800_B26","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4899-6846-3","volume-title":"Introduction to Computational Biology: Maps, Sequences and Genomes.","author":"Waterman","year":"1995"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/12\/i356\/48991590\/bioinformatics_25_12_i356.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/12\/i356\/48991590\/bioinformatics_25_12_i356.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T21:08:30Z","timestamp":1675199310000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/25\/12\/i356\/187108"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5,27]]},"references-count":26,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2009,6,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btp188","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2009,6,15]]},"published":{"date-parts":[[2009,5,27]]}}}