Skip to content

Review: Geometry of the Space of Phylogenetic Trees

Citation

  • Billera, L. J., Holmes, S. P., & Vogtmann, K. (2001). Geometry of the space of phylogenetic trees. Advances in Applied Mathematics, 27(4), 733–767.
  • DOI

Abstract

The space of phylogenetic trees on \( n \) labeled leaves is given the structure of a polyhedral cone complex, in which each orthant corresponds to one tree topology. The complex has a natural metric, and geodesics between trees can be computed explicitly. Properties of this space relevant to statistics on trees are described, including the existence and uniqueness of Fréchet means.

A phylogenetic tree is not a point in Euclidean space: different tree topologies are qualitatively different objects, and naive parameterizations do not give a space with useful geometric properties. Billera, Holmes, and Vogtmann (2001) define a metric space of phylogenetic trees, now called BHV tree space, that treats both topology and branch lengths continuously and has provably nice geometric properties.

The construction starts from the observation that an unrooted binary tree on \( n \) leaves has \( n - 3 \) internal branches, each with a non-negative length. Fixing a topology and varying branch lengths traces out the non-negative orthant \( \mathbb{R}_{\geq 0}^{n-3} \). BHV space is the union of all such orthants (one per topology) glued together at their boundaries: when an internal branch length goes to zero, the corresponding internal edge collapses and the tree is on the boundary between two adjacent topologies. Orthants are glued precisely along these boundaries, producing a polyhedral cone complex with a locally Euclidean metric within each orthant.

The key geometric property is that geodesic paths between any two points in BHV space exist and are unique. Computing a geodesic means finding the path of minimum length that may pass through several topology-orthants. The paper gives an algorithm for doing so explicitly, and shows that this metric coincides with the natural sense in which two trees that differ by a small NNI or branch-length perturbation are "close."

Hifuku does not compute the full BHV geodesic. Its tree metric is the normalized clade branch score combined with the Robinson-Foulds count (Section 5), a Euclidean-embeddable approximation to tree-space distance that is much cheaper to evaluate. The three pairwise anchor distances are embedded in a local Euclidean plane by classical multidimensional scaling, which gives the two-dimensional chart (Section 6). BHV geometry is what makes that plane only a local chart: tree space is non-positively curved (CAT(0)) and globally non-Euclidean, so the flat chart is faithful only where the sampled region is approximately flat, and the out-of-plane residual \( z \) (Section 7) measures the departure.

BHV geometry also gives the Robinson-Foulds reading of orthant adjacencies: an NNI move corresponds to crossing from one orthant to an adjacent one through a codimension-1 face, which is why NNI is a natural topology-changing move in tree space.

Key result

Theorem (Billera et al., Theorem 4.1). For any two trees in BHV space there exists a unique geodesic, and it can be computed explicitly in polynomial time. The space is non-positively curved (CAT(0)), so the Fréchet mean (barycenter) of any finite set of trees exists and is unique.