Limits...
Performance comparison between k-tuple distance and four model-based distances in phylogenetic tree reconstruction.

Yang K, Zhang L - Nucleic Acids Res. (2008)

Bottom Line: 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.

View Article: PubMed Central - PubMed

Affiliation: Virginia Bioinformatics Institute, Virginia, USA.

ABSTRACT
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.

Show MeSH

Related in: MedlinePlus

The accuracies of the five metrics on dataset 4 with the NJ method.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC2275138&req=5

Figure 4: The accuracies of the five metrics on dataset 4 with the NJ method.

Mentions: 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–Cantor and the lowest 0.50200 for the F84 matrix. Tamura–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. 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 five metrics, but the difference is trivial, <4% (Table 2).Figure 4.


Performance comparison between k-tuple distance and four model-based distances in phylogenetic tree reconstruction.

Yang K, Zhang L - Nucleic Acids Res. (2008)

The accuracies of the five metrics on dataset 4 with the NJ method.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC2275138&req=5

Figure 4: The accuracies of the five metrics on dataset 4 with the NJ method.
Mentions: 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–Cantor and the lowest 0.50200 for the F84 matrix. Tamura–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. 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 five metrics, but the difference is trivial, <4% (Table 2).Figure 4.

Bottom Line: 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.

View Article: PubMed Central - PubMed

Affiliation: Virginia Bioinformatics Institute, Virginia, USA.

ABSTRACT
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.

Show MeSH
Related in: MedlinePlus