{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T01:12:13Z","timestamp":1773277933618,"version":"3.50.1"},"reference-count":33,"publisher":"Oxford University Press (OUP)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,2,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Sequencing capacity is currently growing more rapidly than CPU speed, leading to an analysis bottleneck in many genome projects. Alignment-free sequence analysis methods tend to be more efficient than their alignment-based counterparts. They may, therefore, be important in the long run for keeping sequence analysis abreast with sequencing.<\/jats:p>\n               <jats:p>Results: We derive and implement an alignment-free estimator of the number of pairwise mismatches, . Our implementation of , pim, is based on an enhanced suffix array and inherits the superior time and memory efficiency of this data structure. Simulations demonstrate that is accurate if mutations are distributed randomly along the chromosome. While real data often deviates from this ideal, remains useful for identifying regions of low genetic diversity using a sliding window approach. We demonstrate this by applying it to the complete genomes of 37 strains of Drosophila melanogaster, and to the genomes of two closely related Drosophila species, D.simulans and D.sechellia. In both cases, we detect the diversity minimum and discuss its biological implications.<\/jats:p>\n               <jats:p>Availability: \u00a0pim is written in standard C and its sources can be downloaded from http:\/\/guanine.evolbio.mpg.de\/pim\/.<\/jats:p>\n               <jats:p>Contact: \u00a0haubold@evolbio.mpg.de<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq689","type":"journal-article","created":{"date-parts":[[2010,12,15]],"date-time":"2010-12-15T02:24:00Z","timestamp":1292379840000},"page":"449-455","source":"Crossref","is-referenced-by-count":17,"title":["Alignment-free estimation of nucleotide diversity"],"prefix":"10.1093","volume":"27","author":[{"given":"Bernhard","family":"Haubold","sequence":"first","affiliation":[{"name":"1 Department of Evolutionary Genetics, Max-Planck-Institute for Evolutionary Biology, Pl\u00f6n and 2Abteilung f\u00fcr Mathematische Stochastik, Mathematical Institute, Albert-Ludwigs University, Freiburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Floyd A.","family":"Reed","sequence":"additional","affiliation":[{"name":"1 Department of Evolutionary Genetics, Max-Planck-Institute for Evolutionary Biology, Pl\u00f6n and 2Abteilung f\u00fcr Mathematische Stochastik, Mathematical Institute, Albert-Ludwigs University, Freiburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Pfaffelhuber","sequence":"additional","affiliation":[{"name":"1 Department of Evolutionary Genetics, Max-Planck-Institute for Evolutionary Biology, Pl\u00f6n and 2Abteilung f\u00fcr Mathematische Stochastik, Mathematical Institute, Albert-Ludwigs University, Freiburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2010,12,14]]},"reference":[{"key":"2023012511573234300_B1","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/3-540-45784-4_35","article-title":"The enhanced suffix array and its applications to genome analysis","volume-title":"Proceedings of the Second Workshop on Algorithms in Bioinformatics.","author":"Abouelhoda","year":"2002"},{"key":"2023012511573234300_B2","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1016\/j.ydbio.2008.07.003","article-title":"Sensory mechanisms controlling the timing of larval developmental and behavioral transitions require the drosophila DEG\/ENaC subunit, pickpocket1","volume":"322","author":"Ainsley","year":"2008","journal-title":"Dev. Biol."},{"key":"2023012511573234300_B3","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1038\/356519a0","article-title":"Levels of naturally occuring DNA polymorphism are correlated with recombination rates in Drosophila melanogaster","volume":"356","author":"Begun","year":"1992","journal-title":"Nature"},{"key":"2023012511573234300_B4","doi-asserted-by":"crossref","first-page":"e310","DOI":"10.1371\/journal.pbio.0050310","article-title":"Population genomics: whole-genome analysis of polymorphism and divergence in Drosophila simulans","volume":"5","author":"Begun","year":"2007","journal-title":"PLoS Biol."},{"key":"2023012511573234300_B5","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1186\/1471-2148-5-63","article-title":"Exploration of phylogenetic data using a global sequence analysis method","volume":"5","author":"Chapus","year":"2005","journal-title":"BMC Evol. Biol."},{"key":"2023012511573234300_B6","doi-asserted-by":"crossref","first-page":"1289","DOI":"10.1093\/genetics\/134.4.1289","article-title":"The effect of deleterious mutations on neutral molecular variation","volume":"134","author":"Charlesworth","year":"1993","journal-title":"Genetics"},{"key":"2023012511573234300_B7","doi-asserted-by":"crossref","first-page":"3221","DOI":"10.1093\/bioinformatics\/btp590","article-title":"Efficient estimation of pairwise distances between genomes","volume":"25","author":"Domazet-Lo\u0161o","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012511573234300_B8","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1038\/nature06341","article-title":"Evolution of genes and genomes on the Drosophila phylogeny","volume":"450","author":"Drosophila 12 Genomes Consortium","year":"2007","journal-title":"Nature"},{"key":"2023012511573234300_B9","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511779398","volume-title":"Probability\u2014Theory and Examples.","author":"Durrett","year":"2010","edition":"4th"},{"key":"2023012511573234300_B10","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1534\/genetics.108.093419","article-title":"Gentic changes accompanying the evolution of host specialization in Drosophila sechellia","volume":"181","author":"Dworkin","year":"2009","journal-title":"Genetics"},{"key":"2023012511573234300_B11","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1186\/1471-2105-8-252","article-title":"Compression-based classification of biological sequences and structures via the Universal Similarity Metric: experimental assessment","volume":"8","author":"Ferragina","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"2023012511573234300_B12","first-page":"1.12:1","article-title":"Compressed text indexes: from theory to practice","volume":"13","author":"Ferragina","year":"2008","journal-title":"ACM J. Exp. Algorithms"},{"key":"2023012511573234300_B13","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology.","author":"Gusfield","year":"1997"},{"key":"2023012511573234300_B14","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1186\/1471-2105-6-123","article-title":"Genome comparison without alignment using shortest unique substrings","volume":"6","author":"Haubold","year":"2005","journal-title":"BMC Bioinformatics"},{"key":"2023012511573234300_B15","doi-asserted-by":"crossref","first-page":"1487","DOI":"10.1089\/cmb.2009.0106","article-title":"Estimating mutation distances from unaligned genomes","volume":"16","author":"Haubold","year":"2009","journal-title":"J. Comput. Biol."},{"key":"2023012511573234300_B16","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1111\/j.1365-294X.2009.04482.x","article-title":"mlRho: a program for estimating the population mutation and recombination rates from shotgun-sequenced diploid genomes","volume":"19","author":"Haubold","year":"2010","journal-title":"Mol. Ecol."},{"key":"2023012511573234300_B17","doi-asserted-by":"crossref","first-page":"1020","DOI":"10.1101\/gr.074187.107","article-title":"Population genetic analysis of shotgun assemblies of genomic sequences from multiple individuals","volume":"18","author":"Hellmann","year":"2008","journal-title":"Genome Res."},{"key":"2023012511573234300_B18","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1093\/bioinformatics\/18.2.337","article-title":"Generating samples under a Wright-Fisher neutral model of genetic variation","volume":"18","author":"Hudson","year":"2002","journal-title":"Bioinformatics"},{"key":"2023012511573234300_B19","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1534\/genetics.107.080630","article-title":"Population genetic inference from resequencing data","volume":"181","author":"Jiang","year":"2009","journal-title":"Genetics"},{"key":"2023012511573234300_B20","doi-asserted-by":"crossref","first-page":"1320","DOI":"10.1101\/gr.5431206","article-title":"Inference of population genetic parameters in metagenomics: a clean look at messy data","volume":"16","author":"Johnson","year":"2006","journal-title":"Genome Res."},{"key":"2023012511573234300_B21","doi-asserted-by":"crossref","first-page":"151","DOI":"10.2307\/1403098","article-title":"An informal guide to the theory of conditioning in point processes","volume":"52","author":"Kallenberg","year":"1984","journal-title":"Int. Stat. Rev."},{"key":"2023012511573234300_B22","doi-asserted-by":"crossref","first-page":"R12","DOI":"10.1186\/gb-2004-5-2-r12","article-title":"Versatile and open software for comparing large genomes","volume":"5","author":"Kurtz","year":"2004","journal-title":"Genome Biol."},{"key":"2023012511573234300_B23","doi-asserted-by":"crossref","first-page":"1197","DOI":"10.1534\/genetics.108.092080","article-title":"Species-wide genetic variation and demographic history of drosophila sechellia, a species lacking population structure","volume":"182","author":"Legrand","year":"2009","journal-title":"Genetics"},{"key":"2023012511573234300_B24","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/BF00331251","article-title":"Relationships within the melanogaster species subgroup of the genus Drosophila (Sophophora). iv. the chromosomes of two new species","volume":"89","author":"Lemeunier","year":"1984","journal-title":"Chromosoma"},{"key":"2023012511573234300_B25","doi-asserted-by":"crossref","first-page":"2409","DOI":"10.1093\/molbev\/msn185","article-title":"Estimation of nucleotide diversity, disequilibrium coefficients, and mutation rates from high-coverage genomic-sequencing projects","volume":"25","author":"Lynch","year":"2008","journal-title":"Mol. Biol. Evol."},{"key":"2023012511573234300_B26","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1534\/genetics.109.100479","article-title":"Estimation of allele frequencies from high-coverage genome sequencing projects","volume":"182","author":"Lynch","year":"2009","journal-title":"Genetics"},{"key":"2023012511573234300_B27","first-page":"698","article-title":"Engineering a lightweight suffix array construction algorithm","volume-title":"ESA '02: Proceedings of the 10th Annual European Symposium on Algorithms.","author":"Manzini","year":"2002"},{"key":"2023012511573234300_B28","doi-asserted-by":"crossref","first-page":"4629","DOI":"10.1093\/nar\/11.13.4629","article-title":"An efficient method for finding repeats in molecular sequences","volume":"11","author":"Martinez","year":"1983","journal-title":"Nucleic Acids Res."},{"key":"2023012511573234300_B29","doi-asserted-by":"crossref","first-page":"1135","DOI":"10.1038\/nbt1486","article-title":"Next-generation DNA sequencing","volume":"26","author":"Shendure","year":"2008","journal-title":"Nat. Biotechnol."},{"key":"2023012511573234300_B30","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1093\/genetics\/123.3.585","article-title":"Statistical method for testing the neutral mutation hypothesis by DNA polymorphism","volume":"123","author":"Tajima","year":"1989","journal-title":"Genetics"},{"key":"2023012511573234300_B31","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1089\/cmb.2006.13.336","article-title":"The average common substring approach to phylogenomic reconstruction","volume":"13","author":"Ulitsky","year":"2006","journal-title":"J. Comput. Biol."},{"key":"2023012511573234300_B32","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1093\/bioinformatics\/btg005","article-title":"Alignment-free sequence comparison\u2014a review","volume":"19","author":"Vinga","year":"2003","journal-title":"Bioinformatics"},{"key":"2023012511573234300_B33","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1006\/tpbi.1998.1403","article-title":"Recombination as a point process along a sequence","volume":"55","author":"Wiuf","year":"1999","journal-title":"Theor. Popul. Biol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/4\/449\/48867838\/bioinformatics_27_4_449.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/4\/449\/48867838\/bioinformatics_27_4_449.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T12:43:08Z","timestamp":1674650588000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/27\/4\/449\/197811"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12,14]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,2,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq689","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2011,2,15]]},"published":{"date-parts":[[2010,12,14]]}}}