1
|
Abstract
We propose a new space of phylogenetic trees which we call wald space. The motivation is to develop a space suitable for statistical analysis of phylogenies, but with a geometry based on more biologically principled assumptions than existing spaces: in wald space, trees are close if they induce similar distributions on genetic sequence data. As a point set, wald space contains the previously developed Billera–Holmes–Vogtmann (BHV) tree space; it also contains disconnected forests, like the edge-product (EP) space but without certain singularities of the EP space. We investigate two related geometries on wald space. The first is the geometry of the Fisher information metric of character distributions induced by the two-state symmetric Markov substitution process on each tree. Infinitesimally, the metric is proportional to the Kullback–Leibler divergence, or equivalently, as we show, to any f-divergence. The second geometry is obtained analogously but using a related continuous-valued Gaussian process on each tree, and it can be viewed as the trace metric of the affine-invariant metric for covariance matrices. We derive a gradient descent algorithm to project from the ambient space of covariance matrices to wald space. For both geometries we derive computational methods to compute geodesics in polynomial time and show numerically that the two information geometries (discrete and continuous) are very similar. In particular, geodesics are approximated extrinsically. Comparison with the BHV geometry shows that our canonical and biologically motivated space is substantially different.
Collapse
|
2
|
Brown DG, Owen M. Mean and Variance of Phylogenetic Trees. Syst Biol 2019; 69:139-154. [DOI: 10.1093/sysbio/syz041] [Citation(s) in RCA: 5] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/02/2017] [Revised: 05/13/2019] [Accepted: 05/24/2019] [Indexed: 11/13/2022] Open
Abstract
Abstract
We describe the use of the Fréchet mean and variance in the Billera–Holmes–Vogtmann (BHV) treespace to summarize and explore the diversity of a set of phylogenetic trees. We show that the Fréchet mean is comparable to other summary methods, and, despite its stickiness property, is more likely to be binary than the majority-rule consensus tree. We show that the Fréchet variance is faster and more precise than commonly used variance measures. The Fréchet mean and variance are more theoretically justified, and more robust, than previous estimates of this type and can be estimated reasonably efficiently, providing a foundation for building more advanced statistical methods and leading to applications such as mean hypothesis testing and outlier detection.
Collapse
Affiliation(s)
- Daniel G Brown
- David R. Cheriton School of Computer Science, University of Waterloo, 200 University Ave. W, Waterloo ON N2L 3G1, Canada
| | - Megan Owen
- Department of Mathematics, Lehman College, City University of New York, 250 Bedford Park Blvd West, Bronx, New York, NY 10468, USA
| |
Collapse
|
3
|
|
4
|
Yoshida R, Zhang L, Zhang X. Tropical Principal Component Analysis and Its Application to Phylogenetics. Bull Math Biol 2018; 81:568-597. [PMID: 30206809 DOI: 10.1007/s11538-018-0493-4] [Citation(s) in RCA: 8] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/07/2017] [Accepted: 08/24/2018] [Indexed: 10/28/2022]
Abstract
Principal component analysis is a widely used method for the dimensionality reduction of a given data set in a high-dimensional Euclidean space. Here we define and analyze two analogues of principal component analysis in the setting of tropical geometry. In one approach, we study the Stiefel tropical linear space of fixed dimension closest to the data points in the tropical projective torus; in the other approach, we consider the tropical polytope with a fixed number of vertices closest to the data points. We then give approximative algorithms for both approaches and apply them to phylogenetics, testing the methods on simulated phylogenetic data and on an empirical dataset of Apicomplexa genomes.
Collapse
Affiliation(s)
- Ruriko Yoshida
- Naval Postgraduate School, 1411 Cunningham Road, Monterey, CA, 93943-5219, USA.
| | - Leon Zhang
- University of California, Berkeley, 1042 Evans Hall, Berkeley, CA, 94720-3840, USA
| | - Xu Zhang
- University of Kentucky, 725 Rose Street, Multidisciplinary Science Building 0082, Room 311, Lexington, KY, 40536-0082, USA
| |
Collapse
|
5
|
Duncan A, Klassen E, Srivastava A. Statistical shape analysis of simplified neuronal trees. Ann Appl Stat 2018. [DOI: 10.1214/17-aoas1107] [Citation(s) in RCA: 11] [Impact Index Per Article: 1.8] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/19/2022]
|
6
|
Nye TMW, Tang X, Weyenberg G, Yoshida R. Principal component analysis and the locus of the Fréchet mean in the space of phylogenetic trees. Biometrika 2017; 104:901-922. [PMID: 29422694 PMCID: PMC5793493 DOI: 10.1093/biomet/asx047] [Citation(s) in RCA: 18] [Impact Index Per Article: 2.6] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/10/2016] [Indexed: 11/13/2022] Open
Abstract
Evolutionary relationships are represented by phylogenetic trees, and a phylogenetic
analysis of gene sequences typically produces a collection of these trees, one for each
gene in the analysis. Analysis of samples of trees is difficult due to the
multi-dimensionality of the space of possible trees. In Euclidean spaces, principal
component analysis is a popular method of reducing high-dimensional data to a
low-dimensional representation that preserves much of the sample’s structure. However, the
space of all phylogenetic trees on a fixed set of species does not form a Euclidean vector
space, and methods adapted to tree space are needed. Previous work introduced the notion
of a principal geodesic in this space, analogous to the first principal component. Here we
propose a geometric object for tree space similar to the \documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{upgreek}
\usepackage{mathrsfs}
\setlength{\oddsidemargin}{-69pt}
\begin{document}
}{}$k$\end{document}th
principal component in Euclidean space: the locus of the weighted Fréchet mean of
\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{upgreek}
\usepackage{mathrsfs}
\setlength{\oddsidemargin}{-69pt}
\begin{document}
}{}$k+1$\end{document} vertex trees when the weights vary over
the \documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{upgreek}
\usepackage{mathrsfs}
\setlength{\oddsidemargin}{-69pt}
\begin{document}
}{}$k$\end{document}-simplex. We establish some basic properties
of these objects, in particular showing that they have dimension \documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{upgreek}
\usepackage{mathrsfs}
\setlength{\oddsidemargin}{-69pt}
\begin{document}
}{}$k$\end{document}, and
propose algorithms for projection onto these surfaces and for finding the principal locus
associated with a sample of trees. Simulation studies demonstrate that these algorithms
perform well, and analyses of two datasets, containing Apicomplexa and African coelacanth
genomes respectively, reveal important structure from the second principal components.
Collapse
Affiliation(s)
- Tom M W Nye
- School of Mathematics and Statistics, Newcastle University, Newcastle upon Tyne NE1 7RU,
| | - Xiaoxian Tang
- Department of Mathematics, Texas A&M University, College Station, Texas 77843,
| | - Grady Weyenberg
- Department of Mathematics, University of Hawaii at Hilo, Hilo, Hawaii 96720,
| | - Ruriko Yoshida
- Department of Operations Research, Naval Postgraduate School, Monterey, California 93943,
| |
Collapse
|
7
|
St. John K. Review Paper: The Shape of Phylogenetic Treespace. Syst Biol 2017; 66:e83-e94. [PMID: 28173538 PMCID: PMC5837343 DOI: 10.1093/sysbio/syw025] [Citation(s) in RCA: 11] [Impact Index Per Article: 1.6] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/20/2015] [Revised: 12/16/2015] [Accepted: 03/22/2016] [Indexed: 11/23/2022] Open
Abstract
Trees are a canonical structure for representing evolutionary histories. Many popular criteria used to infer optimal trees are computationally hard, and the number of possible tree shapes grows super-exponentially in the number of taxa. The underlying structure of the spaces of trees yields rich insights that can improve the search for optimal trees, both in accuracy and in running time, and the analysis and visualization of results. We review the past work on analyzing and comparing trees by their shape as well as recent work that incorporates trees with weighted branch lengths.
Collapse
Affiliation(s)
- Katherine St. John
- Department of Mathematics and Computer Science, Lehman College, NY 10034, USA
| |
Collapse
|
8
|
Barden D, Le H, Owen M. Limiting behaviour of Fréchet means in the space of phylogenetic trees. ANN I STAT MATH 2016. [DOI: 10.1007/s10463-016-0582-9] [Citation(s) in RCA: 10] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/30/2022]
|
9
|
Hauberg S. Principal Curves on Riemannian Manifolds. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2016; 38:1915-1921. [PMID: 26540674 DOI: 10.1109/tpami.2015.2496166] [Citation(s) in RCA: 7] [Impact Index Per Article: 0.9] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/05/2023]
Abstract
Euclidean statistics are often generalized to Riemannian manifolds by replacing straight-line interpolations with geodesic ones. While these Riemannian models are familiar-looking, they are restricted by the inflexibility of geodesics, and they rely on constructions which are optimal only in Euclidean domains. We consider extensions of Principal Component Analysis (PCA) to Riemannian manifolds. Classic Riemannian approaches seek a geodesic curve passing through the mean that optimizes a criteria of interest. The requirements that the solution both is geodesic and must pass through the mean tend to imply that the methods only work well when the manifold is mostly flat within the support of the generating distribution. We argue that instead of generalizing linear Euclidean models, it is more fruitful to generalize non-linear Euclidean models. Specifically, we extend the classic Principal Curves from Hastie & Stuetzle to data residing on a complete Riemannian manifold. We show that for elliptical distributions in the tangent of spaces of constant curvature, the standard principal geodesic is a principal curve. The proposed model is simple to compute and avoids many of the pitfalls of traditional geodesic approaches. We empirically demonstrate the effectiveness of the Riemannian principal curves on several manifolds and datasets.
Collapse
|
10
|
Feragen A, Petersen J, Owen M, Hohwu Thomsen L, Wille MMW, Dirksen A, de Bruijne M. Geodesic Atlas-Based Labeling of Anatomical Trees: Application and Evaluation on Airways Extracted From CT. IEEE TRANSACTIONS ON MEDICAL IMAGING 2015; 34:1212-1226. [PMID: 25532169 DOI: 10.1109/tmi.2014.2380991] [Citation(s) in RCA: 8] [Impact Index Per Article: 0.9] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/04/2023]
Abstract
We present a fast and robust atlas-based algorithm for labeling airway trees, using geodesic distances in a geometric tree-space. Possible branch label configurations for an unlabeled airway tree are evaluated using distances to a training set of labeled airway trees. In tree-space, airway tree topology and geometry change continuously, giving a natural automatic handling of anatomical differences and noise. A hierarchical approach makes the algorithm efficient, assigning labels from the trachea and downwards. Only the airway centerline tree is used, which is relatively unaffected by pathology. The algorithm is evaluated on 80 segmented airway trees from 40 subjects at two time points, labeled by three medical experts each, testing accuracy, reproducibility and robustness in patients with chronic obstructive pulmonary disease (COPD). The accuracy of the algorithm is statistically similar to that of the experts and not significantly correlated with COPD severity. The reproducibility of the algorithm is significantly better than that of the experts, and negatively correlated with COPD severity. Evaluation of the algorithm on a longitudinal set of 8724 trees from a lung cancer screening trial shows that the algorithm can be used in large scale studies with high reproducibility, and that the negative correlation of reproducibility with COPD severity can be explained by missing branches, for instance due to segmentation problems in COPD patients. We conclude that the algorithm is robust to COPD severity given equally complete airway trees, and comparable in performance to that of experts in pulmonary medicine, emphasizing the suitability of the labeling algorithm for clinical use.
Collapse
|
11
|
Quantification and Visualization of Variation in Anatomical Trees. ASSOCIATION FOR WOMEN IN MATHEMATICS SERIES 2015. [DOI: 10.1007/978-3-319-16348-2_5] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 01/26/2023]
|
12
|
Nye TMW. An Algorithm for Constructing Principal Geodesics in Phylogenetic Treespace. IEEE/ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2014; 11:304-315. [PMID: 26355778 DOI: 10.1109/tcbb.2014.2309599] [Citation(s) in RCA: 7] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/05/2023]
Abstract
Most phylogenetic analyses result in a sample of trees, but summarizing and visualizing these samples can be challenging. Consensus trees often provide limited information about a sample, and so methods such as consensus networks, clustering and multidimensional scaling have been developed and applied to tree samples. This paper describes a stochastic algorithm for constructing a principal geodesic or line through treespace which is analogous to the first principal component in standard principal components analysis. A principal geodesic summarizes the most variable features of a sample of trees, in terms of both tree topology and branch lengths, and it can be visualized as an animation of smoothly changing trees. The algorithm performs a stochastic search through parameter space for a geodesic which minimizes the sum of squared projected distances of the data points. This procedure aims to identify the globally optimal principal geodesic, though convergence to locally optimal geodesics is possible. The methodology is illustrated by constructing principal geodesics for experimental and simulated data sets, demonstrating the insight into samples of trees that can be gained and how the method improves on a previously published approach. A java package called GeoPhytter for constructing and visualizing principal geodesics is freely available from www.ncl.ac.uk/ ntmwn/geophytter.
Collapse
|