Bogdanowicz Damian, Giaro Krzysztof
Department of Algorithms and System Modeling, Gdansk University of Technology , Gdansk, Poland .
J Comput Biol. 2017 May;24(5):422-435. doi: 10.1089/cmb.2016.0204. Epub 2017 Feb 8.
Ability to quantify dissimilarity of different phylogenetic trees describing the relationship between the same group of taxa is required in various types of phylogenetic studies. For example, such metrics are used to assess the quality of phylogeny construction methods, to define optimization criteria in supertree building algorithms, or to find horizontal gene transfer (HGT) events. Among the set of metrics described so far in the literature, the most commonly used seems to be the Robinson-Foulds distance. In this article, we define a new metric for rooted trees-the Matching Pair (MP) distance. The MP metric uses the concept of the minimum-weight perfect matching in a complete bipartite graph constructed from partitions of all pairs of leaves of the compared phylogenetic trees. We analyze the properties of the MP metric and present computational experiments showing its potential applicability in tasks related to finding the HGT events.
在各类系统发育研究中，都需要具备量化描述同一组分类单元之间关系的不同系统发育树差异的能力。例如，此类度量用于评估系统发育构建方法的质量、定义超级树构建算法中的优化标准，或发现水平基因转移（HGT）事件。在目前文献中描述的一系列度量中，最常用的似乎是罗宾逊 - 福尔兹距离。在本文中，我们为有根树定义了一种新的度量——匹配对（MP）距离。MP度量使用了在由比较的系统发育树所有叶对的划分构建的完全二分图中最小权重完美匹配的概念。我们分析了MP度量的性质，并展示了计算实验，表明其在与发现HGT事件相关任务中的潜在适用性。
