{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T09:35:40Z","timestamp":1769765740401,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T00:00:00Z","timestamp":1586217600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T00:00:00Z","timestamp":1586217600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Background<\/jats:title><jats:p>The increasing amount of available genome sequence data enables large-scale comparative studies. A common task is the inference of phylogenies\u2014a challenging task if close reference sequences are not available, genome sequences are incompletely assembled, or the high number of genomes precludes multiple sequence alignment in reasonable time.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>We present a new whole-genome based approach to infer phylogenies that is alignment- and reference-free. In contrast to other methods, it does not rely on pairwise comparisons to determine distances to infer edges in a tree. Instead, a colored de\u00a0Bruijn graph is constructed, and information on common subsequences is extracted to infer phylogenetic splits.<\/jats:p><\/jats:sec><jats:sec><jats:title>Conclusions<\/jats:title><jats:p>The introduced new methodology for large-scale phylogenomics shows high potential. Application to different datasets confirms robustness of the approach. A comparison to other state-of-the-art whole-genome based methods indicates comparable or higher accuracy and efficiency.<\/jats:p><\/jats:sec>","DOI":"10.1186\/s13015-020-00164-3","type":"journal-article","created":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T10:02:35Z","timestamp":1586253755000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Alignment- and reference-free phylogenomics with colored de Bruijn graphs"],"prefix":"10.1186","volume":"15","author":[{"given":"Roland","family":"Wittler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,4,7]]},"reference":[{"issue":"1","key":"164_CR1","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1186\/s12864-015-1647-5","volume":"16","author":"H Fan","year":"2015","unstructured":"Fan H, Ives AR, Surget-Groba Y, Cannon CH. An assembly and alignment-free method of phylogeny reconstruction from next-generation sequencing data. BMC Genomics. 2015;16(1):522.","journal-title":"BMC Genomics"},{"issue":"8","key":"164_CR2","doi-asserted-by":"publisher","first-page":"1169","DOI":"10.1093\/bioinformatics\/btu815","volume":"31","author":"B Haubold","year":"2014","unstructured":"Haubold B, Kl\u00f6tzl F, Pfaelhuber P. andi: Fast and accurate estimation of evolutionary distances between closely related genomes. Bioinformatics. 2014;31(8):1169\u201375.","journal-title":"Bioinformatics"},{"issue":"7","key":"164_CR3","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1093\/bioinformatics\/btw776","volume":"33","author":"C-A Leimeister","year":"2017","unstructured":"Leimeister C-A, Sohrabi-Jahromi S, Morgenstern B. Fast and accurate phylogeny reconstruction using filtered spaced-word matches. Bioinformatics. 2017;33(7):971\u20139.","journal-title":"Bioinformatics"},{"issue":"7","key":"164_CR4","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1093\/nar\/gkt003","volume":"41","author":"H Yi","year":"2013","unstructured":"Yi H, Jin L. Co-phylog: an assembly-free phylogenomic approach for closely related organisms. Nucleic Acids Res. 2013;41(7):75.","journal-title":"Nucleic Acids Res"},{"key":"164_CR5","doi-asserted-by":"publisher","first-page":"117693431875929","DOI":"10.1177\/1176934318759299","volume":"14","author":"X Yu","year":"2018","unstructured":"Yu X, Reva ON. SWPhylo\u2013a novel tool for phylogenomic inferences by comparison of oligonucleotide patterns and integration of genome-based and gene-based phylogenetic trees. Evol Bioinf. 2018;14:1176934318759299.","journal-title":"Evol Bioinf"},{"issue":"5","key":"164_CR6","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/j.gpb.2015.08.004","volume":"13","author":"G Zuo","year":"2015","unstructured":"Zuo G, Hao B. CVTree3 web server for whole-genome-based and alignment-free prokaryotic phylogeny and taxonomy. Genom Proteom Bioinf. 2015;13(5):321\u201331.","journal-title":"Genom Proteom Bioinf"},{"issue":"4","key":"164_CR7","first-page":"406","volume":"4","author":"N Saitou","year":"1987","unstructured":"Saitou N, Nei M. The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol Biol Evol. 1987;4(4):406\u201325.","journal-title":"Mol Biol Evol"},{"key":"164_CR8","first-page":"013","volume":"2","author":"T Dencker","year":"2020","unstructured":"Dencker T, Leimeister C-A, Gerth M, Bleidorn C, Snir S, Morgenstern B. Multi-SpaM: a maximum-likelihood approach to phylogeny reconstruction using multiple spaced-word matches and quartet trees. NAR Genom Bioinf. 2020;2:013.","journal-title":"NAR Genom Bioinf"},{"key":"164_CR9","unstructured":"Wittler R. https:\/\/gitlab.ub.uni-bielefeld.de\/gi\/sans"},{"issue":"1","key":"164_CR10","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0001-8708(92)90061-O","volume":"92","author":"H-J Bandelt","year":"1992","unstructured":"Bandelt H-J, Dress AW. A canonical decomposition theory for metrics on a finite set. Adv Math. 1992;92(1):47\u2013105.","journal-title":"Adv Math"},{"key":"164_CR11","unstructured":"Wittler R. Alignment- and reference-free phylogenomics with colored de Bruijn graphs. In: Huber, K.T., Gusfield, D. (eds.) 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany. 2019; vol. 143: pp. 2\u20131214."},{"issue":"2","key":"164_CR12","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1038\/ng.1028","volume":"44","author":"Z Iqbal","year":"2012","unstructured":"Iqbal Z, Caccamo M, Turner I, Flicek P, McVean G. De novo assembly and genotyping of variants using colored de Bruijn graphs. Nat Genet. 2012;44(2):226.","journal-title":"Nat Genet"},{"key":"164_CR13","doi-asserted-by":"crossref","unstructured":"Almodaresi F, Pandey P, Patro R. Rainbowfish: a succinct colored de Bruijn graph representation. In: Schwartz, R., Reinert, K. (eds.) 17th International Workshop on Algorithms in Bioinformatics (WABI 2017). Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany. 2017; vol. 88:pp. 18\u201311815.","DOI":"10.1101\/138016"},{"issue":"1","key":"164_CR14","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1186\/s13015-016-0066-8","volume":"11","author":"G Holley","year":"2016","unstructured":"Holley G, Wittler R, Stoye J. Bloom filter trie: an alignment-free and reference-free data structure for pan-genome storage. Algorith Mol Biol. 2016;11(1):3.","journal-title":"Algorith Mol Biol"},{"issue":"20","key":"164_CR15","doi-asserted-by":"publisher","first-page":"3181","DOI":"10.1093\/bioinformatics\/btx067","volume":"33","author":"MD Muggli","year":"2017","unstructured":"Muggli MD, Bowe A, Noyes NR, Morley PS, Belk KE, Raymond R, Gagie T, Puglisi SJ, Boucher C. Succinct colored de Bruijn graphs. Bioinformatics. 2017;33(20):3181\u20137.","journal-title":"Bioinformatics"},{"key":"164_CR16","first-page":"338","volume":"695","author":"G Holley","year":"2019","unstructured":"Holley G, Melsted P. Bifrost-Highly parallel construction and indexing of colored and compacted de Bruijn graphs. BioRxiv. 2019;695:338.","journal-title":"BioRxiv"},{"key":"164_CR17","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1093\/bioinformatics\/14.1.68","volume":"14","author":"DH Huson","year":"2008","unstructured":"Huson DH, Kloepper T, Bryant D. SplitsTree 4.0-computation of phylogenetic trees and networks. Bioinformatics. 2008;14:68\u201373.","journal-title":"Bioinformatics"},{"issue":"1","key":"164_CR18","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1186\/1471-2148-8-22","volume":"8","author":"TH Kloepper","year":"2008","unstructured":"Kloepper TH, Huson DH. Drawing explicit phylogenetic networks and their integration into SplitsTree. BMC Evol Biol. 2008;8(1):22.","journal-title":"BMC Evol Biol"},{"issue":"D1","key":"164_CR19","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1093\/nar\/gky1003","volume":"47","author":"J Thurmond","year":"2018","unstructured":"Thurmond J, Goodman JL, Strelets VB, Attrill H, Gramates L, Marygold SJ, Matthews BB, Millburn G, Antonazzo G, Trovisco V, Kaufman TC, Calvi BR. the FlyBase Consortium: FlyBase 2.0: the next generation. Nucleic Acids Res. 2018;47(D1):759\u201365.","journal-title":"Nucleic Acids Res"},{"issue":"suppl 1","key":"164_CR20","first-page":"486","volume":"35","author":"MA Crosby","year":"2006","unstructured":"Crosby MA, Goodman JL, Strelets VB, Zhang P, Gelbart WM. the FlyBase Consortium: FlyBase: genomes by the dozen. Nucleic Acids Res. 2006;35(suppl 1):486\u201391.","journal-title":"Nucleic Acids Res"},{"issue":"4","key":"164_CR21","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/s00438-009-0468-0","volume":"282","author":"NM Vidal","year":"2009","unstructured":"Vidal NM, Ludwig A, Loreto ELS. Evolution of Tom, 297, 176 and rover retrotransposons in Drosophilidae species. Mol Genet Genom. 2009;282(4):351\u201362.","journal-title":"Mol Genet Genom"},{"issue":"9","key":"164_CR22","doi-asserted-by":"publisher","first-page":"1395","DOI":"10.1101\/gr.232397.117","volume":"28","author":"Z Zhou","year":"2018","unstructured":"Zhou Z, Alikhan N-F, Sergeant MJ, Luhmann N, Vaz C, Francisco AP, Carri\u00e7o JA, Achtman M. GrapeTree: visualization of core genomic relationships among 100,000 bacterial pathogens. Genome Res. 2018;28(9):1395\u2013404.","journal-title":"Genome Res"},{"issue":"4","key":"164_CR23","doi-asserted-by":"publisher","first-page":"1007261","DOI":"10.1371\/journal.pgen.1007261","volume":"14","author":"N-F Alikhan","year":"2018","unstructured":"Alikhan N-F, Zhou Z, Sergeant MJ, Achtman M. A genomic overview of the population structure of Salmonella. PLoS Genet. 2018;14(4):1007261.","journal-title":"PLoS Genet"},{"issue":"15","key":"164_CR24","doi-asserted-by":"publisher","first-page":"2420","DOI":"10.1016\/j.cub.2018.05.058","volume":"28","author":"Z Zhou","year":"2018","unstructured":"Zhou Z, Lundstrm I, Tran-Dien A, Duch\u00eane S, Alikhan N-F, Sergeant MJ, Langridge G, Fotakis AK, Nair S, Sten\u00f8ien HK, Hamre SS, Casjens S, Christophersen A, Quince C, Thomson NR, Weill F-X, Ho SYW, Gilbert MTP, Achtman M. Pan-genome analysis of ancient and modern Salmonella enterica demonstrates genomic stability of the invasive Para C lineage for millennia. Curr Biol. 2018;28(15):2420\u20138.","journal-title":"Curr Biol"},{"key":"164_CR25","first-page":"6","volume":"2014","author":"M Haeussler","year":"2014","unstructured":"Haeussler M, Karolchik D, Clawson H, Raney BJ, Rosenbloom KR, Fujita PA, Hinrichs AS, Speir ML, Eisenhart C, Zweig AS, et al. The UCSC Ebola genome portal. PLoS Curr. 2014;2014:6.","journal-title":"PLoS Curr"},{"issue":"3","key":"164_CR26","doi-asserted-by":"publisher","first-page":"16240","DOI":"10.1038\/nmicrobiol.2016.240","volume":"2","author":"BJ Shapiro","year":"2017","unstructured":"Shapiro BJ, Levade I, Kovacikova G, Taylor RK, Almagro-Moreno S. Origins of pandemic Vibrio cholerae from environmental gene pools. Nat Microbiol. 2017;2(3):16240.","journal-title":"Nat Microbiol"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-020-00164-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s13015-020-00164-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-020-00164-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T16:44:23Z","timestamp":1696005863000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-020-00164-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,7]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["164"],"URL":"https:\/\/doi.org\/10.1186\/s13015-020-00164-3","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,7]]},"assertion":[{"value":"15 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 March 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 April 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The author declare that there are no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"4"}}