Alignment- and reference-free phylogenomics with colored de Bruijn graphs

Springer Science and Business Media LLC - Tập 15 Số 1 - 2020
Roland Wittler1
1Genome Informatics, Faculty of Technology, Bielefeld University, Bielefeld, Germany

Tóm tắt

AbstractBackgroundThe increasing amount of available genome sequence data enables large-scale comparative studies. A common task is the inference of phylogenies—a 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.ResultsWe 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 Bruijn graph is constructed, and information on common subsequences is extracted to infer phylogenetic splits.ConclusionsThe 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.

Từ khóa


Tài liệu tham khảo

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.

Haubold B, Klötzl F, Pfaelhuber P. andi: Fast and accurate estimation of evolutionary distances between closely related genomes. Bioinformatics. 2014;31(8):1169–75.

Leimeister C-A, Sohrabi-Jahromi S, Morgenstern B. Fast and accurate phylogeny reconstruction using filtered spaced-word matches. Bioinformatics. 2017;33(7):971–9.

Yi H, Jin L. Co-phylog: an assembly-free phylogenomic approach for closely related organisms. Nucleic Acids Res. 2013;41(7):75.

Yu X, Reva ON. SWPhylo–a 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.

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–31.

Saitou N, Nei M. The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol Biol Evol. 1987;4(4):406–25.

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.

Wittler R. https://gitlab.ub.uni-bielefeld.de/gi/sans

Bandelt H-J, Dress AW. A canonical decomposition theory for metrics on a finite set. Adv Math. 1992;92(1):47–105.

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–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany. 2019; vol. 143: pp. 2–1214.

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.

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–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany. 2017; vol. 88:pp. 18–11815.

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.

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–7.

Holley G, Melsted P. Bifrost-Highly parallel construction and indexing of colored and compacted de Bruijn graphs. BioRxiv. 2019;695:338.

Huson DH, Kloepper T, Bryant D. SplitsTree 4.0-computation of phylogenetic trees and networks. Bioinformatics. 2008;14:68–73.

Kloepper TH, Huson DH. Drawing explicit phylogenetic networks and their integration into SplitsTree. BMC Evol Biol. 2008;8(1):22.

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–65.

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–91.

Vidal NM, Ludwig A, Loreto ELS. Evolution of Tom, 297, 176 and rover retrotransposons in Drosophilidae species. Mol Genet Genom. 2009;282(4):351–62.

Zhou Z, Alikhan N-F, Sergeant MJ, Luhmann N, Vaz C, Francisco AP, Carriço JA, Achtman M. GrapeTree: visualization of core genomic relationships among 100,000 bacterial pathogens. Genome Res. 2018;28(9):1395–404.

Alikhan N-F, Zhou Z, Sergeant MJ, Achtman M. A genomic overview of the population structure of Salmonella. PLoS Genet. 2018;14(4):1007261.

Zhou Z, Lundstrm I, Tran-Dien A, Duchêne S, Alikhan N-F, Sergeant MJ, Langridge G, Fotakis AK, Nair S, Stenøien 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–8.

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.

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.

Thông tin
Thông tin xuất bản

Springer Science and Business Media LLC

Tập 15 Số 1

Thông tin tác giả