text: In order to develop statistical methods for shapes with a tree-structure, we construct a shape space framework for tree-like shapes and study metrics on the shape space. This shape space has singularities, corresponding to topological transitions in the represented trees. We study two closely related metrics on the shape space, TED and QED. QED is a quotient Euclidean distance arising naturally from the shape space formulation, while TED is the classical tree edit distance. Using Gromov's metric geometry we gain new insight into the geometries defined by TED and QED. We show that the new metric QED has nice geometric properties which facilitate statistical analysis, such as existence and local uniqueness of geodesics and averages. TED, on the other hand, does not share the geometric advantages of QED, but has nice algorithmic properties. We provide a theoretical framework and experimental results on synthetic data trees as well as airway trees from pulmonary CT scans. This way, we effectively illustrate that our framework has both the theoretical and qualitative properties necessary to build a theory of statistical tree-shape analysis.
  @cite_28: We explored the use of multidimensional scaling (MDS) of tree-to-tree pairwise distances to visualize the re- lationships among sets of phylogenetic trees. We found the technique to be useful for exploring "tree islands" (sets of topologically related trees among larger sets of near-optimal trees), for comparing sets of trees obtained from bootstrapping and Bayesian sampling, for comparing trees obtained from the analysis of several different genes, and for comparing mul- tiple Bayesian analyses. The technique was also useful as a teaching aid for illustrating the progress of a Bayesian analysis and as an exploratory tool for examining large sets of phylogenetic trees. We also identified some limitations to the method, including distortions of the multidimensional tree space into two dimensions through the MDS technique, and the defini- tion of the MDS-defined space based on a limited sample of trees. Nonetheless, the technique is a useful approach for the analysis of large sets of phylogenetic trees. (Bayesian analysis; multidimensional scaling; phylogenetic analysis; tree space; visualization.) Systematists are often faced with the need to analyze a large collection of phylogenetic trees. These trees may represent a collection of equally parsimonious solutions to a phylogenetic problem, or a set of trees of similar likelihood, or a sampled set of trees from a Markov chain Monte Carlo (MCMC) Bayesian analysis. In any of these cases, a common approach for expressing the results is to make a consensus tree from the large col- lection of potential solutions (see Swofford, 1991, for a discussion of consensus methods). Consensus trees are produced to distill a large amount of information into a single summary tree, because it is often impractical to examine or display all of the individual solutions. In the case of MCMC Bayesian analysis, a consensus tree is usually used to summarize information about the pos- terior probabilities of the individual inferred branches. Although these uses of consensus trees may be ap- propriate for many purposes, a great deal of informa- tion about the individual solutions is usually lost. It is possible that two or more distinct but different bi- ological explanations are represented among different "islands" of solutions (e.g., see Maddison, 1991), but that a consensus of these solutions produces little or no resolution. Although many other solutions among the universe of possible trees may be excluded by the avail- able data, this information can be lost in a consensus tree.
  @cite_9: Comparing and computing distances between phylogenetic trees are important biological problems, especially for models where edge lengths play an important role. The geodesic distance measure between two phylogenetic trees with edge lengths is the length of the shortest path between them in the continuous tree space introduced by Billera, Holmes, and Vogtmann. This tree space provides a powerful tool for studying and comparing phylogenetic trees, both in exhibiting a natural distance measure and in providing a euclidean-like structure for solving optimization problems on trees. An important open problem is to find a polynomial time algorithm for finding geodesics in tree space. This paper gives such an algorithm, which starts with a simple initial path and moves through a series of successively shorter paths until the geodesic is attained.
  @cite_30: We consider a continuous space which models the set of all phylogenetic trees having a fixed set of leaves. This space has a natural metric of nonpositive curvature, giving a way of measuring distance between phylogenetic trees and providing some procedures for averaging or combining several trees whose leaves are identical. This geometry also shows which trees appear within a fixed distance of a given tree and enables construction of convex hulls of a set of trees. This geometric model of tree space provides a setting in which questions that have been posed by biologists and statisticians over the last decade can be approached in a systematic fashion. For example, it provides a justification for disregarding portions of a collection of trees that agree, thus simplifying the space in which comparisons are to be made.
  @cite_23: Phylogenetic analysis of DNA or other data commonly gives rise to a collection or sample of inferred evolutionary trees. Principal Components Analysis (PCA) cannot be applied directly to collections of trees since the space of evolutionary trees on a fixed set of taxa is not a vector space. This paper describes a novel geometrical approach to PCA in tree-space that constructs the first principal path in an analogous way to standard linear Euclidean PCA. Given a data set of phylogenetic trees, a geodesic principal path is sought that maximizes the variance of the data under a form of projection onto the path. Due to the high dimensionality of tree-space and the nonlinear nature of this problem, the computational complexity is potentially very high, so approximate optimization algorithms are used to search for the optimal path. Principal paths identified in this way reveal and quantify the main sources of variation in the original collection of trees in terms of both topology and branch lengths. The approach is illustrated by application to simulated sets of trees and to a set of gene trees from metazoan (animal) species.
summary: Trees also appear in genetics. @cite_28 visualize large sets of phylogenetic trees using multidimensional scaling. @cite_30 have invented a phylogenetic tree-space suitable for geodesic analysis of phylogenetic trees, and Owen and Provan @cite_9 have developed fast algorithms for computing geodesics in phylogenetic tree-space. Nye @cite_23 has developed a notion of PCA in phylogenetic tree-space, but is forced to make strict assumptions on possible principle components being ''simple lines'' for the sake of computability. Phylogenetic trees are not geometric, and have fixed, labeled leaf sets, making the space of phylogenetic trees much simpler than the space of tree-like shapes.