Published online 22 February 2008 Nucleic Acids Research, 2008, Vol. 36, No. 5 e33 doi:10.1093/nar/gkn075 Performance comparison between k-tuple distance and four model-based distances in phylogenetic tree reconstruction Kuan Yang1,2 and Liqing Zhang2,3,* 1Virginia Bioinformatics Institute, 2Department of Computer Sciences and 3Program in Genetics, Bioinformatics and Computational Biology, Virginia Tech, Virginia, USA Received October 7, 2007; Revised February 4, 2008; Accepted February 7, 2008 ABSTRACT Phylogenetic tree reconstruction requires construc- tion 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 construc- tion. 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 substitu- tion 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 diver- gence 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 tremen- dous amount of time for phylogenetic tree recon- structions when the data include a large number of sequences. INTRODUCTION A phylogenetic tree is a graphical representation of the genetic closeness among diﬀerent species or biological entities. Despite other representation forms, such as phylogenetic networks (1), trees are still the most popular and standard representation of species’ evolutionary relationships. Many diﬀerent criteria can be used to build a tree for a set of DNA sequences, such as maximum parsimony, minimum evolution, neighbor-joining (NJ), maximum likelihood and Bayesian inference. Among these methods, NJ is the most frequently used due to its high speed and comparable accuracy. Many modiﬁed versions of NJ algorithms (2) have been introduced since its introduction, such as bioNJ (3) and Weighbor (4). The current paradigm in phylogenetic tree reconstruc- tion is to start from a set of sequences, build multiple sequence alignment (MSA), and then based on the MSA, build a tree using one or several methods mentioned earlier. Therefore, clearly, all methods of phylogenetic tree reconstruction share the same starting point: computation of an MSA from the given set of DNA sequences. MSA refers to the arrangement of a set of sequences so that it reﬂects the evolutionary history of these sequences. Computationally, it is represented by a matrix, in which a row of the matrix represents one of the sequences in the set of sequences and a column represents speciﬁc positions along all the sequences and reﬂects matches, mismatches or gaps in all sequences. Therefore, once an MSA is constructed, an evolutionary hypothesis is automatically *To whom correspondence should be addressed. Tel: +1 540 231 9413; Fax: +1 540 231 6075; Email: lqzhang@vt.edu 2008 The Author(s) This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/ by-nc/2.0/uk/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.