{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T16:19:13Z","timestamp":1771863553574,"version":"3.50.1"},"reference-count":25,"publisher":"Oxford University Press (OUP)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015,4,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: A standard approach to classifying sets of genomes is to calculate their pairwise distances. This is difficult for large samples. We have therefore developed an algorithm for rapidly computing the evolutionary distances between closely related genomes.<\/jats:p>\n               <jats:p>Results: Our distance measure is based on ungapped local alignments that we anchor through pairs of maximal unique matches of a minimum length. These exact matches can be looked up efficiently using enhanced suffix arrays and our implementation requires approximately only 1 s and 45 MB RAM\/Mbase analysed. The pairing of matches distinguishes non-homologous from homologous regions leading to accurate distance estimation. We show this by analysing simulated data and genome samples ranging from 29 Escherichia coli\/Shigella genomes to 3085 genomes of Streptococcus pneumoniae.<\/jats:p>\n               <jats:p>Availability and implementation: We have implemented the computation of anchor distances in the multithreaded UNIX command-line program andi for ANchor DIstances. C sources and documentation are posted at http:\/\/github.com\/evolbioinf\/andi\/<\/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\/btu815","type":"journal-article","created":{"date-parts":[[2014,12,12]],"date-time":"2014-12-12T02:23:08Z","timestamp":1418350988000},"page":"1169-1175","source":"Crossref","is-referenced-by-count":99,"title":["<tt>andi<\/tt>: Fast and accurate estimation of evolutionary distances between closely related genomes"],"prefix":"10.1093","volume":"31","author":[{"given":"Bernhard","family":"Haubold","sequence":"first","affiliation":[{"name":"1 Department of Evolutionary Genetics, Max-Planck-Institute for Evolutionary Biology, 24306 Pl\u00f6n, Germany, 2Institue for Neuro- and Bioinformatics, L\u00fcbeck University, 23562 L\u00fcbeck, Germany and 3Mathematical Stochastics, Mathematical Institute, Freiburg University, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabian","family":"Kl\u00f6tzl","sequence":"additional","affiliation":[{"name":"1 Department of Evolutionary Genetics, Max-Planck-Institute for Evolutionary Biology, 24306 Pl\u00f6n, Germany, 2Institue for Neuro- and Bioinformatics, L\u00fcbeck University, 23562 L\u00fcbeck, Germany and 3Mathematical Stochastics, Mathematical Institute, Freiburg University, Germany"},{"name":"1 Department of Evolutionary Genetics, Max-Planck-Institute for Evolutionary Biology, 24306 Pl\u00f6n, Germany, 2Institue for Neuro- and Bioinformatics, L\u00fcbeck University, 23562 L\u00fcbeck, Germany and 3Mathematical Stochastics, Mathematical Institute, Freiburg University, 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, 24306 Pl\u00f6n, Germany, 2Institue for Neuro- and Bioinformatics, L\u00fcbeck University, 23562 L\u00fcbeck, Germany and 3Mathematical Stochastics, Mathematical Institute, Freiburg University, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2014,12,10]]},"reference":[{"key":"2023051309020204400_btu815-B1","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":"2023051309020204400_btu815-B2","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1093\/bioinformatics\/btq665","article-title":"Mugsy: fast multiple alignment of closely related whole genomes","volume":"27","author":"Angiuoli","year":"2011","journal-title":"Bioinformatics"},{"key":"2023051309020204400_btu815-B3","doi-asserted-by":"crossref","first-page":"1077","DOI":"10.1093\/molbev\/msu088","article-title":"Automated reconstruction of whole-genome phylogenies from short-sequence reads","volume":"31","author":"Bertels","year":"2014","journal-title":"Mol. Biol. Evol."},{"key":"2023051309020204400_btu815-B4","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1038\/ng.2895","article-title":"Dense genomic sampling identifies highways of pneumococcal recombination","volume":"46","author":"Chewapreecha","year":"2014","journal-title":"Nat. Genet."},{"key":"2023051309020204400_btu815-B5","doi-asserted-by":"crossref","first-page":"945","DOI":"10.1089\/cmb.2012.0122","article-title":"Detecting phylogenetic signals in eukaryotic whole genome sequences","volume":"19","author":"Cohen","year":"2012","journal-title":"J. Comput. Biol."},{"key":"2023051309020204400_btu815-B6","doi-asserted-by":"crossref","first-page":"1394","DOI":"10.1101\/gr.2289704","article-title":"Mauve: multiple alignment of conserved genomic sequence with rearrangement","volume":"14","author":"Darling","year":"2004","journal-title":"Genome Res."},{"key":"2023051309020204400_btu815-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":"2023051309020204400_btu815-B8","volume-title":"Inferring Phylogenies","author":"Felsenstein","year":"2004"},{"key":"2023051309020204400_btu815-B9","article-title":"PHYLIP (phylogeny interference package) version 3.6","author":"Felsenstein","year":"2005"},{"key":"2023051309020204400_btu815-B10","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1007\/978-3-540-74450-4_41","article-title":"A new succinct representation of rmq-information and improvements in the enhanced suffix array","volume":"4614","author":"Fischer","year":"2007","journal-title":"Lect. Notes Comput. Sc."},{"key":"2023051309020204400_btu815-B11","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1093\/bib\/bbt083","article-title":"Alignment-free phylogenetics and population genetics","volume":"15","author":"Haubold","year":"2014","journal-title":"Brief. Bioinform."},{"key":"2023051309020204400_btu815-B12","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":"2023051309020204400_btu815-B13","doi-asserted-by":"crossref","first-page":"3121","DOI":"10.1093\/bioinformatics\/btt550","article-title":"An alignment-free test for recombination","volume":"29","author":"Haubold","year":"2013","journal-title":"Bioinformatics"},{"key":"2023051309020204400_btu815-B14","doi-asserted-by":"crossref","first-page":"2971","DOI":"10.1093\/bioinformatics\/btl505","article-title":"TimeTree: a public knowledge-base of divergence times among organisms","volume":"22","author":"Hedges","year":"2006","journal-title":"Bioinformatics"},{"key":"2023051309020204400_btu815-B15","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/B978-1-4832-3211-9.50009-7","article-title":"Evolution of protein molecules","volume-title":"Mammalian Protein Metabolism","author":"Jukes","year":"1969"},{"key":"2023051309020204400_btu815-B16","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":"2023051309020204400_btu815-B17","doi-asserted-by":"crossref","first-page":"2000","DOI":"10.1093\/bioinformatics\/btu331","article-title":"kmacs: the k-mismatch average common substring approach to alignment-free sequence comparison","volume":"30","author":"Leimeister","year":"2014","journal-title":"Bioinformatics"},{"key":"2023051309020204400_btu815-B18","volume-title":"Molecular Evolution","author":"Li","year":"1997"},{"key":"2023051309020204400_btu815-B19","volume-title":"Bioinformatics Algorithms","author":"Ohlebusch","year":"2013"},{"key":"2023051309020204400_btu815-B20","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1016\/0300-9084(96)84768-7","article-title":"WWW-Query: an on-line retrieval system for biological sequence banks","volume":"78","author":"Perri\u00e8re","year":"1996","journal-title":"Biochimie"},{"key":"2023051309020204400_btu815-B21","doi-asserted-by":"crossref","DOI":"10.1073\/pnas.1322678111","article-title":"Global dissemination of a multidrug resistant Escherichia coli clone","volume-title":"Proceedings of the National Academy of Sciences","author":"Petty","year":"2014"},{"key":"2023051309020204400_btu815-B22","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1016\/0025-5564(81)90043-2","article-title":"Comparison of phylogenetic trees","volume":"53","author":"Robinson","year":"1981","journal-title":"Math. Biosci."},{"key":"2023051309020204400_btu815-B23","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":"2023051309020204400_btu815-B24","doi-asserted-by":"crossref","first-page":"1421","DOI":"10.1137\/110845045","article-title":"Fixed-parameter algorithms for maximum agreement forests","volume":"42","author":"Whidden","year":"2013","journal-title":"SIAM J. Comput."},{"key":"2023051309020204400_btu815-B25","doi-asserted-by":"crossref","first-page":"e75","DOI":"10.1093\/nar\/gkt003","article-title":"Co-phylog: an assembly-free phylogenomic approach for closely related organisms","volume":"41","author":"Yi","year":"2013","journal-title":"Nucleic Acids Res."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/8\/1169\/50306168\/bioinformatics_31_8_1169.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/8\/1169\/50306168\/bioinformatics_31_8_1169.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T09:02:30Z","timestamp":1683968550000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/31\/8\/1169\/212918"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,10]]},"references-count":25,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2015,4,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btu815","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2015,4,15]]},"published":{"date-parts":[[2014,12,10]]}}}