e33 Nucleic Acids Research, 2008, Vol. 36, No. 5 PAGE 8 OF 9 Figure 8. Accuracy comparison for dataset 7 with indel versus substitution rate ratio of 10. performance of k-tuple distance, although the impact seems small. As simulation cannot capture all the complexities of real sequence evolution, it will be useful to perform some analyses on real data. However, real sequences with ‘real’ trees are not usually available. But it is still useful to examine how consistent k-tuple distance performs in building phylogenetic trees with the alignment-based distances and also how robust the k-tuple distance is as compared to the bootstrapped alignment-based trees. Bootstrapping is a common way to determine the quality and conﬁdence of a reconstructed phylogenetic tree. It is usually done by re-sampling the sequences with replace- ment, repeating the tree-reconstruction processes for a certain number of times, and obtaining bootstrap values as the percentage times that certain bifurcation is supported by the reconstructed trees. Thus, bootstrapping gives conﬁdence estimate of certain groupings in a phylogenetic tree. One would expect that highly supported phylogenetic groupings (i.e. having high bootstrap values) can be recovered by the trees produced by the k-tuple distance. To address these issues, we manually picked 10 genes from the TreeFam database to study whether the k-tuple distance can produce trees that agree with the alignment-based methods and whether the k-tuple trees can recover the highly supported phylogenetic groupings in the bootstrapped trees. We visually inspected all the k-tuple trees and alignment-based trees, and found that about 76% of the bifurcations that have bootstrapping values higher than 75% were recovered also by the k-tuple trees, whereas only 25% of the bifurcations that have bootstrap values lower than 30% were recovered. This indicates that the k-tuple trees have little diﬃculty in recovering the phylogenetic groupings that have high bootstrap conﬁdence in the alignment-based trees, but for the phylogenetic groupings with low conﬁdence in the alignment-based trees, k-tuple methods may also produce ambiguous grouping, similar to what happens to the alignment-based methods. Broadly, the k-tuple distance falls into the category of alignment-free sequence comparison metrics. Except the k-tuple distance used in this study, there are other more elaborated ones that are also based on tuple frequencies, such as the Mahalanobis distance and Weighted Enclidean distance (31). Some of these alignment-free distance measurements have been previously explored in the application of searching DNA and protein databases. Though there is no evidence yet that any of these are preferable to simple k-tuple distance, this is a likely question for further research. Compared to the most popular ClustalW program, MUSCLE gives accurate alignments faster. ClustalW becomes impractical when the lengths and number of sequences increase to certain extent. However, even though MUSCLE is faster than ClustalW, it on average still takes 30–40 min to align 250 sequences of around 1300 bp. In contrast, it takes only seconds to calculate the k-tuple distance matrix. Therefore, the advantage of the k-tuple distance over existing distance estimators in distance-based phylogenetic tree reconstruction is not only its accuracy, but also its computational speed: it is at least hundreds of times, if not thousands, faster than any other distance estimators that require an MSA to calculate distances between sequences. It can be very useful in constructing phylogenetic trees for a large number of sequences, for example, in the case of building the ‘tree of life’ (32,33). ACKNOWLEDGEMENTS We thank the two anonymous reviewers for their helpful comments. This work is supported in part by NSF grant IIS-0710945 and AdvanceVT at Virginia Tech. Funding to pay the Open Access publication charges for this article was provided by NSF grant IIS-0710945. Conﬂict of interest statement. None declared. REFERENCES 1. Jin,G., Nakhleh,L., Snir,S. and Tuller,T. (2007) Eﬃcient parsimony- based methods for phylogenetic network reconstruction. Bioinformatics, 23, e123–e128. 2. Saitou,N. and Nei,M. (1987) The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol. Biol. Evol., 4, 406–425. 3. Gascuel,O. (1997) BIONJ: an improved version of the NJ algorithm based on a simple model of sequence data. Mol. Biol. Evol., 14, 685–695. 4. Bruno,W.J., Socci,N.D. and Halpern,A.L. (2000) Weighted neighbor joining: a likelihood-based approach to distance-based phylogeny reconstruction. Mol. Biol. Evol., 17, 189–197. 5. Blackshields,G., Wallace,I.M., Larkin,M. and Higgins,D.G. (2006) Analysis and comparison of benchmarks for multiple sequence alignment. In Silico Biol., 6, 321–339. 6. Wallance,I.M., O’Sullivan,O., Higgins,D.G. and Notredame,C. (2006) M-Coﬀee: combining multiple sequence alignment methods with T-Coﬀee. Nucleic Acids Res., 34, 7. 7. Chenna,R., Sugawara,H., Koike,T., Lopez,R., Gibson,T.J., Higgins,D.G. and Thompson,J.D. (2003) Multiple sequence alignment with the Clustal series of programs. Nucleic Acids Res., 31, 4.