Comparing Phylogenetic Trees by Matching Nodes Using the Transfer Distance Between Partitions.
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.
Department of Algorithms and System Modeling, Gdansk University of Technology , Gdansk, Poland .
Damian
D
Bogdanowicz
Department of Algorithms and System Modeling, Gdansk University of Technology , Gdansk, Poland .
Krzysztof
K
Giaro
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D022761:Gene Transfer, Horizontal; D008957:Models, Genetic; D010802:Phylogeny
matching pair distance; minimum-weight perfect matching; phylogenetic tree comparison; phylogenetic tree metric