Abstract
We describe a novel method for efficient reconstruction of phylogenetic trees, based on sequences of whole genomes or proteomes. The core of our method is a new measure of pairwise distances between sequences, whose lengths may greatly vary. This measure is based on information theoretic tools (Kullback-Leibler relative entropy). We present an algorithm for efficiently computing these distances. The algorithm uses suffix arrays to compute the distance of two l long sequences in O(l) time. It is fast enough to enable the construction of the phylogenomic tree for hundreds of species, and the phylogenomic forest for almost two thousand viruses. An initial analysis of the results exhibits a remarkable agreement with "acceptable phylogenetic truth". To assess our approach, it was implemented together with a number of alternative approaches, including two that were previously published in the literature. Comparing their outcome to ours, using a "traditional" tree and a standard tree comparison method, our algorithm improved upon the "competition" by a substantial margin.
Original language | English |
---|---|
Pages (from-to) | 283-295 |
Number of pages | 13 |
Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
Volume | 3500 |
DOIs | |
State | Published - 2005 |
Externally published | Yes |
Event | 9th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2005 - Cambridge, MA, United States Duration: 14 May 2005 → 18 May 2005 |
Keywords
- Distance matrix
- Divergence
- Kullback-leibler relative entropy
- Phylogenomics
- Tree reconstruction
- Whole genome and proteom phylogenetic