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.
Get full access to this article
View all access options for this article.
References
1.
AllenB.L., and SteelM.2001. Subtree transfer operations and their induced metrics on evolutionary trees. Ann. Comb., 5, 1–15.
BocA., PhilippeH., and MakarenkovV.2010. Inferring and validating horizontal gene transfer events using bipartition dissimilarity. Syst. Biol., 59, 195–211.
4.
BöckerS., CanzarS., and KlauG.W.2013. The generalized Robinson-Foulds metric, 156–169. In Algorithms in Bioinformatics. LNCS 8126. Springer, Berlin, Heidelberg.
5.
BogdanowiczD.2008. Comparing phylogenetic trees using a minimum weight perfect matching. Proc. 1st International Conference on Information Technology, 451–454. Gdansk, Poland.
6.
BogdanowiczD., and GiaroK.2012. Matching split distance for unrooted binary phylogenetic trees. IEEE/ACM Trans. Comput. Biol. Bioinform., 9, 150–160.
7.
BogdanowiczD., and GiaroK.2013. On a matching distance between rooted phylogenetic trees. Int. J. Appl. Math. Comput. Sci., 23, 669–684.
8.
BogdanowiczD., GiaroK., and WróbelB.2012. TreeCmp: Comparison of trees in polynomial time. Evol. Bioinform., 8, 475–487.
9.
BordewichM., GascuelO., HuberK.T., et al.2009. Consistency of topological moves based on the balanced minimum evolution principle of phylogenetic inference. IEEE/ACM Trans. Comput. Biol. Bioinform., 6, 110–117.
10.
BordewichM., and SempleC.2005. On the computational complexity of the rooted subtree prune and regraft distance. Ann. Comb., 8, 409–423.
11.
CardonaG., LlabrésM., RossellóF., et al.2010. Nodal distances for rooted phylogenetic trees. J. Math. Biol., 61, 253–276.
12.
CardonaG., MirA., RossellóF., et al.2013. Cophenetic metrics for phylogenetic trees, after Sokal and Rohlf. BMC Bioinformat. 14, 3.
13.
CharonI., DenœudL., GuénocheA., et al.2006. Maximum transfer distance between partitions. J. Classification, 23, 103–121.
14.
ChaudharyR., BurleighJ.G., and Fernández-BacaD.2013. Inferring species trees from incongruent multi-copy gene trees using the Robinson-Foulds distance. Algorithms Mol. Biol. 8, 28.
15.
ChenY.H.2012. The k partition-distance problem. J. Comp. Biol., 19, 404–417.
16.
ChenZ.-Z., FanY., and WangL.2015. Faster exact computation of rSPR distance. J. Comb. Optim., 29, 605–635.
17.
ColbournC.J., and DinitzJ.H.2006. Handbook of Combinatorial Designs. Second Edition, Chapman and Hall/CRC. Boca Raton, FL, USA.
18.
CritchlowD.E., PearlD.K., and QianC.1996. The triples distance for rooted bifurcating phylogenetic trees. Syst. Biol., 45, 323–334.
19.
DasGuptaB., HeX., JiangT., et al.1997. On distances between phylogenetic trees. Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 427–436.
20.
DayW.H.E.1981. The complexity of computing metric distances between partitions. Math. Soc. Sci., 1, 269–287.
21.
DenœudL.2008. Transfer distance between partitions. Adv. Data Anal. Classification, 2, 279–294.
22.
EstabrookG.F., McMorrisF.R., and MeachamC.A.1985. Comparison of undirected phylogenetic trees based on subtrees of four evolutionary units. Syst. Biol., 34, 193–200.
23.
FindenC.R., and GordonA.D.1985. Obtaining common pruned trees. J. Classification, 2, 255–276.
24.
GabowH.N., and TarjanR.E.1989. Faster scaling algorithms for network problems. SIAM J. Sci. Comput., 18, 1013–1036.
25.
GordonK., FordE., and St. JohnK.2013. Hamiltonian Walks of Phylogenetic Treespaces. IEEE/ACM Trans. Comput. Biol. Bioinform., 10, 1076–1079.
26.
GuénocheA.2011. Consensus of partitions: a constructive approach. Adv. Data Anal. Classif., 5, 215–229.
27.
GusfieldD.2002. Partition-distance: A problem and class of perfect graphs arising in clustering. Inf. Process. Lett., 82, 159–164.
28.
HickeyG., DehneF., Rau-ChaplinA., et al.2008. SPR distance computation for unrooted trees. Evol. Bioinform., 4, 17–27.
29.
HillisD.M., HeathT.A., and St. JohnK.2005. Analysis and visualization of tree space. Syst. Biol., 54, 471–482.
30.
HumphriesP.J., and WuT.2013. On the neighborhoods of trees. IEEE/ACM Trans. Comput. Biol. Bioinform., 10, 721–728.
31.
KirkmanT.P.1847. On a problem in combinatorics. Cambridge Dublin Math. J., 2, 191–204.
32.
KirkpatrickM., and SlatkinM.1993. Searching for evolutionary patterns in the shape of a phylogenetic tree. Evolution, 47, 1171–118.
33.
KonovalovD.A., LitowB., and BajemaN.2005. Partition-distance via the assignment problem. Bioinformatics, 21, 2463–2468.
34.
KooninE.V., PuigbòP., and WolfY.I.2011. Comparison of phylogenetic trees and search for a central trend in the “forest of life.”. J. Comp. Biol., 18, 917–924.
35.
LinH.T., BurleighJ.G., and EulensteinO.2009. Triplet supertree heuristics for the tree of life. BMC Bioinformat. 10(Suppl 1), S8.
36.
McKenzieA., and SteelM.2000. Distributions of cherries for two models of trees. Math. Biosci., 164, 81–92.
37.
OrlinJ.B., and AhujaR.K.1992. New scaling algorithms for the assignment and minimum mean cycle problems. Math. Program., 54, 41–56.
38.
RégnierS.1965. Sur quelques aspects mathématiques des problèmes de classification automatique. I.C.C. Bulletin, 4, 175–191. Reprint in Mathématiques et Sciences Humaines 82, 13–29, 1983.
39.
RobinsonD.F., and FouldsL.R.1981. Comparison of phylogenetic trees. Math. Biosci., 53, 131–147.
40.
SackinM.J.1972. “Good” and “bad” phenograms. Syst. Zool., 21, 225–226.
41.
SempleC., and SteelM.2003. Phylogenetics. Oxford University Press. Oxford, United Kingdom.
42.
ShaoK.-T., and SokalR.R.1990. Tree balance. Syst. Zool., 39, 266–276.
43.
SmithK.C., Castro-NallarE., FisherJ.N.B., et al.2013. Phage cluster relationships identified through single gene analysis. BMC Genomics, 14, 410.
44.
SteelM.A., and PennyD.1993. Distributions of tree comparison metrics–some new results. Syst. Biol., 42, 126–141.
45.
WhiddenC., ZehN., and BeikoR.G.2014. Supertrees based on the subtree prune-and-regraft distance. Syst. Biol., 63, 566–581.
46.
WuY.2009. A practical method for exact computation of subtree prune and regraft distance. Bioinformatics, 25, 190–196.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
