Geometry of the space of phylogenetic trees with non-identical leaves
MARÍA A. VALDEZ-CABRERA, AMY D. WILLIS · 2025
Read Geometry of the space of phylogenetic trees with non-identical leaves by MARÍA A. VALDEZ-CABRERA, AMY D. WILLIS (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-06747.txt.
Introduction
Maria Alejandra Valdez Cabrera and Amy Willis build a new math space for family trees of species, in a 2025 paper. Such trees show how species relate through evolution. A well-known space for comparing them has strong math traits. It fails, though, when the trees cover different sets of species.
Their new space, called Towering space, extends the old one. It links many copies of the old space through steps that cut or rejoin branches. The authors study the shape of paths in the new space. They also give a method to compute distances between trees there. Modern data sets, such as gene trees that span many groups of life, need this wider reach. The work opens those sets to the tools of the older space.
Catalog record
| CREATOR | MARÍA A. VALDEZ-CABRERA, AMY D. WILLIS |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 91 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-06747
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Geometry of the space of phylogenetic trees with non-identical leaves MARÍA A. VALDEZ-CABRERA, AMY D. WILLIS Abstract Phylogenetic trees summarize evolutionary relationships. The Billera-Holmes-Vogtmann (BHV) space for comparing phylogenetic trees has many elegant mathematical properties, but it does not encompass trees with differing leaf sets. To overcome this, we introduce Towering space: a complete metric space that extends BHV space to trees with non-identical leaf sets. Towering space is a structured collection of BHV spaces connected via pruning and regrafting operations. We study the geometry of paths in Towering space and present an algorithm for computing metric distances. By addressing a major limitation of BHV space, Towering space facilitates the analysis of modern phylogenetic datasets such as multi-domain gene trees. 1 Introduction Phylogenetic trees represent evolutionary relationships between organisms. While a single phylogenetic tree can describe the shared evolution of large, complex eukaryotes, the genes of simple organisms may meaningfully differ in their evolutionary histories. This is in part because genes are more commonly transferred, duplicated, gained, or lost in bacteria, archaea, and viruses than in eukaryotes ( Jain et al. 1999 ; Koonin et al. 2001 ) . In these organisms, different genes have distinct evolutionary histories, and a collection of “gene trees” offers a more complete summary of phylogenetic relationships than a single tree. Unfortunately, analyzing collections of phylogenetic trees remains challenging in practice. A major advancement in mathematical phylogenetics was the introduction of the BHV tree space ( Billera et al. 2001 ) , a metric space for phylogenetic trees that accounts for differences between trees with respect to both their topologies and their branch lengths. Geodesics in BHV space are smooth, with trees along the path deforming in a locally continuous manner. The polynomial-time algorithm of Owen & Provan 2011 cemented the impact of BHV space, facilitating the development of BHV-based tools for estimating means, variances, principal paths and densities ( Barden et al. 2013 ; Benner et al. 2014 ; Willis & Bell 2018 ; Brown & Owen 2020 ; Nye 2011 ; Nye et al. 2017 ; Weyenberg et al. 2014 ) , constructing confidence sets ( Willis 2019 ) , and clustering ( Gori et al. 2016 ) . Unfortunately, BHV space suffers a major limitation that precludes its applicability to modern datasets: the BHV distance is only defined between trees with the same leaf set. If an organism is missing even one gene (such as due to gene loss or data incompleteness), either the gene tree or the organism must be discarded from a BHV-based analysis. To address this shortcoming, we introduce a metric space for phylogenetic trees with non-identical leaf sets. Our proposal is closely connected to BHV space, and shares its property that distances account for both topological and edge length differences between trees. Previous attempts to extend BHV space to accommodate trees with non-identical leaf sets considered combinatorial methods to transition between BHV tree spaces ( Ren et al. 2017 ) , and constructed representative sets within the largest possible BHV space for all trees ( Grindstaff & Owen 2019 ) . However, these approaches yield dissimilarity measures, not metrics. Our approach yields a metric, and paths have a biological interpretation reflecting gene gain and loss, in addition to sequence divergence. Because our proposed paths traverse nested BHV spaces of differing dimension, we call it the Towering space . While most phylogenetic tree distances are defined only for trees with the same leaf set, our proposal is by no means the first distance that accommodates non-identical leaf sets. The Robinson-Foulds distance — a well-known and simple distance that reflects only topological differences — has multiple extensions to accommodate non-identical leaf sets (reviewed in Li et al. 2024 ). However, to our knowledge, no (proper) metric has been defined for trees with non-identical leaf sets that accounts for differences in both topology and branch lengths. Our work fills this gap. Our paper is structured as follows: Section 2 introduces notation and summarizes key elements of BHV space. Section 3 discusses the geometry of connections between BHV spaces via leaf prunings and regraftings. Section 4 formally defines Towering space and describes the geometry of geodesics, which may traverse multiple BHV spaces. We conclude the paper in Section 5 with a discussion of the implications of the results, applications to broader biological studies, and future work. Proofs of all results can be found in the Supplementary Material. 2 Background 2.1 Preliminaries Phylogenetic trees are labeled tree-graphs that describe the shared evolutionary history of a set of organisms. The branching of the tree reflects the structure of the organisms’ evolutionary relationships, and branch lengths represent the distance between divergence events. Our proposal is equivalent for trees with and without a “root” organism. For generality, we proceed by considering unrooted trees. Definition 2.1 . A phylogenetic tree T on a set of organisms \mathcal{L} is a connected edge-weighted acyclic graph whose leaves (nodes of degree one) are labeled by the elements of \mathcal{L} , and all interior nodes have degree greater or equal to 3. All edge-weights are non-negative values referred to as lengths . The branching pattern of the graph gives the topology of the tree. Removing an edge from a tree splits its leaves into two groups, and such a split of leaves uniquely identifies the edge in the tree. Throughout we use the notation \mathcal{G}\big|\mathcal{L}\setminus\mathcal{G} , with \mathcal{G}\subset\mathcal{L} , to represent the split on \mathcal{L} that separates the leaves in \mathcal{G} from \mathcal{L}\setminus\mathcal{G} . Edges that induce the same split on topologically distinct trees are considered to be the same edge. Therefore, we use the terms edge and split interchangeably. Edges connecting to leaves are called the external edges, which correspond to splits |\mathcal{G}|=1 or |\mathcal{L}|-1 , while all others, with 2\leq|\mathcal{G}|\leq|\mathcal{L}|-2 , are the internal edges. The topology of a tree is fully defined by all its internal splits ( Pachter & Sturmfels 2005 , Theorem 2.34) . We use \mathcal{S}(T) to refer to the set of internal splits in T (equivalently, the topology of T ), while \mathcal{H}(T) refers to the set of external splits and \mathcal{P}(T)=\mathcal{S}(T)\cup\mathcal{H}(T) the entire set of edges. Only certain combinations of splits can be present on a tree. We say two splits are compatible ( Billera et al. 2001 , Section 3.2) if they can simultaneously be present on a tree. 2.2 The Billera-Holmes-Vogtmann tree space Billera et al. 2001 introduced the BHV tree space (\mathcal{T}^{\mathcal{N}},d_{\text{BHV}}) , where \mathcal{T}^{\mathcal{N}} denotes the set of all trees with leaf set \mathcal{N} , and d_{\text{BHV}}:\mathcal{T}^{\mathcal{N}}\times\mathcal{T}^{\mathcal{N}}\mapsto\mathbb{R}_{\geq 0} is a distance function. This metric space is Hadamard ( Bacák 2014 ) , which guarantees continuous paths connecting any pair of trees, as well as a unique path achieving the minimum length, called the geodesic . The space we define in Section 4 is comprised of connected BHV spaces. Consider all possible topologies for trees with leaf set \mathcal{N} of cardinality n=|\mathcal{N}| . Equivalently, consider all possible subsets of internal splits on \mathcal{N} that are pairwise compatible. For one such subset S , assign an order to its elements ( S=\{s_{1},s_{2},\ldots,s_{m}\} ) in any consistent way; for example, a lexicographic order can be assigned to the leaves and the edges