e33 Nucleic Acids Research, 2008, Vol. 36, No. 5 PAGE 4 OF 9 Table 2. The average accuracy (A) and standard deviation (S) of all possible combination between tree building methods and distance estimators Dataset 1 Dataset 2 Dataset 3 Dataset 4 Dataset 5 Dataset 6 Dataset 7 Dataset 1 Dataset 2 Dataset 3 Dataset 4 Dataset 5 Name Type NJ k-tuple distance A S Tamura-Nei A S F84 A S Jukes-Cantor A S Kimura A S 0.26110 0.04463 0.11246 0.03687 0.00126 0.00471 0.00043 0.00189 0.00103 0.00448 0.51568 0.09604 0.35853 0.19900 0.42550 0.18174 0.43574 0.20702 0.42759 0.18031 0.30889 0.04278 0.16092 0.03402 0.04410 0.08308 0.03222 0.07173 0.04484 0.08374 0.52836 0.10363 0.58316 0.20987 0.50200 0.17209 0.64871 0.18384 0.50406 0.17061 0.33298 0.04744 0.25570 0.04321 0.07833 0.12747 0.06525 0.12097 0.08002 0.12899 0.40770 0.09988 0.14186 0.08386 0.15035 0.14348 0.14376 0.15540 0.15236 0.14257 0.16618 0.07410 0.04860 0.02595 0.02973 0.04503 0.02238 0.04173 0.03014 0.04510 BioNJ 0.26090 0.04407 0.10977 0.03662 0.00144 0.00496 0.00092 0.00380 0.00144 0.00486 0.51966 0.09773 0.38250 0.19207 0.43291 0.18516 0.43934 0.21054 0.43457 0.18345 0.30846 0.04266 0.16134 0.03489 0.04274 0.08145 0.03231 0.07228 0.04414 0.08259 0.53144 0.10316 0.60882 0.19781 0.51339 0.17759 0.65129 0.18542 0.51556 0.17731 0.33285 0.04766 0.25466 0.04212 0.07830 0.12823 0.06470 0.11992 0.07978 0.12914 estimators in phylogenetic tree reconstruction, we used only two very popular methods to perform tree recon- struction, the standard NJ program in PHYLIP (12) and BioNJ (3). BioNJ has been shown to be the best NJ method (23). In total, we have 10 diﬀerent combinations of tree reconstruction algorithms and distance metrics. We measured the accuracy of underlying distance estimators by comparing each NJ tree with the original model tree used by DAWG to generate sequences. Strictly speaking, the accuracy for the four distance estimators also includes the accuracy of the MSA. We used the symmetric diﬀerence (SD) (24) for this purpose. SD is bounded from zero to 2(t 3), meaning identical to totally diﬀerent respectively, where t is the number of taxa in the trees. It is a commonly used and standardized measure- ment of ‘topological closeness’ between diﬀerent trees. Mathematically speaking, the symmetric diﬀerence of two sets was the number of the sets of elements that are in one but not the other set. For example, when comparing two trees built from 10 taxa, a score between 0 and 14 will be returned, with 0 meaning identical or isomorphic and 14 meaning completely diﬀerent. The result was transformed into accuracy in percentage by the following formula. i ¼ 1 Si Smax 1 Where Si is the SD score of a particular entry and Smax is the largest score possible for that particular comparison. All trees are taken as unrooted trees in our study. RESULTS We simulated 1050 sets of sequences with the number of sequences ranging from 50 to 250 or more and with diﬀerent settings for indel rates and sequence lengths (Table 1). We constructed both NJ and BioNJ trees for each set of sequences and found that they gave qualita- tively the same results in terms of the comparison between the k-tuple distance and the other four distance estima- tors. For brevity, we show only the results of NJ. The results of BioNJ are summarized in Table 2. Alignments for short sequences such as upstream regulatory regions can be extremely diﬃcult due to the Figure 1. The accuracy of all ﬁve metrics on dataset 1 with the NJ method. lack of knowledge on their mutation patterns. Low alignment quality can lead to erroneous inference of phylogenetic trees for these regions. Because using the k-tuple distance matrix to build phylogenetic trees bypasses the construction of an MSA, the k-tuple distance has great potential in addressing the need of tree construction for these regions. To evaluate the k-tuple distance performance in short sequences, we simulated 210 sets of sequences with the number of taxa in the sets ranging from 50 to 260 and sequence lengths from 30 to 120 bp. Figure 1 shows the result of the accuracy of trees reconstructed by the NJ method for the ﬁve distance estimators on dataset 1. It shows that the k-tuple distance outperformed other distance estimators by a considerable amount. The Tamura–Nei distance performed second with an average accuracy of 0.11246, less than half of that of the k-tuple distance 0.26110. The other three performed similarly, with average accuracy of 0.00126 for F84, 0.00043 for Jukes–Cantor and 0.00103 for Kimura. To see the performance of the k-tuple distance on real data, we obtained trees from the TreeFAM database. We used 210 trees together with their branch lengths as