{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T18:35:56Z","timestamp":1767206156966,"version":"build-2238731810"},"reference-count":27,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2018,1,10]],"date-time":"2018-01-10T00:00:00Z","timestamp":1515542400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["www.mdpi.com"],"crossmark-restriction":true},"short-container-title":["Algorithms"],"abstract":"<jats:p>Seeding heuristics are the most widely used strategies to speed up sequence alignment in bioinformatics. Such strategies are most successful if they are calibrated, so that the speed-versus-accuracy trade-off can be properly tuned. In the widely used case of read mapping, it has been so far impossible to predict the success rate of competing seeding strategies for lack of a theoretical framework. Here, we present an approach to estimate such quantities based on the theory of analytic combinatorics. The strategy is to specify a combinatorial construction of reads where the seeding heuristic fails, translate this specification into a generating function using formal rules, and finally extract the probabilities of interest from the singularities of the generating function. The generating function can also be used to set up a simple recurrence to compute the probabilities with greater precision. We use this approach to construct simple estimators of the success rate of the seeding heuristic under different types of sequencing errors, and we show that the estimates are accurate in practical situations. More generally, this work shows novel strategies based on analytic combinatorics to compute probabilities of interest in bioinformatics.<\/jats:p>","DOI":"10.3390\/a11010003","type":"journal-article","created":{"date-parts":[[2018,1,10]],"date-time":"2018-01-10T12:41:10Z","timestamp":1515588070000},"page":"3","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Analytic Combinatorics for Computing Seeding Probabilities"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3473-1632","authenticated-orcid":false,"given":"Guillaume","family":"Filion","sequence":"first","affiliation":[{"name":"Department of Biological Sciences, University of Toronto Scarborough, 1265 Military Trail, Toronto, ON M1C 1A4, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,1,10]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1016\/j.molcel.2015.05.004","article-title":"High-throughput sequencing technologies","volume":"58","author":"Reuter","year":"2015","journal-title":"Mol. Cell"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1093\/gigascience\/gix100","article-title":"Parallel sequencing lives, or what makes large sequencing projects successful","volume":"6","author":"Quilez","year":"2017","journal-title":"Gigascience"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1093\/bib\/bbq015","article-title":"A survey of sequence alignment algorithms for next-generation sequencing","volume":"11","author":"Li","year":"2010","journal-title":"Brief. Bioinform."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Durbin, R., Eddy, S.R., Krogh, A., and Mitchison, G. (1998). Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids, Cambridge University Press.","DOI":"10.1017\/CBO9780511790492"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Sun, Y., and Buhler, J. (2006). Choosing the best heuristic for seeded alignment of DNA sequences. BMC Bioinform., 7.","DOI":"10.1186\/1471-2105-7-133"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J. Mol. Biol."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"5873","DOI":"10.1073\/pnas.90.12.5873","article-title":"Applications and statistics for multiple high-scoring segments in molecular sequences","volume":"90","author":"Karlin","year":"1993","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"2264","DOI":"10.1073\/pnas.87.6.2264","article-title":"Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes","volume":"87","author":"Karlin","year":"1990","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_9","unstructured":"Ferragina, P., and Manzini, G. (2000, January 12\u201314). Opportunistic Data Structures with Applications. Proceedings of the 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, USA."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","article-title":"Fast and accurate short read alignment with Burrows-Wheeler transform","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"R25","DOI":"10.1186\/gb-2009-10-3-r25","article-title":"Ultrafast and memory-efficient alignment of short DNA sequences to the human genome","volume":"10","author":"Langmead","year":"2009","journal-title":"Genome Biol."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1137\/0403019","article-title":"Singularity analysis of generating functions","volume":"3","author":"Flajolet","year":"1990","journal-title":"SIAM J. Discrete Math."},{"key":"ref_13","unstructured":"Flajolet, P., and Sedgewick, R. (1996). An introduction to the analysis of algorithms, Addison-Wesley Longman Publishing Co., Inc.. [2nd ed.]."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Flajolet, P., and Sedgewick, R. (2009). Analytic Combinatorics, Cambridge University Press. [1st ed.].","DOI":"10.1017\/CBO9780511801655"},{"key":"ref_15","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":"ref_16","doi-asserted-by":"crossref","first-page":"1050","DOI":"10.1080\/01621459.1994.10476841","article-title":"Distribution Theory of Runs: A Markov Chain Approach","volume":"89","author":"Fu","year":"1994","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_17","unstructured":"Chan, J., Daykin, J.W., and Sohel, M. (2009). A word counting graph. London Algorithmics 2008: Theory and Practice (Texts in Algorithmics), Rahman London College Publications."},{"key":"ref_18","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. Prob."},{"key":"ref_19","unstructured":"Chen, K., and Ravindran, A. (2016). Counting Regular Expressions in Degenerated Sequences Through Lazy Markov Chain Embedding. Forging Connections between Computational Mathematics and Computational Geometry: Papers from the 3rd International Conference on Computational Mathematics and Computational Geometry, Springer International Publishing."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Chaisson, M.J., and Tesler, G. (2012). Mapping single molecule sequencing reads using basic local alignment with successive refinement (BLASR): Application and theory. BMC Bioinform., 13.","DOI":"10.1186\/1471-2105-13-238"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0001-8708(81)90052-9","article-title":"Une th\u00e9orie combinatoire des s\u00e9ries formelles","volume":"42","author":"Joyal","year":"1981","journal-title":"Adv. Math."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Bona, M. (2015). Handbook of Enumerative Combinatorics, CRC Press.","DOI":"10.1201\/b18255"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0166-218X(92)90177-C","article-title":"Birthday Paradox, Coupon Collectors, Caching Algorithms and Self-organizing Search","volume":"39","author":"Flajolet","year":"1992","journal-title":"Discrete Appl. Math."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Pemantle, R., and Wilson, M.C. (2013). Analytic Combinatorics in Several Variables, Cambridge University Press.","DOI":"10.1017\/CBO9781139381864"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1137\/1016082","article-title":"Asymptotic Methods in Enumeration","volume":"16","author":"Bender","year":"1974","journal-title":"SIAM Rev."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"e90","DOI":"10.1093\/nar\/gkr344","article-title":"Sequence-specific error profile of Illumina sequencers","volume":"39","author":"Nakamura","year":"2011","journal-title":"Nucleic Acids Res."},{"key":"ref_27","unstructured":"R Core Team (2015). R: A Language and Environment for Statistical Computing, R Foundation for Statistical Computing."}],"updated-by":[{"DOI":"10.3390\/a15060206","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2018,1,10]],"date-time":"2018-01-10T00:00:00Z","timestamp":1515542400000}}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/1\/3\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,3]],"date-time":"2025-08-03T23:15:14Z","timestamp":1754262914000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/1\/3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,10]]},"references-count":27,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2018,1]]}},"alternative-id":["a11010003"],"URL":"https:\/\/doi.org\/10.3390\/a11010003","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1,10]]}}}