online read us now
Paper details
Number 3 - September 2013
Volume 23 - 2013
On a matching distance between rooted phylogenetic trees
Damian Bogdanowicz, Krzysztof Giaro
Abstract
The Robinson–Foulds (RF) distance is the most popular method of evaluating the dissimilarity between phylogenetic trees.
In this paper, we define and explore in detail properties of the Matching Cluster (MC) distance, which can be regarded as a
refinement of the RF metric for rooted trees. Similarly to RF, MC operates on clusters of compared trees, but the distance
evaluation is more complex. Using the graph theoretic approach based on a minimum-weight perfect matching in bipartite
graphs, the values of similarity between clusters are transformed to the final MC-score of the dissimilarity of trees. The
analyzed properties give insight into the structure of the metric space generated by MC, its relations with the Matching
Split (MS) distance of unrooted trees and asymptotic behavior of the expected distance between binary n-leaf trees selected uniformly in both MC and MS (Θ(n3/2)).
Keywords
phylogenetic tree, phylogenetic tree metric, phylogenetic tree comparison, matching cluster distance, matching split distance