a phylogenetic tree is a graphical representation of the genetic closeness among different species or biological entities . despite other representation forms , such as phylogenetic networks ( 1 ) , trees are still the most popular and standard representation of species evolutionary relationships .
many different criteria can be used to build a tree for a set of dna sequences , such as maximum parsimony , minimum evolution , neighbor - joining ( nj ) , maximum likelihood and bayesian inference . among these methods
, nj is the most frequently used due to its high speed and comparable accuracy .
many modified versions of nj algorithms ( 2 ) have been introduced since its introduction , such as bionj ( 3 ) and weighbor ( 4 ) .
the current paradigm in phylogenetic tree reconstruction is to start from a set of sequences , build multiple sequence alignment ( msa ) , and then based on the msa , build a tree using one or several methods mentioned earlier .
therefore , clearly , all methods of phylogenetic tree reconstruction share the same starting point : computation of an msa from the given set of dna sequences .
msa refers to the arrangement of a set of sequences so that it reflects the evolutionary history of these sequences .
computationally , it is represented by a matrix , in which a row of the matrix represents one of the sequences in the set of sequences and a column represents specific positions along all the sequences and reflects matches , mismatches or gaps in all sequences .
therefore , once an msa is constructed , an evolutionary hypothesis is automatically generated and represented by the alignment .
the quality of an msa thus directly affects the accuracy of subsequent phylogenetic inference , and erroneous msa can lead to low - quality phylogenetic trees that give misleading information and false inference of evolutionary histories .
more than 50 multiple sequence alignment methods and/or packages have been described over the past 10 years ( 5 ) and there were at least 20 new publications in 2005 alone ( 6 ) . among many msa programs , clustalw ( 7 )
it made its way to daily usage by its friendly interface , stability and accuracy .
however , as a result of its high consumption of time , it becomes impractical to use when the number of sequences that need to be aligned becomes large and/or the lengths of sequences reach a certain level .
subsequently , other programs have been introduced such as t - coffee ( 8) , mafft ( 9 ) and muscle ( 10 ) .
comparatively , the relatively new muscle has the highest accuracy among existing programs and the shortest running time , according to the original paper ( 10 ) .
however , despite the essential role of msa in the entire process of phylogenetic tree reconstruction and multiple efforts to improve msa methods , there remain several issues .
first , finding the optimal msa under a set of scoring schemes for a large number of sequences is computationally impossible .
even with heuristic methods , aligning a large number of sequences can be time consuming .
second , the quality of an msa is extremely sensitive to the choices of the scoring parameters used in producing the alignment , such as penalty scores of gap opening and gap extension .
different scoring schemes can produce drastically different msas , which in turn can lead to different phylogenetic trees .
unfortunately , in most cases , the true msa that reflects the evolutionary history of the underlying set of sequences is unknown .
thus the users have to either choose to trust the default scoring schemes or use their own judgment in choosing a scoring scheme .
third , the quality of an msa is sensitive to sequence length difference and the degree of sequence identity .
a set of sequences with dramatically different lengths can adversely influence the quality of an msa .
similarly , if the sequences in the set are highly diverged from one another , the quality of an msa is most likely low . because the construction of an msa can introduce errors and adversely influence the accuracy of subsequent phylogenetic inference and
because it is time consuming to construct an msa for a large number of sequences , we formally introduce the application of the k - tuple distance ( aka k - mer distance ) in the phylogenetic tree reconstruction .
the k - tuple distance refers to the total of the differences , over all possible k - tuples , between the sequences , for any given length k. the idea of using the k - tuple distance to construct a tree is not new and the procedure is in fact embedded in many msa programs such as clustalw ( 7 ) , kalign ( 11 ) and muscle ( 10 ) . to construct an msa
, these programs first compute a pairwise k - tuple distance matrix for the sequences to be aligned , use upgma or nj methods to quickly build a  guide tree , and use the guide tree to determine the order in which sequences or profiles are aligned .
however , despite the common use of k - tuple distance in generating  guide trees , guide trees are rarely used by evolutionary biologists as the final phylogenetic trees , and instead , packages dedicated to tree building such as phylip ( 12 ) and paup ( 13 ) will be used to produce the final trees . to our knowledge , the value of the k - tuple distance in constructing a 
real phylogenetic tree ( instead of a  guide tree for sequence alignment ) has not been formally discussed before , nor has the accuracy of the resulting phylogenetic tree .
as the k - tuple distance can be calculated without sequence alignment and its computation for even a large number of sequences takes only seconds , k - tuple distance can be extremely useful when we are faced with the overwhelming number of sequences that require phylogenetic information and may essentially be the only option in cases where there are sequences that are too diverged to be reasonably aligned in the post - genomic era .
but an important prerequisite for the broad application of k - tuple distance in phylogenetic tree reconstruction is that the trees built from the k - tuple distance have comparable accuracy to the trees built from traditional alignment - based methods . in order to address the issue , we compared the k - tuple distance performance and accuracy in producing the correct nj and bionj trees with four other commonly used distance estimators .
the four distance estimators are model - based , in other words , they are computed based on certain substitution models for dna sequence evolution .
our results show that when k equals five , the k - tuple distance outperformed other distance estimators most of the time and it could be twice , or more , the accuracy of other distance estimators .
moreover , compared to the existing alignment - dependent distance estimators , the k - tuple distance is fast and easy to compute and can save the tremendous amount of running time that is required for constructing msas .
taken together , our results show that the application of k - tuple distance in phylogenetic tree reconstruction is very promising .
dawg is a program that simulates the evolution of sequences based on a given phylogenetic tree , incorporating both nucleotide substitutions and insertions and deletions .
it can simulate nucleotide substitutions with different substitution models and indel formation with a power law distribution of indel sizes .
we simulated five different datasets of sequences using the hky substitution model ( 15 ) , as summarized in table 1 , in order to accommodate the different situations that we might encounter in real - world phylogenetic tree reconstruction .
the first dataset is generated to consider the situation of alignment of regulatory regions or short intronic sequences and reconstruction of phylogenetic trees based on the alignment .
compared with coding 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 questionable 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 .
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 different lengths ( 5001500 bp ) , which accommodate the common situation of phylogenetic tree reconstruction .
the only difference 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 .
we chose 200 trees with the number of sequences within the interval of 50250 and 10 trees with the number of sequences larger than 250 .
for example , trees 110 have 5060 sequences , trees 1120 have 6170 sequences , trees 2130 have 7180 sequences and so on .
the difference between real trees and random trees lies in the branch lengths , which will in turn affect 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 .
dataset 4 used real trees as model trees , and dataset 5 used random trees as model trees . 

table 1.summary of the 1470 simulated sets of sequencesdatasetsno . of treestypesindel rateno . of taxalength ( bps)1210random0.250260302002210real0.150250 and 10 trees with taxa > 2505015003210random0.15026050015004210real050250 and 10 tree with taxa > 25050015005210random05026050015006210real150250 and 10 trees with taxa
> 25050015007210real1050250 and 10 trees with taxa > 2505001500the length of a simulated sequence is a random number within the range specified below .
summary of the 1470 simulated sets of sequences the length of a simulated sequence is a random number within the range specified below .
the k - tuple distance is calculated as the difference 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 4 ( k is the tuple size , k  1 ) numbers , each of which represents the frequency of the corresponding tuple in the sequence .
for any two sequences x and y , the k - tuple distance is calculated using the formula : , where xi and yi correspond to the tuple i 's frequencies ( = counts / nk + 1 ) in sequences x and y , respectively ; n is the sequence length of either sequence x or y ; k is the tuple length .
we compared tuples of different 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 randomness , but the vector size expands exponentially and gets too large and computationally inefficient .
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 dinucleotides 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 , first 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 specific sequence .
we constructed the k - tuple distance by adopting euclidean distance to measure distances between two sequences .
as the distances in the matrix are computed on percentages and thus small , we amplified it by 1000 , which has no effect 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 calculated the f84 , jukes  cantor and kimura distance matrices through the dnadist program in phylip ( 12 ) and the tamura 
since the focus of our study is to compare the performance of the k - tuple distance with existing distance estimators in phylogenetic tree reconstruction , we used only two very popular methods to perform tree reconstruction , the standard nj program in phylip ( 12 ) and bionj ( 3 ) .
bionj has been shown to be the best nj method ( 23 ) . in total
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 .
sd is bounded from zero to 2(t  3 ) , meaning identical to totally different respectively , where t is the number of taxa in the trees .
mathematically speaking , the symmetric difference 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 different . the result was transformed into accuracy in percentage by the following formula . 
 1 
 where si is the sd score of a particular entry and smax is the largest score possible for that particular comparison .
dawg is a program that simulates the evolution of sequences based on a given phylogenetic tree , incorporating both nucleotide substitutions and insertions and deletions .
it can simulate nucleotide substitutions with different substitution models and indel formation with a power law distribution of indel sizes .
we simulated five different datasets of sequences using the hky substitution model ( 15 ) , as summarized in table 1 , in order to accommodate the different situations that we might encounter in real - world phylogenetic tree reconstruction .
the first dataset is generated to consider the situation of alignment of regulatory regions or short intronic sequences and reconstruction of phylogenetic trees based on the alignment .
compared with coding 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 questionable 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 .
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 different lengths ( 5001500 bp ) , which accommodate the common situation of phylogenetic tree reconstruction .
the only difference 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 .
we chose 200 trees with the number of sequences within the interval of 50250 and 10 trees with the number of sequences larger than 250 .
for example , trees 110 have 5060 sequences , trees 1120 have 6170 sequences , trees 2130 have 7180 sequences and so on .
the difference between real trees and random trees lies in the branch lengths , which will in turn affect 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 .
dataset 4 used real trees as model trees , and dataset 5 used random trees as model trees . 

table 1.summary of the 1470 simulated sets of sequencesdatasetsno . of treestypesindel rateno . of taxalength ( bps)1210random0.250260302002210real0.150250 and 10 trees with taxa > 2505015003210random0.15026050015004210real050250 and 10 tree with taxa > 25050015005210random05026050015006210real150250 and 10 trees with taxa
> 25050015007210real1050250 and 10 trees with taxa > 2505001500the length of a simulated sequence is a random number within the range specified below .
summary of the 1470 simulated sets of sequences the length of a simulated sequence is a random number within the range specified below .
the k - tuple distance is calculated as the difference 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 4 ( k is the tuple size , k  1 ) numbers , each of which represents the frequency of the corresponding tuple in the sequence .
for any two sequences x and y , the k - tuple distance is calculated using the formula : , where xi and yi correspond to the tuple i 's frequencies ( = counts / nk + 1 ) in sequences x and y , respectively ; n is the sequence length of either sequence x or y ; k is the tuple length .
we compared tuples of different 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 randomness , but the vector size expands exponentially and gets too large and computationally inefficient .
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 dinucleotides 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 , first 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 specific sequence .
we constructed the k - tuple distance by adopting euclidean distance to measure distances between two sequences .
as the distances in the matrix are computed on percentages and thus small , we amplified it by 1000 , which has no effect 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 calculated the f84 , jukes  cantor and kimura distance matrices through the dnadist program in phylip ( 12 ) and the tamura 
since the focus of our study is to compare the performance of the k - tuple distance with existing distance estimators in phylogenetic tree reconstruction , we used only two very popular methods to perform tree reconstruction , the standard nj program in phylip ( 12 ) and bionj ( 3 ) .
bionj has been shown to be the best nj method ( 23 ) . in total
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 .
sd is bounded from zero to 2(t  3 ) , meaning identical to totally different respectively , where t is the number of taxa in the trees .
mathematically speaking , the symmetric difference 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 different .
the result was transformed into accuracy in percentage by the following formula . 
 1 
 where si is the sd score of a particular entry and smax is the largest score possible for that particular comparison .
we simulated 1050 sets of sequences with the number of sequences ranging from 50 to 250 or more and with different 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 qualitatively the same results in terms of the comparison between the k - tuple distance and the other four distance estimators . for brevity , we show only the results of nj .
table 2.the average accuracy ( a ) and standard deviation ( s ) of all possible combination between tree building methods and distance estimatorsnametypenjbionjdataset 1dataset 2dataset 3dataset 4dataset 5dataset 6dataset 7dataset 1dataset
2dataset 3dataset 4dataset 5k - tuple distancea0.261100.515680.308890.528360.332980.407700.166180.260900.519660.308460.531440.33285s0.044630.096040.042780.103630.047440.099880.074100.044070.097730.042660.103160.04766tamura - neia0.112460.358530.160920.583160.255700.141860.048600.109770.382500.161340.608820.25466s0.036870.199000.034020.209870.043210.083860.025950.036620.192070.034890.197810.04212f84a0.001260.425500.044100.502000.078330.150350.029730.001440.432910.042740.513390.07830s0.004710.181740.083080.172090.127470.143480.045030.004960.185160.081450.177590.12823jukes - cantora0.000430.435740.032220.648710.065250.143760.022380.000920.439340.032310.651290.06470s0.001890.207020.071730.183840.120970.155400.041730.003800.210540.072280.185420.11992kimuraa0.001030.427590.044840.504060.080020.152360.030140.001440.434570.044140.515560.07978s0.004480.180310.083740.170610.128990.142570.045100.004860.183450.082590.177310.12914 the average accuracy ( a ) and standard deviation ( s ) of all possible combination between tree building methods and distance estimators alignments for short sequences such as upstream regulatory regions can be extremely difficult due to the 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 five distance estimators on dataset 1 .
it shows that the k - tuple distance outperformed other distance estimators by a considerable amount .
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
the accuracy of all five metrics on dataset 1 with the nj method . to see the performance of the k - tuple distance on real data
we used 210 trees together with their branch lengths as model trees to simulate dataset 2 .
figure 2 shows the accuracies of all five distance estimators with the nj method on dataset 2 .
although the advantage of the k - tuple distance matrix is not as obvious as in dataset 1 , we can see that k - tuple distance accuracy is above the other distance matrices most of the time .
in fact , the k - tuple distance has the best performance for 127 of the 210 trees .
another very important advantage that is not very clearly shown in the figure is the stability of the k - tuple distance .
it has a leading average accuracy of 0.51568 with the lowest standard deviation of 0.09604 .
cantor ranked second in terms of average accuracy ( = 0.43574 ) but has the highest standard deviation ( = 0.20702 ) among the five estimators .
kimura and f84 scored almost the same with an average accuracy of 0.42759 and 0.42550 , respectively , and a standard deviation of 0.01831 and 0.18175 , respectively .
nei has the lowest average accuracy ( 0.35853 ) with a standard deviation of 0.19900 .
it is clear that , in additional to its high accuracy , the k - tuple distance also produced a much smaller standard deviation , which is an equally important factor in judging the performance of a metric .
bionj trees gave a slightly better accuracy for all five estimators but the difference was very subtle ( table 2 ) . 

figure 3 shows the performance comparison of five estimators on dataset 3 generated by random trees with sequence lengths from 500 to 1500 bp .
it is interesting to note that as the number of taxa increases in the trees ( the trees are arranged along the x - axis according to the ascending order of the number of taxa that trees contain ) , the accuracy of f84 , kimura and juke  cantor significantly dropped .
nei and k - tuple distance maintained their accuracy regardless of the change of the number of taxa .
as shown in figure 3 , after the 100th tree sample , which contained 150 taxa , f84 , jukes  cantor and kimura basically had the same performance as random clustering .
the k - tuple distance achieved the highest average accuracy of 0.30889 with a standard deviation of 0.04278 .
nei had the second highest average accuracy of 0.16092 with a standard deviation of 0.03402 .
kimura and f84 matrices performed similarly , with an average accuracy of 0.04410 and 0.04484 , respectively , and a standard deviation of 0.08308 and 0.08374 , respectively . jukes 
cantor matrix ranked last with the lowest average accuracy of 0.03222 and a standard deviation of 0.07173 . 

figure 4 shows the comparison of accuracies of the metrics with the nj method for dataset 4 .
compared to results from other datasets , the accuracy difference decreased considerably , with the highest average accuracy of 0.64871 for jukes
nei , k - tuple distance and kimura ranked second , third and fourth with an average accuracy of 0.58316 , 0.52836 and 0.50406 , respectively . despite the loss of advantage in accuracy ,
the k - tuple distance still maintained its leading position in terms of performance stability with the lowest standard deviation of 0.10363 .
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 five metrics , but the difference is trivial , < 4% ( table 2 ) . 

figure 5 compares the accuracy of different 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 .
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 five distance estimators , five datasets and two tree - building methods .
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 
in order to examine the reason for the difference in accuracies of the k - tuple distance in the above datasets , we calculated the average pairwise sequence identity for each simulated sample .
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 ) . 
 figure 6.the distribution of average pairwise sequence identity in all the datasets . the distribution of average pairwise sequence identity in all the datasets
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 difference 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 difference will drop greatly for the alignment - dependent distance estimators . the most significant difference 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 ) .
a recent study ( 5 ) on msa algorithm performance has shown that all msa programs return alignments of low accuracy when 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 different lengths from different species .
difference in sequence lengths is introduced through indel rate setting in the sequence generation program and branch length in the model trees .
the difference between real trees and randomly generated trees lies mostly on the branch lengths ( i.e. the degree of sequence divergence ) .
specifically , 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 gene family members might have been discarded from final 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 3040% 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 .
nei distances show a stronger accuracy and stability under such circumstances indicates that the simpler distance estimators , as compared to tamura 
nei , is not a good fit to the underlying sequences , which were generated under the hky model , a special case of the tamura 
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 reconstruction , 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 ) .
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 .
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 difference between different methods diminishes and the difference 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 can not reflect 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 refined model - based distances , because , for example , it can not differentiate 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 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 different indel / substitution rate ratio scheme : the first 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 suffer 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 . 

figure 7.accuracy comparison for dataset 6 with indel versus substitution rate ratio of 1 . 
 figure 8.accuracy comparison for dataset 7 with indel versus substitution rate ratio of 10 . accuracy comparison for dataset 6 with indel versus substitution rate ratio of 1 .
accuracy comparison for dataset 7 with indel versus substitution rate ratio of 10 . 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 different 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 deviation = 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 affect the performance of k - tuple distance , although the impact seems small . as simulation
can not capture all the complexities of real sequence evolution , it will be useful to perform some analyses on real data . however , real sequences with 
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 confidence of a reconstructed phylogenetic tree .
it is usually done by re - sampling the sequences with replacement , 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 .
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 difficulty in recovering the phylogenetic groupings that have high bootstrap confidence in the alignment - based trees , but for the phylogenetic groupings with low confidence 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 .
however , even though muscle is faster than clustalw , it on average still takes 3040 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 ) .
 phylogenetic tree reconstruction requires construction of a multiple sequence alignment ( msa ) from sequences . 
 computationally , it is difficult to achieve an optimal msa for many sequences . 
 moreover , even if an optimal msa is obtained , it may not be the true msa that reflects the evolutionary history of the underlying sequences . 
 therefore , errors can be introduced during msa construction which in turn affects the subsequent phylogenetic tree construction . in order to circumvent this issue 
 , we extend the application of the k - tuple distance to phylogenetic tree reconstruction . 
 the k - tuple distance between two sequences is the sum of the differences in frequency , over all possible tuples of length k , between the sequences and can be estimated without msas . 
 it has been traditionally used to build a fast  guide tree to assist the construction of msas . using the 1470 simulated sets of sequences generated under different evolutionary scenarios , the neighbor - joining trees and bionj trees , we compared the performance of the k - tuple distance with 
 four commonly used distance estimators including jukes  cantor , kimura , f84 and tamura  nei . 
 these four distance estimators fall into the category of model - based distance estimators , as each of them takes account of a specific substitution model in order to compute the distance between a pair of already aligned sequences . 
 results show that trees constructed from the k - tuple distance are more accurate than those from other distances most time ; when the divergence between underlying sequences is high , the tree accuracy could be twice or higher using the k - tuple distance than other estimators . furthermore , 
 as the k - tuple distance voids the need for constructing an msa , it can save tremendous amount of time for phylogenetic tree reconstructions when the data include a large number of sequences . 
INTRODUCTION
MATERIALS AND METHODS
Simulation of five sequence datasets
Computation of five distance matrices
Performance comparison of five distance estimators using symmetric distance
RESULTS
DISCUSSION