Subtree Pruning and Regrafting

Subtree Pruning and Regrafting (SPR) is a global topological rearrangement operation used in phylogenetics to search the combinatorial space of evolutionary trees under maximum-likelihood phylogenetics, Bayesian inference, and maximum parsimony criteria. Whereas a Nearest-Neighbor Interchange (NNI) move is restricted to swapping adjacent subtrees across a single internal branch, an SPR operation detaches ("prunes") a subtree from its current position in an unrooted or rooted binary tree and reattaches ("regrafts") that subtree by subdividing any remaining branch of the residual tree.

Specifically, an unrooted SPR move proceeds in three topological steps:

1. Pruning: Select any branch e of an unrooted binary tree τ and sever it, partitioning τ into two disconnected subtrees, T_prune (the pruned clade, rooted at the cut endpoint v_p) and T_rem (the remaining backbone tree).
2. Suppression of the Degree-2 Node: In the residual backbone tree T_rem, the internal vertex v₀ from which T_prune was detached now has degree 2; suppressing vertex v₀ merges its two incident edges e₁ and e₂ into a single continuous branch e₁₂ of initial length t₁ + t₂.
3. Regrafting: Select any target branch e_target ≠ e₁₂ anywhere in the residual backbone tree T_rem, insert a new internal vertex v_new that splits e_target into two sub-branches, and attach the root v_p of the pruned subtree T_prune to v_new via the reconnected branch e.

Because an SPR move can transport a misplaced taxon or clade across an arbitrary number of intervening nodes in a single step, SPR searches smoothly traverse low-likelihood valleys that trap local NNI hill-climbers.

Size of the 1-Step Unrooted SPR Neighborhood

Consider an unrooted binary tree τ with N terminal taxa, which contains 2N − 3 total branches (N terminal tip branches and N − 3 internal branches) and N − 2 internal vertices. In a 1-step SPR neighborhood, every possible pruned subtree T_prune can be reattached onto any branch of the remaining backbone tree T_rem except the merged branch e₁₂ from which it was just detached.

Summing over all 2(2N − 3) directed branch cuts and subtracting the redundant moves that regenerate the starting topology τ or duplicate identical 1-edge swaps (as derived by Allen and Steel in 2001), the number of distinct unrooted binary trees within a 1-step SPR move of τ is:

|N_SPR(τ)| = 2(N − 3)(2N − 7)

Notice that when the target branch e_target selected for regrafting is adjacent to the original attachment branch e₁₂ (separated by only one internal node along the tree backbone), the SPR move reduces to a Nearest-Neighbor Interchange (NNI). Subtracting the 2(N − 3) NNI moves from the total SPR count leaves 4(N − 3)(N − 4) non-NNI long-range SPR moves.

Hierarchy of Rearrangement Operators: NNI ⊂ SPR ⊂ TBR

Phylogenetic tree rearrangement operators form a nested inclusion hierarchy of neighborhoods around any tree τ₀:

N_NNI(τ₀) ⊂ N_SPR(τ₀) ⊂ N_TBR(τ₀)

The broadest operator in this hierarchy is Tree Bisection and Reconnection (TBR): after severing an internal branch e to split the tree into two subtrees T₁ and T₂ (and suppressing the resulting degree-2 vertices in both T₁ and T₂), TBR allows the reconnection branch to join any branch of T₁ to any branch of T₂ (re-rooting T_prune before regrafting it). While TBR explores O(N³) neighbors per sweep, its size depends on the balance of the starting topology (ranging from Θ(N²) on a caterpillar tree to Θ(N³) on a balanced tree), whereas the SPR neighborhood size 2(N − 3)(2N − 7) is a topological invariant independent of tree shape.

The Computational Bottleneck of Naively Evaluating O(N²) SPR Moves

Evaluating a full alignment log-likelihood from scratch via Felsenstein's tree-pruning algorithm requires O(N · L_u · A²) operations. If a naive SPR implementation evaluated all O(N²) candidate trees in N_SPR(τ) from scratch and optimized all 2N − 3 branch lengths on each candidate, a single SPR sweep would require O(N³ · L_u · A²) time—prohibitively slow for trees with N > 100 taxa.

To make SPR tractable for thousands of taxa, Alexandros Stamatakis (RAxML, 2006) and Stéphane Guindon and Olivier Gascuel (PhyML 3.0, 2010) developed three algorithmic optimizations:

1. Incremental Conditional Likelihood Updating along the Migration Path: When a pruned subtree T_prune is detached from node v₀ and regrafted onto a target branch at distance d nodes away along the backbone tree T_rem, the conditional likelihood vectors L_u(s) inside T_prune and inside all clades lying off the path between v₀ and v_new remain unchanged. Only the d − 1 internal nodes along the migration path between the old attachment point and the new insertion point require updated partial likelihood vectors. By sliding the insertion point step-by-step outward from v₀ via depth-first traversal of T_rem, each candidate regrafting site can be visited in O(1) amortized node updates per site pattern.
2. Lazy Subtree Rearrangement (Fast Local Insertion Filtering): When testing a candidate regrafting branch e_target, RAxML and PhyML do not optimize all branch lengths of the tree. Instead, they perform a Lazy SPR check: only the three branches incident to the new insertion node v_new (or the new split lengths on e_target and the connecting branch e) are optimized via 1 to 3 Newton-Raphson steps while holding all other branch lengths fixed. Candidate moves whose fast lazy score falls substantially below the current best log-likelihood ℓ₀ are discarded, and only the top-scoring candidate topologies undergo full multi-branch optimization.
3. Adaptive Rearrangement Radius (r-SPR): Most likelihood-improving SPR moves transport a pruned subtree across a moderate topological distance (typically r = 2 to 8 internal nodes) rather than to the opposite side of a 1,000-taxon tree. RAxML automatically calibrates an initial rearrangement radius r_min–r_max on the starting tree, restricting early SPR sweeps to target branches within radius r of the pruning site before widening the search radius on promising clades.

Rooted SPR Distance and Lateral Gene Acquisition

Beyond its role as a numerical optimization heuristic in tree search, the rooted Subtree Pruning and Regrafting (rSPR) operation has a direct biological interpretation in molecular evolution: a single rooted SPR move models the topological incongruence between a gene tree and a species tree caused by one horizontal gene transfer (HGT) event or hybrid introgression.

When a donor lineage D transfers a genetic locus (such as an antibiotic resistance cassette on a mobile plasmid replicon or a pathogenicity island) horizontally into a recipient lineage R, the transferred gene copy in R traces its evolutionary ancestry back to the donor branch D rather than to the vertical ancestor of R. Consequently, reconstructing the gene tree produces a topology in which the recipient subtree R has been pruned from its vertical species-tree position and regrafted onto the donor branch D (respecting temporal ordering so that donor and recipient lineages are contemporaneous). Calculating the minimum rSPR distance d_rSPR(T_species, T_gene) between a reference species phylogeny and an anomalous gene phylogeny provides a rigorous lower bound on the minimum number of horizontal gene transfer or homologous recombination events required to reconcile the two evolutionary histories, although computing d_rSPR between two arbitrary trees is NP-hard and solved in practice via fixed-parameter tractable (FPT) kernelization algorithms.

Why is Subtree Pruning and Regrafting (SPR) much less likely to get trapped in local optima than NNI?

Nearest-Neighbor Interchange (NNI) can only swap subtrees across a single internal branch (radius r = 1). If a taxon or clade is misplaced several nodes away from its optimal position in a starting tree (such as a Neighbor-Joining or BioNJ tree), moving it via NNI requires multiple sequential single-branch swaps that temporarily pass through low-likelihood intermediate topologies. SPR detaches the misplaced clade and regrafts it onto its optimal target branch in a single step, bypassing the intervening likelihood valley.

How does "Lazy SPR" speed up maximum-likelihood tree search in RAxML and PhyML?

Evaluating all 2(N − 3)(2N − 7) SPR neighbors by re-optimizing every branch length on the tree would take O(N³) time per sweep. Lazy SPR slides the pruned subtree outward along the backbone tree (updating only 1 conditional likelihood vector per step) and estimates the likelihood of each candidate regrafting branch by optimizing only the 1 to 3 branches touching the new insertion node; full branch-length optimization is reserved for moves that pass this fast local filter.

What is the connection between rooted SPR moves and horizontal gene transfer?

In evolutionary genomics, when a recipient species acquires a gene from a distant donor species via horizontal gene transfer (xenologous replacement), the gene tree differs from the vertical species tree by a single rooted SPR operation: the recipient clade is pruned from its vertical taxonomic family and regrafted as the sister group to the donor lineage.

1. Allen, B. L., & Steel, M. (2001). "Subtree transfer operations and their induced metrics on evolutionary trees." Annals of Combinatorics, 5(1), 1–15. https://doi.org/10.1007/s00026-001-8006-8
2. Stamatakis, A. (2006). "RAxML-VI-HPC: Maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models." Bioinformatics, 22(21), 2688–2690. https://doi.org/10.1093/bioinformatics/btl446
3. Guindon, S., Dufayard, J.-F., Lefort, V., Anisimova, M., Hordijk, W., & Gascuel, O. (2010). "New algorithms and methods to estimate maximum-likelihood phylogenies: Assessing the performance of PhyML 3.0." Systematic Biology, 59(3), 307–321. https://doi.org/10.1093/sysbio/syq010
4. Hordijk, W., & Gascuel, O. (2005). "Improving the efficiency of SPR moves in phylogenetic tree search methods based on maximum likelihood." Bioinformatics, 21(24), 4338–4347. https://doi.org/10.1093/bioinformatics/bti713