Polyhedral computational geometry for averaging metric phylogenetic trees. (English) Zbl 1329.68266
Summary: This paper investigates the computational geometry relevant to calculations of the Fréchet mean and variance for probability distributions on the phylogenetic tree space of L. J. Billera et al. [ibid. 27, No. 4, 733–767 (2001; Zbl 0995.92035); erratum ibid. 29, No. 1, 136 (2002)], using the theory of probability measures on spaces of nonpositive curvature developed by Sturm. We show that the combinatorics of geodesics with a specified fixed endpoint in tree space are determined by the location of the varying endpoint in a certain polyhedral subdivision of tree space. The variance function associated to a finite subset of tree space has a fixed \(C^\infty\) algebraic formula within each cell of the corresponding subdivision, and is continuously differentiable in the interior of each orthant of tree space. We use this subdivision to establish two iterative methods for producing sequences that converge to the Fréchet mean: one based on Sturm’s Law of Large Numbers, and another based on descent algorithms for finding optima of smooth functions on convex polyhedra. We present properties and biological applications of Fréchet means and extend our main results to more general globally nonpositively curved spaces composed of Euclidean orthants.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 05C05 | Trees |
| 52B55 | Computational aspects related to convexity |
| 53C23 | Global geometric and topological methods (à la Gromov); differential geometric analysis on metric spaces |
| 60B05 | Probability measures on topological spaces |
| 62P10 | Applications of statistics to biology and medical sciences; meta analysis |
| 92D15 | Problems related to evolution |
Keywords:
tree space; Fréchet mean; polyhedral subdivision; descent method; phylogenetics; nonpositively curved spaceCitations:
Zbl 0995.92035References:
| [1] | Adams, E. N., Consensus techniques and the comparison of taxonomic trees, Syst. Zool., 21, 390-397 (1972) |
| [2] | Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows: Theory, Algorithms, and Applications (1993), Prentice Hall: Prentice Hall Upper Saddle River, NJ · Zbl 1201.90001 |
| [3] | Ardila, F.; Owen, M.; Sullivant, S., Geodesics in \(CAT(0)\) cubical complexes, Adv. in Appl. Math., 48, 142-163 (2012) · Zbl 1275.05055 |
| [4] | Bačák, M., Computing medians and means in Hadamard space, SIAM J. Optim., 24, 1542-1566 (2014) · Zbl 1306.49046 |
| [5] | Barrett, M.; Donoghue, M.; Sober, E., Against consensus, Syst. Zool., 40, 486-493 (1991) |
| [6] | Basrak, B., Limit theorems for the inductive mean on metric trees, J. Appl. Probab., 47, 1136-1149 (2010) · Zbl 1219.60019 |
| [7] | Billera, L.; Holmes, S.; Vogtmann, K., Geometry of the space of phylogenetic trees, Adv. in Appl. Math., 27, 733-767 (2001) · Zbl 0995.92035 |
| [8] | Bridson, M.; Haefliger, A., Metric Spaces of Non-Positive Curvature (1999), Springer-Verlag: Springer-Verlag New York · Zbl 0988.53001 |
| [9] | Bryant, David, A classification of consensus methods for phylogenetics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 61, 163-183 (2003) · Zbl 1029.05032 |
| [10] | Chakerian, J.; Holmes, S., Computational tools for evaluating phylogenetic and hierarchical clustering trees, J. Comput. Graph. Statist., 21, 581-599 (2012) |
| [11] | Cranston, K. A.; Rannala, B., Summarizing a posterior distribution of trees using agreement subtrees, Syst. Biol., 56, 578-590 (2007) |
| [12] | Degnan, J.; Rosenberg, N., Discordance of species trees with their most likely gene trees, PLoS Genet., 3, 762-768 (2006) |
| [13] | Edwards, S. V.; Liu, L.; Pearl, D. K., High-resolution species trees without concatenation, Proc. Natl. Acad. Sci., 104, 5936-5941 (2007) |
| [14] | Feragen, A.; Owen, M.; Petersen, J.; Wille, M. M.W.; Thomsen, L. H.; Dirksen, A.; de Bruijne, M., Tree-space statistics and approximations for large-scale analysis of anatomical trees, Inf. Process. Med. Imag., 23, 74-85 (2013) |
| [15] | Gromov, M., Hyperbolic groups, (Gersten, S., Essays in Group Theory (1987), Springer-Verlag: Springer-Verlag New York), 75-263 · Zbl 0634.20015 |
| [16] | Holmes, S., Statistics for phylogenetic trees, Theor. Popul. Biol., 63, 17-32 (2003) · Zbl 1101.92305 |
| [17] | Holmes, S., Statistical approach to tests involving phylogenetics, (Gascuel, O., Mathematics of Evolution and Phylogeny (2005), Oxford University Press), 91-120 · Zbl 1090.62123 |
| [18] | Hotz, T.; Huckemann, S.; Le, H.; Marron, J. S.; Mattingly, J. C.; Miller, E.; Nolen, J.; Owen, M.; Skwerer, S.; Patrangenaru, V., Sticky central limit theorems on open books, Ann. Appl. Probab., 23, 2238-2258 (2013) · Zbl 1293.60006 |
| [19] | Maddison, W. P., Gene trees in species trees, Syst. Biol., 46, 523-536 (1997) |
| [20] | Margush, T.; McMorris, F. R., Consensus \(n\)-trees, Bull. Math. Biol., 43, 239-244 (1981) · Zbl 0455.92019 |
| [21] | Miller, E.; Pak, I., Metric combinatorics of convex polyhedra: cut loci and nonoverlapping unfoldings, Discrete Comput. Geom., 39, 339-388 (2008) · Zbl 1140.52008 |
| [22] | Mitchell, J. S.B., Geometric shortest paths and network optimization, (Sack, J.-R.; Urrutia, J., Handbook of Computational Geometry (2000), Elsevier: Elsevier Amsterdam), 633-701 · Zbl 0941.68137 |
| [23] | Munkres, J. R., Elements of Algebraic Topology (1984), Addison-Wesley: Addison-Wesley Menlo Park, CA · Zbl 0673.55001 |
| [24] | Nye, T. M.W., Principal components analysis in the space of phylogenetic trees, Ann. Statist., 39, 2716-2739 (2011) · Zbl 1231.62110 |
| [25] | Owen, M., Computing geodesic distances in tree space, SIAM J. Discrete Math., 25, 1506-1529 (2011) · Zbl 1237.05045 |
| [26] | Owen, M., Sturm algorithm implementation |
| [27] | Owen, M.; Provan, J. S., A fast algorithm for computing geodesic distance in tree space, IEEE/ACM Trans. Comput. Biol. Bioinform., 8, 2-13 (2011) |
| [28] | Picard, J.-C.; Queyranne, M., On the structure of all minimum cuts in a network and applications, Math. Program., 13, 8-16 (1980) · Zbl 0442.90093 |
| [29] | Rokas, A.; Williams, B. L.; King, N.; Carroll, S. B., Genome-scale approaches to resolving incongruence in molecular phylogenies, Nature, 425, 798-804 (2003) |
| [30] | Semple, C.; Steel, M., Phylogenetics (2003), Oxford University Press: Oxford University Press Oxford · Zbl 1043.92026 |
| [31] | Skwerer, S.; Bullitt, E.; Huckemann, S.; Miller, E.; Oguz, I.; Owen, M.; Patrangenaru, V.; Provan, S.; Marron, J. S., Tree-oriented analysis of brain artery structure, J. Math. Imaging Vision, 50, 126-143 (2014) · Zbl 1303.92054 |
| [32] | Sturm, K.-T., Probability measures on metric spaces of nonpositive curvature, (Auscher, P.; Coulhon, T.; Grigoryan, A., Heat Kernels and Analysis on Manifolds, Graphs, and Metric Spaces: Lecture Notes from a Quarter Program on Heat Kernels, Random Walks, and Analysis on Manifolds and Graphs. Heat Kernels and Analysis on Manifolds, Graphs, and Metric Spaces: Lecture Notes from a Quarter Program on Heat Kernels, Random Walks, and Analysis on Manifolds and Graphs, Contemp. Math., vol. 338 (2003), American Mathematics Society: American Mathematics Society USA), 357-390 · Zbl 1040.60002 |
| [34] | Ziegler, G. M., Lectures on Polytopes, Grad. Texts in Math., vol. 152 (1995), Springer: Springer New York · Zbl 0823.52002 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
