Nucleic Acids Research Advance Access published online on February 22, 2008
Nucleic Acids Research, doi:10.1093/nar/gkn075
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Methods Online |
Performance comparison between k-tuple distance and four model-based distances in phylogenetic tree reconstruction
1Virginia Bioinformatics Institute, 2Department of Computer Sciences and 3Program in Genetics, Bioinformatics and Computational Biology, Virginia Tech, Virginia, USA
*To whom correspondence should be addressed. Tel: +1 540 231 9413; Fax: +1 540 231 6075; Email: lqzhang{at}vt.edu
Received October 7, 2007. Revised February 4, 2008. Accepted February 7, 2008.
Phylogenetic tree reconstruction requires construction of a multiple sequence alignment (MSA) from sequences. Computationally, it is difficult to achieve an optimal MSA for many sequences. Moreover, even if an optimal MSA is obtained, it may not be the true MSA that reflects the evolutionary history of the underlying sequences. Therefore, errors can be introduced during MSA construction which in turn affects the subsequent phylogenetic tree construction. In order to circumvent this issue, we extend the application of the k-tuple distance to phylogenetic tree reconstruction. The k-tuple distance between two sequences is the sum of the differences in frequency, over all possible tuples of length k, between the sequences and can be estimated without MSAs. It has been traditionally used to build a fast ‘guide tree’ to assist the construction of MSAs. Using the 1470 simulated sets of sequences generated under different evolutionary scenarios, the neighbor-joining trees and BioNJ trees, we compared the performance of the k-tuple distance with four commonly used distance estimators including Jukes–Cantor, Kimura, F84 and Tamura–Nei. These four distance estimators fall into the category of model-based distance estimators, as each of them takes account of a specific substitution model in order to compute the distance between a pair of already aligned sequences. Results show that trees constructed from the k-tuple distance are more accurate than those from other distances most time; when the divergence between underlying sequences is high, the tree accuracy could be twice or higher using the k-tuple distance than other estimators. Furthermore, as the k-tuple distance voids the need for constructing an MSA, it can save tremendous amount of time for phylogenetic tree reconstructions when the data include a large number of sequences.