PAGE 3 OF 9 Nucleic Acids Research, 2008, Vol. 36, No. 5 e33 Table 1. Summary of the 1470 simulated sets of sequences Datasets No. of Trees Indel rate No. of Taxa 1 2 3 4 5 6 7 210 210 210 210 210 210 210 Types Random Real Random Real Random Real Real 0.2 0.1 0.1 0 0 1 10 50–260 50–250 and 10 trees with taxa >250 50–260 50–250 and 10 tree with taxa >250 50–260 50–250 and 10 trees with taxa >250 50–250 and 10 trees with taxa >250 Length (bps) 30–200 50–1500 500–1500 500–1500 500–1500 500–1500 500–1500 The length of a simulated sequence is a random number within the range speciﬁed below. sequences, regulatory regions and introns have much higher mutation rates and thus tend to be more diverse in both sequence composition and sequence length for a given set of genes. Therefore, aligning these sequences can be problematic, and the quality of the MSA is question- able and can be very low. In order to address this issue, we generated sequences with lengths ranging from 30 to 200 bp and insertion and deletion rates of 0.1, respectively. We generated random trees and used them as model trees to generate sequences. For these sets of sequences, we tested the performance of the k-tuple distance in dealing with short and divergent sequences. The second and third datasets consisted of sequences of diﬀerent lengths (500– 1500 bp), which accommodate the common situation of phylogenetic tree reconstruction. The only diﬀerence between these two sets was the source of model trees for simulations. Dataset 2 used real trees downloaded from the TreeFam database (16) as model trees while dataset 3 used randomly generated trees for sequence simulation. For dataset 2, we randomly selected 210 real trees from the TreeFam website. We chose 200 trees with the number of sequences within the interval of 50–250 and 10 trees with the number of sequences larger than 250. For example, trees 1–10 have 50–60 sequences, trees 11–20 have 61–70 sequences, trees 21–30 have 71–80 sequences and so on. For dataset 3, we generated random trees using the bioperl module RandomFactory. The diﬀerence between real trees and random trees lies in the branch lengths, which will in turn aﬀect multiple sequence alignment. Datasets 4 and 5 consisted of simulated sequences with the same length, thus accommodating the situation of highly similar sequences in the real world. It is an ideal situation, but we used it as a boundary situation. Dataset 4 used real trees as model trees, and dataset 5 used random trees as model trees. Computation of five distance matrices The k-tuple distance is calculated as the diﬀerence in the frequencies of all possible tuples of length k. We calculate the k-tuple distance by moving a sliding window of length k over the sequence with 1 bp overlapping step size and counting the number of occurrences of tuples of length k. For example, when tuple size k is 3, we need to count the number of occurrences of 64 possible tuples in a DNA sequence. Therefore, each sequence can be represented by a vector containing 4k (k is the tuple size, k 1) numbers, each of which represents the frequency of the correspond- ing tuple in the sequence. For any two sequences X and Y, the k-tuple distance is calculated using the formula: SðX,YÞ ¼ P4k Yij2, where Xi and Yi correspond to the tuple i’s if¼r1eqjXuiencies (=counts/n k + 1) in sequences X and Y, respectively; n is the sequence length of either sequence X or Y; k is the tuple length. Therefore, the k-tuple distance takes into account the sequence length diﬀerence. We compared tuples of diﬀerent sizes and found that tuple size 5 combines both performance speed and accuracy; tuples of shorter lengths contain less information and include more randomness; tuples of longer lengths contain more information and less random- ness, but the vector size expands exponentially and gets too large and computationally ineﬃcient. We observed combined optimum when the length is 5. There was a slight performance drop when the length was raised to 6 (data not shown here) [though we suggest no particular interpretation in terms of biological process or structure of 5-tuples versus other k-tuples, it would seem that 5-tuples constitute more precise genomic signatures than dinucleo- tides as studied, e.g. in (17,18)]. Because the k-tuple distance plays the same role as other distance estimators in phylogenetic tree reconstruction, the procedure of producing trees using the k-tuple distance is the same as for other distance estimators, that is, ﬁrst build a pairwise k-tuple distance matrix for a set of sequences, and then construct a phylogenetic tree based on the distance matrix using a distance-base tree-building method. As we chose tuple length 5, we obtained a vector of 1024 numbers representing the frequencies of all 1024 possible tuples for a speciﬁc sequence. We constructed the k-tuple distance by adopting Euclidean distance to measure distances between two sequences. As the dis- tances in the matrix are computed on percentages and thus small, we ampliﬁed it by 1000, which has no eﬀect on subsequent analyses. We compared the performance of the k-tuple distance with four other distance estimators including F84 (19), Jukes–Cantor (20), Kimura (21) and Tamura–Nei (22). We used MUSCLE to compute MSAs for all the simulated sets of sequences. We calculated the F84, Jukes–Cantor and Kimura distance matrices through the dnadist program in PHYLIP (12) and the Tamura–Nei distance matrix through PAUP (13). Performance comparison of five distance estimators using symmetric distance Since the focus of our study is to compare the performance of the k-tuple distance with existing distance