PAGE 7 OF 9 Nucleic Acids Research, 2008, Vol. 36, No. 5 e33 gene family members might have been discarded from ﬁnal alignments and therefore not considered in the trees. Random trees with long branch lengths can be used to compensate for this limitation. When a set of sequences is highly diverged, the accuracy of the constructed phylogenetic trees is in general low regardless of the type of distance estimators used. Even though the k-tuple distance has the best performance in these cases, it is only about 30–40% accurate on average (e.g. Figures 1 and 3). F84, Jukes–Cantor and Kimura distances basically show performance similar to random clustering, especially when simulated samples contain >180 sequences (after sample #130 in Figures 1 and 3). The low performance of these distance estimators could be partially explained by the low accuracy of the MSAs. However, the fact that Tamura–Nei distances show a stronger accuracy and stability under such circumstances indicates that the simpler distance estimators, as com- pared to Tamura–Nei, is not a good ﬁt to the underlying sequences, which were generated under the HKY model, a special case of the Tamura–Nei model (25). The observation is consistent with previous studies showing that choosing the right nucleotide substitution models are essential for correct phylogenetic analyses (26,27). In fact, when using the distance-based phylogenetic tree recon- struction, it has been suggested that statistical tests should be performed in order to choose the right substitution model for the underlying sequence alignments to calculate the distance matrix (28). We also considered the evolution of DNA sequences without indels. As both insertion and deletion occur in DNA sequences, DNA sequences generated without indels are likely unrealistic, and this scenario may happen only to sequences that diverged from each other recently or to sequences that are under intensive purifying selection against indels. Due to the absence of indels in the sequences, under a suitable scoring scheme, an MSA can be constructed with few errors and little deviation from the true evolution of the sequences. An accurate MSA gives the most advantage to the alignment-dependent distance estimators. Therefore, this scenario can provide us the lower bound of the advantage of the k-tuple distance over other distance estimators. Our result shows that with similar sequences, the diﬀerence between diﬀerent methods diminishes and the diﬀerence of the stability for the underlying metrics also decreases, although the k-tuple distance still shows 50% more stability than the others (Figure 4). Clearly, alignment-based distances will have advantage over k-tuple distances in terms of tree accuracy in cases where k-tuple distances cannot reﬂect the degree of sequence divergence faithfully while alignment methods can. One of the extreme cases is when a set of sequences are almost identical, in which case, the k-tuple distance may have lower resolution than the more reﬁned model- based distances, because, for example, it cannot diﬀer- entiate transitions from transversions. However, a large number of highly identical sequences happens mostly in the studies of population genetics, in the majority of other cases, the large number of sequences that require phylogenetic tree reconstruction might have a wide Figure 7. Accuracy comparison for dataset 6 with indel versus substitution rate ratio of 1. range of sequence divergence, similar to what we observe in the dataset 2. Another extreme case is when rates of insertions and deletions are high and rates of point mutations are low. Conceivably, k-tuple distance could perform worse than alignment distance here. To formally investigate this, we simulated two more datasets using real trees and a diﬀerent indel/substitution rate ratio scheme: the ﬁrst dataset has a ratio of indel rates versus substitution rates of 1 and the second dataset has a ratio of indel rates versus substitution rates of 10 (Table 1). Previous studies show that the ratio of indel versus substitution rates is about 0.1 (29,30), and therefore, both the ratios of 1 and 10 are biologically unrealistic. Nevertheless, it is useful to see in these extreme cases the performance of the k-tuple distance as compared to that of other model-based distances. Results show that high rate ratios of indels versus substitutions harm the alignment- based methods more than k-tuple distance. While the average accuracy of the latter drops to from 0.53 (Figure 4) to 0.52 (Figure 2) to 0.41 and 0.17 (Figures 7 and 8) as the ratio increases from 0, 0.1, 1, to 10, respectively, the alignment based methods uniformly suﬀer a more catastrophic loss of performance. This result is a clear manifestation of the greater disruption by indels of alignment scores than of k-tuple distances. To understand the impact of GC bias on the performance of k-tuple distance, we used real trees from TreeFam and indel/substitution rates of 0.1 and generated 150 sets of sequences that have diﬀerent degrees of GC bias: 50 sets of sequences with strong GC bias (i.e. average GC content = 70%), 50 sets with little GC bias (i.e. average GC content = 50%) and 50 sets of AT rich (i.e. average GC content = 30%). Comparison of k-tuple trees with the model trees shows that the average accuracy of k-tuple trees is 53.84% (standard deviation = 0.11) in the no-GC-bias sequence sets, 48.76% (standard devia- tion = 0.09) in the strong-GC-bias sets and 48.65% (standard deviation = 0.09) in the AT-rich sets. This result suggests that base composition can aﬀect the