New Gromov-inspired metrics on phylogenetic tree space. (English) Zbl 1391.92032

Summary: We present a new class of metrics for unrooted phylogenetic \(X\)-trees inspired by the Gromov-Hausdorff distance for (compact) metric spaces. These metrics can be efficiently computed by linear or quadratic programming. They are robust under NNI operations, too. The local behaviour of the metrics shows that they are different from any previously introduced metrics. The performance of the metrics is briefly analysed on random weighted and unweighted trees as well as random caterpillars.


92D15 Problems related to evolution
92D10 Genetics and epigenetics
90C90 Applications of mathematical programming
Full Text: DOI


[1] Agarwal PK, Fox K, Nath A, Sidiropoulos A, Wang Y (2015) Computing the Gromov-Hausdorff distance for metric trees. In: Elbassioni K, Makino K (eds) Algorithms and computation. Lecture Notes in Computer Science, vol 9472, pp 529-540. Springer, Berlin. arXiv:1509.05751 · Zbl 1454.68173
[2] Allen, BL; Steel, M, Subtree transfer operations and their induced metrics on evolutionary trees, Ann Comb, 5, 1-15, (2001) · Zbl 0978.05023
[3] Benner, P; Bačak, M; Bourguignon, P-Y, Point estimates in phylogenetic reconstructions, Bioinformatics, 30, i534-i540, (2014)
[4] Berkelaar M et al (2015) lpSolve: Interface to “Lp_solve” v. 5.5 to solve linear/integer programs. R package version 5.6.13. https://CRAN.R-project.org/package=lpSolve
[5] Bernstein DI (2017) L-infinity optimization to Bergman fans of matroids with an application to phylogenetics. arXiv:1702.05141
[6] Bernstein DI, Long C (2017) L-infinity optimization to linear spaces and phylogenetic trees. arXiv:1702.05127 · Zbl 1362.92050
[7] Billera, LJ; Holmes, SP; Vogtmann, K, Geometry of the space of phylogenetic trees, Adv Appl Math, 27, 733-767, (2001) · Zbl 0995.92035
[8] Bogdanowicz, D; Giaro, K, Matching split distance for unrooted binary phylogenetic trees, IEEE/ACM Trans Comput Biol Bioinform, 9, 150-160, (2012)
[9] Bonet, ML; St. John, K, On the complexity of uspr distance, IEEE/ACM Trans Comput Biol Bioinform, 7, 572-576, (2010)
[10] Bourque M (1978) Arbres de Steiner et reseaux dont certains sommets sont a localisation variable. PhD thesis, Montreal
[11] Brodal GS, Fagerberg R, Pedersen CNS (2001) Computing the quartet distance between evolutionary trees on time \({\rm O}(n\log ^2n)\). In: Proceedings of the 12th international symposium on algorithms and computation (ISAAC). Lecture Notes in Computer Science, vol 2223, pp 731-737. Springer · Zbl 1077.92513
[12] Buneman, P; Kendall, DG (ed.); Tautu, P (ed.), The recovery of trees from measures of dissimilarity, 387-395, (1971), Edinburgh
[13] Buneman, P, A note on the metric properties of trees, J Comb Theory, 17, 48-50, (1974) · Zbl 0286.05102
[14] Burago D, Burago Y, Ivanov S (2001) A course in metric geometry. Graduate studies in mathematics, vol 33. American Mathematical Society, Providence · Zbl 0981.51016
[15] Chakerian J, Holmes S (2017) Distory: distance between phylogenetic histories. R package version 1.4.3. http://CRAN.R-project.org/package=distory · Zbl 1370.05040
[16] Coons, JI; Rusinko, J, A note on the path interval distance, J Theor Biol, 398, 145-149, (2016) · Zbl 1343.92337
[17] Cristina J (2008) Gromov-Hausdorff convergence of metric spaces, Helsinki. http://www.helsinki.fi/ cristina/pdfs/gromovHausdorff.pdf. Accessed 2 Feb 2015 · Zbl 1338.92078
[18] DasGupta B, He X, Jiang T, Li M, Tromp J, Zhang L (1997) On distances between phylogenetic trees. In: Proceedings of the eighth ACM/SIAM symposium discrete algorithms (SODA ’97), pp 427-436 · Zbl 1321.92061
[19] Day, WHE, Optimal algorithms for comparing trees with labeled leaves, J Classif, 2, 7-28, (1985) · Zbl 0589.62044
[20] Dress, A, Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces, Adv Math, 53, 321-402, (1984) · Zbl 0562.54041
[21] Dress, A; Holland, B; Huber, KT; Koolen, J; Moulton, V; Weyer-Menkoff, J, \(Δ \)-additive and \(Δ \)-ultra-additive maps, gromov’s trees and the farris transform, Discrete Appl Math, 146, 51-73, (2005) · Zbl 1056.92042
[22] Edwards, DA; Stavrakas, NM (ed.); Allen, KR (ed.), The structure of superspace, 121-133, (1975), New York
[23] Estabrook, GF; McMorris, FR; Meacham, CA, Comparison of undirected phylogenetic trees based on subtrees of four evolutionary units, Syst Zool, 34, 193-200, (1985)
[24] Fischer, M; Kelk, S, On the maximum parsimony distance between phylogenetic trees, Ann Comb, 20, 87-113, (2016) · Zbl 1332.05043
[25] Gavryushkin, A; Drummond, A, The space of ultrametric phylogenetic trees, J Theor Biol, 403, 197-208, (2016) · Zbl 1343.92343
[26] Gromov, M, Groups of polynomial growth and expanding maps, Publ Math IHÉS, 53, 53-73, (1981) · Zbl 0474.20018
[27] Guénoche, A; Leclerc, B; Makarenkov, V, On the extension of a partial metric to a tree metric, Discrete Math, 276, 229-248, (2004) · Zbl 1031.05043
[28] Hoffman, AJ; Kruskal, J; Jünger, M (ed.); etal., Introduction to integral boundary points of convex polyhedra, 49-50, (2010), Berlin
[29] Huggins, P; Owen, M; Yoshida, R; Hibi, T (ed.), First steps toward the geometry of cophylogeny, 99-116, (2012), Singapore · Zbl 1338.92078
[30] Isbell, JR, Six theorems about injective metric spaces, Commun Math Helv, 39, 65-76, (1964) · Zbl 0151.30205
[31] Karmarkar, N, A new polynomial-time algorithm for linear programming, Combinatorica, 4, 373-395, (1984) · Zbl 0557.90065
[32] Kelk, S; Fischer, M, On the complexity of computing MP distance between binary phylogenetic trees, Ann Comb, 21, 573-604, (2017) · Zbl 1380.05069
[33] Kendall, M; Colijn, C, Mapping phylogenetic trees to reveal distinct patterns of evolution, Mol Biol Evol, 33, 2735-2743, (2016)
[34] Lang, U; Pavón, M; Züst, R, Metric stability of trees and tight spans, Arch Math, 101, 91-100, (2013) · Zbl 1272.53033
[35] Liebscher V (2015) gromovlab: Gromov-Hausdorff type distances for labeled metric spaces. R package version 0.7-6. http://CRAN.R-project.org/package=gromovlab · Zbl 1332.05043
[36] Lin, Y; Rajan, V; Moret, BME, A metric for phylogenetic trees based on matching, IEEE/ACM Trans Comput Biol Bioinform, 9, 1014-1022, (2012)
[37] Lin, B; Sturmfels, B; Tang, X; Yoshida, R, Convexity in tree spaces, SIAM J Discrete Math, 31, 2015-2038, (2017) · Zbl 1370.05040
[38] Mémoli F (2007) On the use of Gromov-Hausdorff distances for shape comparison. In: Symposium on point based graphics, Prague, Sept 2007 · Zbl 1272.53033
[39] Moulton, V; Wu, T, A parsimony-based metric for phylogenetic trees, Adv Appl Math, 66, 22-45, (2015) · Zbl 1315.05034
[40] Nye, TMW, Principal components analysis in the space of phylogenetic trees, Ann Stat, 39, 2716-2739, (2011) · Zbl 1231.62110
[41] Owen, M; Provan, J, A fast algorithm for computing geodesic distances in tree space, IEEE/ACM Trans Comput Biol Bioinform, 8, 2-13, (2011)
[42] Paradis, E; Claude, J; Strimmer, K, APE: analyses of phylogenetics and evolution in R language, Bioinformatics, 20, 289-290, (2004)
[43] Pardalos PM, Wolkowicz H (eds) (1994) Quadratic assignment and related problems. DIMACS series in discrete mathematics and theoretical computer science, vol 16. AMS, Providence, RI. Papers from the workshop held at Rutgers University, New Brunswick, New Jersey, May 20-21, 1993 · Zbl 1333.68297
[44] Pattengale, ND; Gottlieb, EJ; Moret, BM, Efficiently computing the Robinson-Foulds metric, J Comput Biol, 14, 724-735, (2007)
[45] Penny, D; Hendy, MD, The use of tree comparison metrics, Syst Biol, 34, 75-82, (1985)
[46] R Core Team (2017) R: a language and environment for statistical computing. R Foundation for Statistical Computing, version 3.4.3, Vienna, Austria. http://www.R-project.org/ · Zbl 0451.92006
[47] Robinson, DF, Comparison of labeled trees with valency three, J Comb Theory, 11, 105-119, (1971)
[48] Robinson DF, Foulds LR (1979) Comparison of weighted labelled trees. In: Combinatorial mathematics VI. Lecture Notes in Mathematics, vol 748, pp 119-126. Springer, Berlin
[49] Robinson, DF; Foulds, LR, Comparison of phylogenetic trees, Math Biosci, 53, 131-147, (1981) · Zbl 0451.92006
[50] Semple C, Steel MA (2003) Phylogenetics. Oxford University Press, Oxford · Zbl 1043.92026
[51] Sokal, RR; Rohlf, FJ, The comparison of dendrograms by objective methods, Taxon, 11, 33-40, (1962)
[52] Steel, MA; Penny, D, Distributions of tree comparison metrics—some new results, Syst Biol, 42, 126-141, (1993)
[53] Tuzhilin AA (2016) Who invented the Gromov-Hausdorff distance? arXiv:1612.00728
[54] Villar S, Bandeira AS, Blumberg AJ, Ward R (2016) A polynomial-time relaxation of the Gromov-Hausdorff distance. arXiv:1610.05214
[55] Whidden, C; Beiko, RG; Zeh, N, Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees, Algorithmica, 74, 1019-1054, (2016) · Zbl 1333.68297
[56] Williams, WT; Clifford, HT, On the comparison of two classifications of the same set of elements, Taxon, 20, 519-522, (1971)
[57] Zaretskii, KA, Constructing a tree on the basis of a set of distances between the hanging vertices (in Russian), Uspekhi Mat Nauk, 20, 90-92, (1965)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.