Abstract
We investigated testing the likelihood of a phylogenetic tree by comparison to its subtree pruning and regrafting (SPR) neighbors, with or without re-optimizing branch lengths. This is inspired by aspects of Bayesian significance tests, and the use of SPRs for heuristically finding maximum likelihood trees. Through a number of simulations with the Jukes-Cantor model on various topologies, it is observed that the SPR tests are informative, and reasonably fast compared to searching for the maximum likelihood tree. This suggests that the SPR tests would be a useful addition to the suite of existing statistical tests, for identifying potential inaccuracies of inferred topologies.
Introduction
In evolutionary biology, reconstructing the "tree of life" is a massive computational challenge. As the number of species increases, the number of possible tree topologies grows exponentially—far beyond what any supercomputer can check. Consequently, researchers rely on heuristic searches to find the "Maximum Likelihood" (ML) tree.
However, finding a high-likelihood tree does not guarantee it is the correct one; it may simply be a local optimum. Existing validation tools like the bootstrap (re-sampling data) can be computationally expensive and sometimes overconfident, while the approximate Likelihood Ratio Test (aLRT) only examines very small local changes known as Nearest-Neighbor Interchanges (NNIs). This research proposes a "middle ground": a statistical test that is more thorough than NNI-based tests but significantly faster than a full Bayesian analysis or an exhaustive search.
Methodology: The SPR Framework
The proposed framework utilizes the Subtree Pruning and Regrafting (SPR) operation to explore the tree space around an inferred topology. An SPR move involves cutting a branch (a "clan" or clade) off a tree and grafting it onto a different branch. The authors propose two specific statistics based on this operation:
- $SPR_{plain}$ statistic: This calculates the likelihood of all trees in the SPR neighborhood using the branch lengths from the original inferred tree. This method is computationally efficient because it avoids the need to re-optimize branch lengths for every neighbor.
- $SPR_{opt}$ statistic: This re-optimizes the branch lengths for every single neighbor in the SPR space. While more computationally demanding, it provides a more accurate assessment of the neighborhood's likelihood.
The core logic treats the likelihood of the inferred tree as a ratio against the sum of the likelihoods of its SPR neighbors. This provides an approximate upper bound on the probability that the tree topology is correct.
Experimental Design
The study utilized simulated data to benchmark the performance of these statistics:
- Model: Data was generated using the Jukes-Cantor model of DNA evolution via
Seq-Gensoftware. - Topologies: The authors used specific balanced binary trees (labeled $C_1$ through $C_6$) ranging from 4 to 66 species.
- Sequence Lengths: DNA sequences ranged from a single nucleotide to 65,536 base pairs to evaluate how the test performs across varying levels of phylogenetic signal.
- Inference: Maximum likelihood searches were performed using
DNAMLfrom the PHYLIP package.
Key Insights and Results
Neighborhood Sufficiency
A critical finding of the study is the concept of "Neighborhood Sufficiency." In a 6-species test, the authors observed that the SPR neighborhood—which contains only a small fraction of all possible trees—captured almost all of the total likelihood in the tree space. This suggests that evaluating immediate SPR neighbors is a highly effective proxy for searching the entire (and often impossibly large) tree space.
Accuracy and Decisiveness
Both $SPR_{plain}$ and $SPR_{opt}$ successfully assigned high scores to correct trees and low scores to incorrect ones as sequence length increased. However, $SPR_{opt}$ proved to be significantly more "decisive." For a 6-species tree ($C_2$), the $SPR_{opt}$ statistic had a total likelihood sum of 1.02 across all topologies, while $SPR_{plain}$ was much looser at 3.15. This confirms that re-optimizing branch lengths provides a much tighter bound for significance.
Computational Performance
The tests scale at $O(m^3n)$, where $m$ is the number of species and $n$ is the sequence length. $SPR_{plain}$ is remarkably fast, with a runtime comparable to the initial ML search itself. While $SPR_{opt}$ is slower, it remains practical for modern hardware on moderately sized trees where exhaustive searches are impossible.
Conclusion and Future Work
The SPR test is not intended to replace the bootstrap but to act as a complementary tool for identifying "pathological" cases where a clade is attached to the wrong branch—a common error in phylogenetic inference.
While the current study focused on simulated data and smaller trees, future work could involve "lazy" subtree rearrangements—optimizing only the branches near the regrafting point—to make the $SPR_{opt}$ test even faster. Additionally, testing the framework against real-world DNA data, which includes complexities like gaps and sequencing errors, will be essential for further validating its utility in the field.
Summary updated