Phylogenetics in a warm place: computational aspects of the Tropical Grassmannian

Samir Bhatt, John Sabol, Papri Dey, Matthew J. Penn, David Duchene, Ruriko Yoshida · 2025

Read Phylogenetics in a warm place: computational aspects of the Tropical Grassmannian by Samir Bhatt, John Sabol, Papri Dey, Matthew J. Penn, David Duchene, Ruriko Yoshida (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-2512-21765.txt.

Introduction

Samir Bhatt, Ruriko Yoshida, and their co-authors review the tropical Grassmannian as a tool for phylogenetics, the reconstruction of trees. The number of possible tree shapes explodes with the number of species, making tree space hard to search and summarize. The classical Billera-Holmes-Vogtmann space gives tree space a nice geometry but brings computational difficulties.

Tropical geometry, a piecewise-linear shadow of algebra, offers an alternative. Speyer and Sturmfels showed that the tropical Grassmannian for two-planes coincides with the space of trees. The paper explains that structure and presents algorithms for working with it, including procedures for sampling trees from the tropical Grassmannian. Sampling matters because biologists need to explore the distribution of plausible trees, not just find one best guess. The authors aim to make the machinery accessible to biologists and seed new work where algebraic geometry meets phylogenetic inference.

Catalog record

CREATORSamir Bhatt, John Sabol, Papri Dey, Matthew J. Penn, David Duchene, Ruriko Yoshida
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-21765

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Phylogenetics in a warm place: computational aspects of the Tropical Grassmannian Samir Bhatt, John Sabol, Papri Dey, Matthew J. Penn, David Duchene, Ruriko Yoshida Abstract Phylogenetic trees provide a fundamental representation of evolutionary relationships, yet the combinatorial explosion of possible tree topologies renders inference computationally challenging. Classical approaches to characterizing tree space, such as the Billera–Holmes–Vogtmann (BHV) space, offer elegant geometric structure but suffer from statistical and computational limitations. An alternative perspective arises from tropical geometry: the tropical Grassmannian ( tropGr ⁡ ( 2 , n ) \tropGr(2,n) ), introduced by Speyer and Sturmfels, which coincides with phylogenetic tree space. In this paper, we review the structure of the tropical Grassmannian and present algorithmic methods for its computational study, including procedures for sampling from the tropical Grassmannian. Our aim is to make these concepts accessible to evolutionary biologists and computational scientists, and to motivate new research directions at the interface of algebraic geometry and phylogenetic inference. 1 1 1 Code for all figures are available here https://github.com/bhattsamir/tropical_grassmannian † † footnotetext: 1 University of Copenhagen; 2 Imperial College London; 3 Naval Postgraduate School; 4 University of California, Santa Cruz. * These authors contributed equally to this work. A phylogenetic tree is a mathematical structure that connects the worlds of evolutionary biology and computer science. In evolutionary biology, it represents the evolutionary relationships among a set of taxa. In computer science, an unrooted phylogenetic tree on a set of n taxa is defined as a tree T\in\mathcal{T}_{n}=(\mathcal{V},\mathcal{E}) , where \mathcal{V} is the set of vertices and \mathcal{E} the set of edges (often weighted). The space of possible trees \mathcal{T}_{n} is finite, but intractably large and given by the Schröder number (2n-5)!! in the unrooted case. The tree T has exactly n leaves (also called tips), each corresponding to one taxon, and n-2 internal nodes, each of degree 3. For just n=40 individuals or species, the number of possible evolutionary trees is already greater than the number of hydrogen atoms in the Sun. Trying to find the correct tree in that space is like trying to locate one specific hydrogen atom somewhere inside the entire Sun. If the tree is rooted, the root node has out-degree 2, and there are n-1 internal nodes. In both rooted and unrooted cases, the edges \mathcal{E} are typically assigned non-negative weights, representing evolutionary distances or divergence times. The central challenge in computational phylogenetics is finding the best tree, T^{*} given some data X and an objective criterion \mathcal{L} that measures how well T^{*} characterises the data. i.e. \displaystyle T^{*}=\arg\min_{T\in\mathcal{T}}\;\mathcal{L}(X,T). (1) Broadly three major objective criteria exist, maximum parsimony [ 9 ] , maximum likelihood [ 6 ] and minimum evolution [ 24 ] . Solving Equation 1 is NP-hard for all three criteria [ 10 , 23 , 8 ] . This means that there is no known polynomial-time algorithm that always finds the globally optimal phylogenetic tree under standard objective criteria. Heuristic algorithms, such as hill climbing and tree rearrangement strategies often perform well in practice, but offer no guarantee of global optimality. Hill climbing performs well in phylogenetic tree search because the objective criteria landscapes on tree space exhibit strong local correlation, producing large basins of attraction around high-likelihood topologies and enabling local tree change moves to reliably ascend toward near-optimal trees. Therefore a central challenge in these heuristic algorithms is efficiently exploring tree space. This exploration is typically performed through local rearrangement operations that generate neighboring trees. Two common operations are Nearest Neighbor Interchange (NNI) and Subtree-Prune and Regraft (SPR). NNI modifies a tree by swapping subtrees across an internal edge, resulting in a new topology with minimal change. SPR involves cutting a subtree from the tree and reattaching it at a different edge, allowing for broader exploration of tree space. These operations define the neighborhood structure of the search, but naturally raise the question: what exactly is tree space, and how is it structured? A geometrically rigorous solution to this question was provided by Billera, Holmes, and Vogtmann [ 3 ] , who showed that phylogenetic tree space can be endowed with the structure of a CAT (0) (Cartan–Alexandrov–Toponogov) space, a type of non-positively curved metric space that admits unique geodesics between points. The Billera–Holmes–Vogtmann (BHV) tree space provides a geometric and combinatorial model for the space of phylogenetic trees with edge lengths. Formally, it is a piecewise Euclidean cubical complex in which each orthant (i.e., a Euclidean space {\mathbb{R}}_{\geq 0}^{k} ) corresponds to a unique tree topology defined by a fixed set of internal splits. The dimension k of an orthant equals the number of internal edges in the tree, which is n-3 for a fully resolved unrooted binary tree with n leaves. Within each orthant, trees differ only in the lengths of their internal edges and are equipped with standard Euclidean geometry. Orthants are glued together along shared lower-dimensional faces corresponding to unresolved trees (i.e., trees with collapsed edges or polytomies). The resulting space is connected, contractible, and forms a CAT(0) space. This structure enables well-defined and efficiently computable geodesic distances between trees in polynomial time ( \mathcal{O}(n^{4}) ) [ 19 ] . Despite its elegant geometric properties, BHV tree space presents certain challenges, particularly for statistical inference. One such issue is stickiness , a phenomenon arising from the non-manifold boundaries between orthants. Because the space is composed of orthants glued along lower-dimensional faces, geodesics and Fréchet means (i.e., the average tree) often lie on these lower-dimensional boundaries, corresponding to unresolved trees with one or more zero-length edges. As a result, even when input trees are fully resolved, their average under the BHV metric can be topologically unresolved. Additionally, the high-dimensional and combinatorial structure of BHV space makes some computational tasks, such as likelihood optimization or Bayesian posterior integration, difficult to implement efficiently, particularly as the number of taxa increases. In addition, Lin et al. [ 15 ] showed that the dimension of the convex hull of three points in terms of the BHV metric over BHV space is unbounded in general, and that a convex hull in terms of the BHV metric over BHV space might not be closed. Therefore, unlike Euclidean space, it is not trivial to conduct a simple statistical analysis over BHV space. Finally, it is challenging to efficiently sample uniformly from the BHV space, again prohibiting Bayesian inference. These challenges have motivated the exploration of alternative models of tree space that better accommodate statistical and algorithmic needs. A completely different way to fully characterise tree space that is still geometrically rigorous was provided by Speyer and Sturmfels [ 26 ] and called the Tropical Grassmannian . Before explaining what this exotically named object is, we first need to introduce the concept of the tree metric. A metric space (X,\dist) (where X is the set of taxa of interest and \dist is some distance function) is called a tree metric if there exists a weighted tree T such that for all a,b\in X , \dist(a,b) equals the sum of edge weights along the unique path between a and b in T . Stated more simply, the leaf to leaf distance between any two taxa, is the sum of the branch lengths between them. Unfortunately, it is exceedingly

Read the complete text