LvD: A New Algorithm for Computing the Likelihood of a Phylogeny
David Bryant, Celine Scornavacca, David L. Swofford · 2026
Read LvD: A New Algorithm for Computing the Likelihood of a Phylogeny by David Bryant, Celine Scornavacca, David L. Swofford (2026) 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-2601-19064.txt.
Introduction
David Bryant, Celine Scornavacca, and David L. Swofford present a new way to score an evolutionary tree. Few tools in the field are used more than Felsenstein's pruning method, which computes how likely a tree is given DNA data. Their method, LvD, rests on a different split of the tree's structure.
LvD works for all standard models of how DNA letters change over time. A rival route to the same score gives software writers a check on old code and, in some cases, a faster path. Tree scores sit under nearly all modern work on how species relate, so even small gains spread wide.
Catalog record
| CREATOR | David Bryant, Celine Scornavacca, David L. Swofford |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 43 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-19064
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
LvD: A New Algorithm for Computing the Likelihood of a Phylogeny David Bryant, Celine Scornavacca, David L. Swofford Abstract There are few, if any, algorithms in statistical phylogenetics which are used more heavily than Felsenstein’s 1973 pruning method for computing the likelihood of a tree. We present LvD, (Likelihood via Decomposition), an alternative to Felsenstein’s algorithm based on a different decomposition of the underlying phylogeny. It works for all standard nucleotide models. The new algorithm allows updates of the likelihood calculation in worst case O ( log n ) O(\log n) time with n n taxa, as opposed to worst case O ( n ) O(n) time for existing methods. In practice this leads to appreciable improvements in likelihood calculations, the extent of speed-up depending on how balanced or unbalanced the trees are. We explore implications for parallel computing, and show that the approach allows likelihoods to be computed in O ( log n ) O(\log n) parallel time per site, compared to (worst case) O ( n ) O(n) time. We implemented and applied the algorithm to large numbers of simulated and empirical data sets and showed that these theoretical advances lead to a significant practical speed-up, although the extent of the improvement depends on how balanced the phylogenies already are. Keywords: LvD algorithm; Pruning algorithm; likelihood calculation; parallel algorithms; phylogenetic likelihood function 1 Introduction In statistical phylogenetics, few tools are more fundamental than Felsenstein’s pruning algorithm for computing the likelihood of a phylogeny. Felsenstein 2004 plays down the significance of the algorithm, describing it as a simplification of earlier methods for computing likelihoods on pedigrees. Maybe so, but a simple thought experiment reveals quite clearly how important this algorithm has been and still is. The algorithm is executed for every site, every rate class, every tree, every bootstrap replicate or MCMC iteration, every Bayesian or ML analysis, every data set. If you suspend all the computers carrying out phylogenetic inferences at any single time, the bulk of them will probably be executing the pruning algorithm. Perhaps more remarkable is that, in the fifty years since it appeared, no significant modifications to the core algorithm have been published. There has been remarkable progress in the speed and capability of phylogenetic analysis software. This has, for the most part, been achieved by improved search heuristics, approximations, clever updating algorithms, and hardware. The gains have been achieved by reducing the number of times the pruning algorithm is called, or reducing the fraction of the phylogeny which the algorithm is applied to, rather than by redesigning the underlying algorithm. In this paper we describe a new algorithm for computing the likelihood of a phylogeny. The algorithm uses dynamic programming, like Felsenstein’s pruning algorithm, but uses a different structure for the computations. This results in an appreciable speedup with respect to the pruning algorithm, while exhibiting the same flexibility with respect to extended models and engineering speedups. The main difference between the two algorithms can be summarized as follows. The dynamic programming approach used in Felsenstein’s algorithm decomposes the phylogeny into clades, with partial likelihoods being computed at each node in the phylogeny for the subtree rooted at that node. Our approach is to consider more general subsets of the phylogeny, which we call components . We define partial likelihoods for these objects and define a decomposition tree which can be used to compute these partial likelihoods. Importantly, the decomposition tree can always be chosen to have height at most O(\log n) , a property which underpins all of the improvements in running time. Designing algorithms using this new structure leads to an improvement from worst-case O(n) time to O(\log n) for updating the likelihood of a phylogeny, and a single-site, O(\log n) parallel time , likelihood computation. We call this new approach Likelihood via Decomposition (LvD). To an extent, LvD represents a hybridisation of two main innovations. The first is the idea of defining and computing partial likelihoods for more general subsets of a phylogeny. This was first explored in the highly original paper of Sumner and Charleston 2010 , who employed likelihood tensors to (heuristically) maximize the gains that can be made from repeated sub-patterns in the data. We make use of a similar idea, modified and restricted to make the approach computationally tractable. The second is the structure and properties of the decomposition tree. This is based on data structures used in Bryant and Scornavacca 2019 to compute the path-length metric between trees in O(n\log n) time, which in turn were derived from the algorithm of Brodal et al. 2004 for computing the quartet metric. The structure of this paper is as follows. • In Section 2 we review the standard pruning algorithm for computing the likelihood of a phylogeny. At the same time we introduce notation used throughout the manuscript. • In Section 3 we describe the new approach in detail. The key concept here is a novel decomposition of the phylogeny giving a new method for evaluating likelihoods. We obtain a new tree structure to compute the partial likelihoods on, one that has a logarithmic height. We then outline two ways in which we can take advantage of the new structures: a faster (memory efficient) algorithm for computing likelihoods and a new theoretical bound on the time taken to compute likelihoods in parallel. • In Section 4 we investigate the practical speed-ups resulting from the new updating algorithm. We base our analysis on hundreds of existing simulated and real data sets. • Section 5 reviews the main contributions of the paper and sketches avenues for future work. 2 Revisiting Felsenstein’s pruning algorithm 2.1 Notation Suppose we are given an alignment A , a phylogeny with branch lengths, and the parameters of an evolutionary model. Our goal is to compute the probability of observing the alignment given these parameters. We assume that sites are independent, so this probability can be computed independently for each site A_{j} . The pruning algorithm of Felsenstein 1973 permits to compute the probability of observing a single site in the alignment, given the phylogeny, branch lengths and model parameters. We review the algorithm and introduce notation we will need later on. A phylogeny is made up of nodes and edges. The root is labelled \rho . A node v is a descendant of node u if the path from v to the root passes through u . The set of tips which are descendants of v is denoted C_{v} (Fig. 1 ). Figure 1 : Terminology and notation for phylogenies. The root is denoted \rho . For each node v , the state at that node is denoted \mathbf{x}_{v} and the set of taxa which are descendants of v is denoted by C_{v} . The ancestral state for node v is denoted \mathbf{x}_{v} . The ancestral state \mathbf{x}_{\rho} for the root has distribution \pi , defined by the evolutionary model. The joint distribution of all ancestral states is determined by the root distribution together with all the conditional probabilities \Pr[\mathbf{x}_{v}=s|\mathbf{x}_{u}=r] (1) for the state \mathbf{x}_{v} of a child node v given the state \mathbf{x}_{u} of its parent node. These probabilities are typically functions of the edge length, according