Alignment-free inference of hierarchical and reticulate phylogenomic relationships

被引:58
作者
Bernard, Guillaume [2 ]
Chan, Cheong Xin [3 ]
Chan, Yao-ban [4 ]
Chua, Xin-Yi [5 ]
Cong, Yingnan [1 ]
Hogan, James M. [6 ]
Maetschke, Stefan R. [7 ]
Ragan, Mark A. [8 ]
机构
[1] Univ Queensland, Inst Mol Biosci, 306 Carmody Rd, Brisbane, Qld 4072, Australia
[2] Inst Mol Biosci, Brisbane, Qld, Australia
[3] Univ Queensland, Brisbane, Qld, Australia
[4] Univ Melbourne, Melbourne, Vic, Australia
[5] QFAB Bioinformat, Melbourne, Vic, Australia
[6] Queensland Univ Technol, Comp Sci, Brisbane, Qld, Australia
[7] IBM Res Australia, Brisbane, Qld, Australia
[8] Inst Mol Biosci, Computat Gen, Brisbane, Qld, Australia
基金
澳大利亚研究理事会;
关键词
alignment-free; phylogenomics; lateral genetic transfer; k-mer; D2; statistics; TF-IDF; LATERAL GENETIC TRANSFER; FEATURE FREQUENCY PROFILES; MICROBIAL EVOLUTION; MAMMALIAN ENHANCERS; SEQUENCE ALIGNMENT; SURROGATE METHODS; WORD MATCHES; TREE; RECONSTRUCTION; SIMILARITY;
D O I
10.1093/bib/bbx067
中图分类号
Q5 [生物化学];
学科分类号
071010 ; 081704 ;
摘要
We are amidst an ongoing flood of sequence data arising from the application of high-throughput technologies, and a concomitant fundamental revision in our understanding of how genomes evolve individually and within the biosphere. Workflows for phylogenomic inference must accommodate data that are not only much larger than before, but often more error prone and perhaps misassembled, or not assembled in the first place. Moreover, genomes of microbes, viruses and plasmids evolve not only by tree-like descent with modification but also by incorporating stretches of exogenous DNA. Thus, next-generation phylogenomics must address computational scalability while rethinking the nature of orthogroups, the alignment of multiple sequences and the inference and comparison of trees. New phylogenomic workflows have begun to take shape based on so-called alignment-free (AF) approaches. Here, we review the conceptual foundations of AF phylogenetics for the hierarchical (vertical) and reticulate (lateral) components of genome evolution, focusing on methods based on k-mers. We reflect on what seems to be successful, and on where further development is needed.
引用
收藏
页码:426 / 435
页数:10
相关论文
共 113 条
[71]  
Lu Y, 2017, GRAPPA GRAPH ALGORIT
[72]  
Maetschke SR, 2017, LGTNET FAST INFERENC
[73]   A visual framework for sequence analysis using n-grams and spectral rearrangement [J].
Maetschke, Stefan R. ;
Kassahn, Karin S. ;
Dunn, Jasmyn A. ;
Han, Siew-Ping ;
Curley, Eva Z. ;
Stacey, Katryn J. ;
Ragan, Mark A. .
BIOINFORMATICS, 2010, 26 (06) :737-744
[74]   SUFFIX ARRAYS - A NEW METHOD FOR ONLINE STRING SEARCHES [J].
MANBER, U ;
MYERS, G .
SIAM JOURNAL ON COMPUTING, 1993, 22 (05) :935-948
[75]   A fast, lock-free approach for efficient parallel counting of occurrences of k-mers [J].
Marcais, Guillaume ;
Kingsford, Carl .
BIOINFORMATICS, 2011, 27 (06) :764-770
[76]   HOMOLOGY - A DEFINITION [J].
MARGOLIASH, E .
SCIENCE, 1969, 163 (3863) :127-+
[77]   On the Reconstruction of Text Phylogeny Trees: Evaluation and Analysis of Textual Relationships [J].
Marmerola, Guilherme D. ;
Oikawa, Marina A. ;
Dias, Zanoni ;
Goldenstein, Siome ;
Rocha, Anderson .
PLOS ONE, 2016, 11 (12)
[78]   EVIDENCE FOR HORIZONTAL GENE-TRANSFER IN ESCHERICHIA-COLI SPECIATION [J].
MEDIGUE, C ;
ROUXEL, T ;
VIGIER, P ;
HENAUT, A ;
DANCHIN, A .
JOURNAL OF MOLECULAR BIOLOGY, 1991, 222 (04) :851-856
[79]   Efficient counting of k-mers in DNA sequences using a bloom filter [J].
Melsted, Pall ;
Pritchard, Jonathan K. .
BMC BIOINFORMATICS, 2011, 12
[80]   Aggressive assembly of pyrosequencing reads with mates [J].
Miller, Jason R. ;
Delcher, Arthur L. ;
Koren, Sergey ;
Venter, Eli ;
Walenz, Brian P. ;
Brownley, Anushka ;
Johnson, Justin ;
Li, Kelvin ;
Mobarry, Clark ;
Sutton, Granger .
BIOINFORMATICS, 2008, 24 (24) :2818-2824