ON A MATCHING DISTANCE BETWEEN ROOTED PHYLOGENETIC TREES
ON A MATCHING DISTANCE BETWEEN ROOTED PHYLOGENETIC TREES
复制标题
DOI：
10.2478/amcs-2013-0050
复制
发表时间：
2013-09-01
影响因子：
1.9
通讯作者：
Giaro, Krzysztof
中科院分区：
文献类型：
--
作者：
Bogdanowicz, Damian;Giaro, Krzysztof
Robinson-Foulds（RF）距离是评价系统发育树之间相异性最常用的方法。在本文中，我们详细定义并探讨了匹配聚类（MC）距离的性质，它可以被视为有根树的RF度量的细化。与RF类似，MC对比较树的集群进行操作，但距离评估更复杂。利用基于二分图最小权完美匹配的图论方法，将聚类之间的相似性值转化为树的相异性的最终MC-得分。分析的性质给洞察MC生成的度量空间的结构，它的关系与匹配分裂（MS）的距离无根树和期望的距离之间的渐近行为的二元n叶树一致选择MC和MS（θ（n（3/2）。
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 (Theta(n(3/2))).