The Average Common Substring Approach to Phylogenomic Reconstruction
- 1 March 2006
- journal article
- research article
- Published by Mary Ann Liebert Inc in Journal of Computational Biology
- Vol. 13 (2) , 336-350
- https://doi.org/10.1089/cmb.2006.13.336
Abstract
We describe a novel method for efficient reconstruction of phylogenetic trees, based on sequences of whole genomes or proteomes, whose lengths may greatly vary. The core of our method is a new measure of pairwise distances between sequences. This measure is based on computing the average lengths of maximum common substrings, which is intrinsically related to information theoretic tools (Kullback–Leibler relative entropy). We present an algorithm for efficiently computing these distances. In principle, the distance of two l long sequences can be calculated in O(l) time. We implemented the algorithm using suffix arrays our implementation is fast enough to enable the construction of the proteome phylogenomic tree for hundreds of species and the genome phylogenomic forest for almost two thousand viruses. An initial analysis of the results exhibits a remarkable agreement with "acceptable phylogenetic and taxonomic truth." To assess our approach, our results were compared to the traditional (single-gene or protein-based) maximum likelihood method. The obtained trees were compared to implementations of a number of alternative approaches, including two that were previously published in the literature, and to the published results of a third approach. Comparing their outcome and running time to ours, using a "traditional" trees and a standard tree comparison method, our algorithm improved upon the "competition" by a substantial margin. The simplicity and speed of our method allows for a whole genome analysis with the greatest scope attempted so far. We describe here five different applications of the method, which not only show the validity of the method, but also suggest a number of novel phylogenetic insights.Keywords
This publication has 23 references indexed in Scilit:
- Complete Genome Sequence of Fer-de-Lance Virus Reveals a Novel Gene in Reptilian ParamyxovirusesJournal of Virology, 2004
- New insights into the evolutionary relationships between arenaviruses provided by comparative analysis of small and large segment sequencesVirology, 2003
- Molecular and Enzymatic Characterization of the Porcine Endogenous Retrovirus ProteaseJournal of Virology, 2002
- In silico identification, structure prediction and phylogenetic analysis of the 2′-O-ribose (cap 1) methyltransferase domain in the large structural protein of ssRNA negative-strand virusesProtein Engineering, Design and Selection, 2002
- An information-based sequence distance and its application to whole mitochondrial genome phylogenyBioinformatics, 2001
- Constructing Phylogenies from Quartets: Elucidation of Eutherian Superordinal RelationshipsJournal of Computational Biology, 1998
- The Phylogeny of New World (Tacaribe Complex) ArenavirusesVirology, 1996
- Molecular biology and evolution of filovirusesPublished by Springer Nature ,1993
- A universal algorithm for sequential data compressionIEEE Transactions on Information Theory, 1977
- On the Complexity of Finite SequencesIEEE Transactions on Information Theory, 1976