Limits...
Cophenetic metrics for phylogenetic trees, after Sokal and Rohlf.

Cardona G, Mir A, Rosselló F, Rotger L, Sánchez D - BMC Bioinformatics (2013)

Bottom Line: The cophenetic metrics can be safely used on weighted phylogenetic trees with nested taxa and no restriction on degrees, and they can be computed in O(n2) time, where n stands for the number of taxa.The metrics dφ,1 and dφ,2 have positive skewed distributions, and they show a low rank correlation with the Robinson-Foulds metric and the nodal metrics, and a very high correlation with each other and with the splitted nodal metrics.The diameter of dφ,p, for p⩾1 , is in O(n(p+2)/p), and thus for low p they are more discriminative, having a wider range of values.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Mathematics and Computer Science, University of the Balearic Islands, E-07122 Palma de Mallorca, Spain.

ABSTRACT

Background: Phylogenetic tree comparison metrics are an important tool in the study of evolution, and hence the definition of such metrics is an interesting problem in phylogenetics. In a paper in Taxon fifty years ago, Sokal and Rohlf proposed to measure quantitatively the difference between a pair of phylogenetic trees by first encoding them by means of their half-matrices of cophenetic values, and then comparing these matrices. This idea has been used several times since then to define dissimilarity measures between phylogenetic trees but, to our knowledge, no proper metric on weighted phylogenetic trees with nested taxa based on this idea has been formally defined and studied yet. Actually, the cophenetic values of pairs of different taxa alone are not enough to single out phylogenetic trees with weighted arcs or nested taxa.

Results: For every (rooted) phylogenetic tree T, let its cophenetic vectorφ(T) consist of all pairs of cophenetic values between pairs of taxa in T and all depths of taxa in T. It turns out that these cophenetic vectors single out weighted phylogenetic trees with nested taxa. We then define a family of cophenetic metrics dφ,p by comparing these cophenetic vectors by means of Lp norms, and we study, either analytically or numerically, some of their basic properties: neighbors, diameter, distribution, and their rank correlation with each other and with other metrics.

Conclusions: The cophenetic metrics can be safely used on weighted phylogenetic trees with nested taxa and no restriction on degrees, and they can be computed in O(n2) time, where n stands for the number of taxa. The metrics dφ,1 and dφ,2 have positive skewed distributions, and they show a low rank correlation with the Robinson-Foulds metric and the nodal metrics, and a very high correlation with each other and with the splitted nodal metrics. The diameter of dφ,p, for p⩾1 , is in O(n(p+2)/p), and thus for low p they are more discriminative, having a wider range of values.

Show MeSH

Related in: MedlinePlus

2D-histograms showing the relationship between different distances on.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 7: 2D-histograms showing the relationship between different distances on.

Mentions: In order to analyze this data, we have plotted 2D-histograms for all pairs of metrics and we have computed their Spearman’s rank correlation coefficient. On the one hand, the 2D-histograms for and (the most significative case) are given in Figures 7 and 8, respectively. For each pair of distances, we have divided the range of values that each of the distances gets into 25 subranges, and computed how many pairs of trees fall into each of the 25 × 25 different possibilities. Each of these possibilities is represented by a rectangle in a grid, whose darkness level is proportional of the number of trees. On the other hand, the Spearman’s rank correlation coefficient between the aforementioned distances in the most significative case of n = 6 are given in Tables 2 and 3.


Cophenetic metrics for phylogenetic trees, after Sokal and Rohlf.

Cardona G, Mir A, Rosselló F, Rotger L, Sánchez D - BMC Bioinformatics (2013)

2D-histograms showing the relationship between different distances on.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 7: 2D-histograms showing the relationship between different distances on.
Mentions: In order to analyze this data, we have plotted 2D-histograms for all pairs of metrics and we have computed their Spearman’s rank correlation coefficient. On the one hand, the 2D-histograms for and (the most significative case) are given in Figures 7 and 8, respectively. For each pair of distances, we have divided the range of values that each of the distances gets into 25 subranges, and computed how many pairs of trees fall into each of the 25 × 25 different possibilities. Each of these possibilities is represented by a rectangle in a grid, whose darkness level is proportional of the number of trees. On the other hand, the Spearman’s rank correlation coefficient between the aforementioned distances in the most significative case of n = 6 are given in Tables 2 and 3.

Bottom Line: The cophenetic metrics can be safely used on weighted phylogenetic trees with nested taxa and no restriction on degrees, and they can be computed in O(n2) time, where n stands for the number of taxa.The metrics dφ,1 and dφ,2 have positive skewed distributions, and they show a low rank correlation with the Robinson-Foulds metric and the nodal metrics, and a very high correlation with each other and with the splitted nodal metrics.The diameter of dφ,p, for p⩾1 , is in O(n(p+2)/p), and thus for low p they are more discriminative, having a wider range of values.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Mathematics and Computer Science, University of the Balearic Islands, E-07122 Palma de Mallorca, Spain.

ABSTRACT

Background: Phylogenetic tree comparison metrics are an important tool in the study of evolution, and hence the definition of such metrics is an interesting problem in phylogenetics. In a paper in Taxon fifty years ago, Sokal and Rohlf proposed to measure quantitatively the difference between a pair of phylogenetic trees by first encoding them by means of their half-matrices of cophenetic values, and then comparing these matrices. This idea has been used several times since then to define dissimilarity measures between phylogenetic trees but, to our knowledge, no proper metric on weighted phylogenetic trees with nested taxa based on this idea has been formally defined and studied yet. Actually, the cophenetic values of pairs of different taxa alone are not enough to single out phylogenetic trees with weighted arcs or nested taxa.

Results: For every (rooted) phylogenetic tree T, let its cophenetic vectorφ(T) consist of all pairs of cophenetic values between pairs of taxa in T and all depths of taxa in T. It turns out that these cophenetic vectors single out weighted phylogenetic trees with nested taxa. We then define a family of cophenetic metrics dφ,p by comparing these cophenetic vectors by means of Lp norms, and we study, either analytically or numerically, some of their basic properties: neighbors, diameter, distribution, and their rank correlation with each other and with other metrics.

Conclusions: The cophenetic metrics can be safely used on weighted phylogenetic trees with nested taxa and no restriction on degrees, and they can be computed in O(n2) time, where n stands for the number of taxa. The metrics dφ,1 and dφ,2 have positive skewed distributions, and they show a low rank correlation with the Robinson-Foulds metric and the nodal metrics, and a very high correlation with each other and with the splitted nodal metrics. The diameter of dφ,p, for p⩾1 , is in O(n(p+2)/p), and thus for low p they are more discriminative, having a wider range of values.

Show MeSH
Related in: MedlinePlus