e33 Nucleic Acids Research, 2008, Vol. 36, No. 5 generated and represented by the alignment. The quality of an MSA thus directly aﬀects the accuracy of subsequent phylogenetic inference, and erroneous MSA can lead to low-quality phylogenetic trees that give misleading information and false inference of evolutionary histories. Therefore MSA has been an extremely active research topic. More than 50 multiple sequence alignment methods and/or packages have been described over the past 10 years (5) and there were at least 20 new publications in 2005 alone (6). Among many MSA programs, ClustalW (7) is one of the most popular and standard programs. It made its way to daily usage by its friendly interface, stability and accuracy. However, as a result of its high consumption of time, it becomes impractical to use when the number of sequences that need to be aligned becomes large and/or the lengths of sequences reach a certain level. Subsequently, other programs have been introduced such as T-Coﬀee (8), MAFFT (9) and MUSCLE (10). Comparatively, the relatively new MUSCLE has the highest accuracy among existing programs and the short- est running time, according to the original paper (10). However, despite the essential role of MSA in the entire process of phylogenetic tree reconstruction and multiple eﬀorts to improve MSA methods, there remain several issues. First, ﬁnding the optimal MSA under a set of scoring schemes for a large number of sequences is computationally impossible. Most algorithms currently available are heuristic, which leads to an approximate solution. Even with heuristic methods, aligning a large number of sequences can be time consuming. Second, the quality of an MSA is extremely sensitive to the choices of the scoring parameters used in producing the alignment, such as penalty scores of gap opening and gap extension. Diﬀerent scoring schemes can produce drastically diﬀerent MSAs, which in turn can lead to diﬀerent phylogenetic trees. Unfortunately, in most cases, the true MSA that reﬂects the evolutionary history of the underlying set of sequences is unknown. Thus the users have to either choose to trust the default scoring schemes or use their own judgment in choosing a scoring scheme. Third, the quality of an MSA is sensitive to sequence length diﬀerence and the degree of sequence identity. A set of sequences with dramatically diﬀerent lengths can adversely inﬂuence the quality of an MSA. Similarly, if the sequences in the set are highly diverged from one another, the quality of an MSA is most likely low. Because the construction of an MSA can introduce errors and adversely inﬂuence the accuracy of subsequent phylogenetic inference and because it is time consuming to construct an MSA for a large number of sequences, we formally introduce the application of the k-tuple distance (aka k-mer distance) in the phylogenetic tree reconstruc- tion. The k-tuple distance refers to the total of the diﬀerences, over all possible k-tuples, between the sequences, for any given length k. The idea of using the k-tuple distance to construct a tree is not new and the procedure is in fact embedded in many MSA programs such as ClustalW (7), Kalign (11) and MUSCLE (10). To construct an MSA, these programs ﬁrst compute a pairwise k-tuple distance matrix for the sequences to be aligned, use UPGMA or NJ methods to quickly build PAGE 2 OF 9 a ‘guide tree’, and use the guide tree to determine the order in which sequences or proﬁles are aligned. However, despite the common use of k-tuple distance in generating ‘guide trees’, guide trees are rarely used by evolutionary biologists as the ﬁnal phylogenetic trees, and instead, packages dedicated to tree building such as PHYLIP (12) and PAUP (13) will be used to produce the ﬁnal trees. To our knowledge, the value of the k-tuple distance in constructing a ‘real’ phylogenetic tree (instead of a ‘guide tree’ for sequence alignment) has not been formally discussed before, nor has the accuracy of the resulting phylogenetic tree. As the k-tuple distance can be calculated without sequence alignment and its computa- tion for even a large number of sequences takes only seconds, k-tuple distance can be extremely useful when we are faced with the overwhelming number of sequences that require phylogenetic information and may essentially be the only option in cases where there are sequences that are too diverged to be reasonably aligned in the post-genomic era. But an important prerequisite for the broad applica- tion of k-tuple distance in phylogenetic tree reconstruction is that the trees built from the k-tuple distance have comparable accuracy to the trees built from traditional alignment-based methods. In order to address the issue, we compared the k-tuple distance performance and accuracy in producing the correct NJ and BioNJ trees with four other commonly used distance estimators. The four distance estimators are model-based, in other words, they are computed based on certain substitution models for DNA sequence evolution. Our results show that when k equals ﬁve, the k-tuple distance outperformed other distance estimators most of the time and it could be twice, or more, the accuracy of other distance estimators. Moreover, compared to the existing alignment-dependent distance estimators, the k-tuple distance is fast and easy to compute and can save the tremendous amount of running time that is required for constructing MSAs. Taken together, our results show that the application of k-tuple distance in phylogenetic tree reconstruction is very promising. MATERIALS AND METHODS Simulation of five sequence datasets We used DAWG (14) to simulate sequences. DAWG is a program that simulates the evolution of sequences based on a given phylogenetic tree, incorporating both nucleo- tide substitutions and insertions and deletions. It can simulate nucleotide substitutions with diﬀerent substitu- tion models and indel formation with a power law distribution of indel sizes. Therefore, it seems a rather good approximation of real sequence evolution. We simulated ﬁve diﬀerent datasets of sequences using the HKY substitution model (15), as summarized in Table 1, in order to accommodate the diﬀerent situations that we might encounter in real-world phylogenetic tree recon- struction. The ﬁrst dataset is generated to consider the situation of alignment of regulatory regions or short intronic sequences and reconstruction of phylogenetic trees based on the alignment. Compared with coding