e33 Nucleic Acids Research, 2008, Vol. 36, No. 5 of 0.10363. The standard deviation for the Tamura–Nei, F84, Jukes–Cantor and Kimura matrices were 0.20987, 0.17209, 0.18384 and 0.17061, respectively. With BioNJ, we observed a better accuracy score for all ﬁve metrics, but the diﬀerence is trivial, <4% (Table 2). Figure 5 compares the accuracy of diﬀerent distance matrices with the NJ method for dataset 5. With the increase of the number of taxa in the trees, the accuracy of F84, Jukes–Cantor and Kimura decreased greatly, similar to the observation in dataset 1 where sequences were simulated with indels using random trees. The k-tuple distance has the best performance followed by Tamura– Nei. In this dataset, BioNJ performed at almost the same level as traditional NJ (Table 2). Table 2 shows a summary of the average accuracy (A) and standard deviation (S) of the 50 combinations of the ﬁve distance estimators, ﬁve datasets and two tree- building methods. k-tuple distance outperformed other distance metrics in most cases. Its performance is very stable, as indicated by the low standard deviation. Only Tamura–Nei achieved a slightly lower standard deviation with the NJ method on dataset 5, which might be because the HKY model used to simulate sequence evolution is a special case of the Tamura–Nei model. In order to examine the reason for the diﬀerence in accuracies of the k-tuple distance in the above datasets, we calculated the average pairwise sequence identity for each simulated sample. The distribution in each dataset is shown in Figure 6. The average pairwise sequence identity ranges from 8.53 to 79.43 in dataset 1, from 27.52 to 73.14 in dataset 2, from 26.07 to 31.15 in dataset 3, from 27.44 to 79.43 in dataset 4 and from 26.35 to 32.77 in dataset 5. Therefore, in general, the 210 sets of sequences in datasets 2 and 4 (generated from real trees) tend to have a higher average pairwise sequence identity than that of those in datasets 3 and 5 (generated from random trees). DISCUSSION In most cases, the performance of distance matrices is largely related to the size of the tree (i.e. the number of taxa in the tree), the length diﬀerence and the divergence of the sequences. Most distance matrices would produce good results with a small number of sequences of low divergence. However, as the number of sequences increases and sequence divergence increases, the accuracy measured by the symmetric diﬀerence will drop greatly for the alignment-dependent distance estimators. The most signiﬁcant diﬀerence between the accuracy of the k-tuple distance and the other distance estimators was found in dataset 1, which contains short sequences with high diversity. This dataset was generated to take account of upstream regulatory regions and short intronic sequences. Our results show that with the increase of sequence diversity and the number of taxa, the accuracy of all other matrices except the k-tuple distance has dropped tremendously (Figure 1). The decrease of accuracy is most likely due to decreased quality of MSAs. A recent study (5) on MSA algorithm performance has shown that all MSA programs return alignments of low accuracy when PAGE 6 OF 9 Figure 5. The accuracies of the ﬁve metrics on dataset 5 with the NJ method. Figure 6. The distribution of average pairwise sequence identity in all the datasets. highly diverged sequences are used. This fact may explain the existence of the performance gap between the k-tuple distance, which does not rely on multiple sequence alignment to determine sequence distance, and the other distance estimators. The most common scenario in phylogenetic tree reconstruction is to construct a tree from a group of sequences with diﬀerent lengths from diﬀerent species. Datasets 2 and 3 were generated to take account of this aspect. Diﬀerence in sequence lengths is introduced through indel rate setting in the sequence generation program and branch length in the model trees. The diﬀerence between real trees and randomly generated trees lies mostly on the branch lengths (i.e. the degree of sequence divergence). Speciﬁcally, real trees in TreeFAM are built mostly because sequence alignments are of high quality, which essentially limits the real trees to datasets containing only sequences that can be aligned by alignment programs. Due to this limitation, some remote