Nearest-Neighbor Interchange

Nearest-Neighbor Interchange (NNI) is the most elementary topological rearrangement operator used to navigate the discrete space of unrooted binary trees during phylogenetics inference under maximum-likelihood phylogenetics, minimum evolution, and maximum parsimony criteria. Formulated mathematically by David F. Robinson in 1971 and Moore, Goodman, and Barnabas in 1973, an NNI operation acts on a single internal branch (interior edge) of an unrooted binary tree. Because every internal branch connects two degree-3 internal nodes, erasing that central branch together with its two incident nodes partitions the tree into four disjoint subtrees: A, B, C, and D.

There are exactly three ways to connect four subtrees (A, B, C, D) across a central internal branch e:

1. Current Topology (τ₀): Subtrees (A, B) are sister on one side of branch e, and subtrees (C, D) are sister on the other side: ((A, B), (C, D)).
2. First NNI Neighbor (τ₁): Subtree B is swapped with subtree C across branch e, yielding ((A, C), (B, D)).
3. Second NNI Neighbor (τ₂): Subtree B is swapped with subtree D across branch e, yielding ((A, D), (B, C)).

Because an unrooted binary tree with N terminal taxa possesses exactly N − 3 internal branches, and each internal branch admits 2 alternative quartet configurations, the entire 1-step NNI neighborhood of any tree τ₀ contains exactly 2(N − 3) candidate trees.

Combinatorial Growth of Unrooted Binary Topologies

The necessity of heuristic topological rearrangement operators like NNI and Subtree Pruning and Regrafting arises from the rapid double-factorial growth of the number of possible unrooted binary trees U(N) for N labeled taxa:

U(N) = (2N − 5)!! = 1 × 3 × 5 × ··· × (2N − 5) = (2N − 5)! / [ 2^N−3 (N − 3)! ]

While exhaustive evaluation of all topologies is trivial for N = 4 taxa (3 trees) or N = 5 taxa (15 trees), U(N) reaches 2,027,025 trees at N = 10, 2.22 × 10²⁰ trees at N = 20, and 2.75 × 10⁷⁶ trees at N = 50 (outpacing an exponential growth phase exp(N ln N)). Finding the maximum-likelihood tree topology is formally NP-hard, requiring iterative hill-climbing and stochastic search through the NNI graph—the regular graph of degree 2(N − 3) whose vertices are the (2N − 5)!! unrooted binary topologies and whose edges connect pairs of trees separated by a single NNI swap.

Properties of the NNI Metric and Robinson's Theorem

Robinson (1971) proved that the NNI graph is connected: any unrooted binary tree τ_A can be transformed into any other unrooted binary tree τ_B on the same N taxa through a finite sequence of NNI moves. The minimum number of NNI operations required to transform τ_A into τ_B defines the NNI distance d_NNI(τ_A, τ_B), which is bounded above by O(N log N) and bounded below by half the Robinson-Foulds (RF) bipartition distance. Every NNI move alters the bipartition (split) defined by the central internal branch e while leaving all other N − 4 internal bipartitions of the tree intact.

Local Quartet Partial Likelihood Caching

A major computational advantage of NNI over global rearrangements in maximum-likelihood phylogenetics is that evaluating both alternative NNI configurations (((A,C),(B,D)) and ((A,D),(B,C))) across an internal edge e does not require re-running Felsenstein's tree-pruning algorithm across the four subtrees A, B, C, and D.

By invoking Felsenstein's Pulley Principle for time-reversible Markov chain models, a maximum-likelihood solver pre-computes and caches the conditional subtree likelihood vectors L_A, L_B, L_C, and L_D at the root nodes of the four subtrees A, B, C, and D. Because all branch lengths internal to subtrees A, B, C, and D remain fixed during the local NNI test, the four subtrees behave precisely like a 4-taxon quartet tree connected by five branches: the central internal branch e (of length t_e) and the four pendant branches leading to the roots of A, B, C, and D (of lengths t_A, t_B, t_C, and t_D).

One-Dimensional and Five-Branch Newton-Raphson Optimization

When testing an NNI swap (for instance, swapping B and C to form τ₁ = ((A,C),(B,D))), the log-likelihood ℓ(τ₁) is maximized with respect to the central branch length t_e (and optionally the four adjacent branch lengths t_A, t_B, t_C, t_D) using analytical first and second derivatives ∂ℓ/∂t_e and ∂²ℓ/∂t_e² evaluated directly from the spectral decomposition of the transition matrix P(t_e) = exp(Qt_e):

t_e^(m+1) = t_e^(m) − [ ∂ℓ / ∂t_e ] / [ ∂²ℓ / ∂t_e² ]

In a 1-branch fast NNI evaluation, only the central branch length t_e is optimized (taking 3–5 Newton-Raphson iterations in O(L_u · A²) time), while the four adjacent branch lengths t_A, t_B, t_C, t_D are held fixed; if this conservative lower bound already improves or nearly approaches the current log-likelihood ℓ(τ₀), a 5-branch NNI refinement then optimizes t_e, t_A, t_B, t_C, and t_D simultaneously.

Simultaneous Non-Overlapping NNI (PhyML and FastTree)

In classical steepest-ascent NNI hill-climbing, the algorithm evaluates all 2(N − 3) NNI neighbors, applies only the single NNI move with the largest positive log-likelihood gain Δℓ = ℓ(τ_new) − ℓ(τ₀) > 0, and repeats until no single NNI move yields Δℓ > 0. However, changing only one branch per sweep requires O(N) sweeps to propagate topology corrections across a large tree.

Stéphane Guindon and Olivier Gascuel (2003) revolutionized NNI search in PhyML (and later Price et al. in FastTree) by introducing simultaneous NNI. In a single pass over all N − 3 internal branches, PhyML records every internal branch e that admits a likelihood-improving NNI swap (Δℓ_e > 0), ranks those positive moves in descending order of Δℓ_e, and applies a maximal set of non-overlapping (disjoint) NNI moves simultaneously in a single step, followed by global branch-length optimization. Applying multiple independent NNI swaps simultaneously accelerates convergence by more than an order of magnitude.

Escaping Local Optima and Ultrafast Approximation (IQ-TREE and aLRT)

Because NNI only swaps adjacent subtrees across a single internal edge, deterministic NNI hill-climbing frequently becomes trapped in local optima (topological "islands" where every 1-step NNI move decreases the log-likelihood, even though moving a taxon across two or more branches via Subtree Pruning and Regrafting would substantially increase the likelihood).

To overcome NNI local optima without sacrificing speed, IQ-TREE (Nguyen et al., 2015) combines a candidate pool of diverse starting trees with stochastic NNI perturbations: whenever NNI hill-climbing reaches a local optimum, IQ-TREE randomly perturbs a fraction (e.g., 20–50%) of the locally optimal internal branches via random NNI moves and immediately launches a new round of simultaneous NNI hill-climbing, accepting new local optima that surpass the best-known log-likelihood. Furthermore, because the two alternative NNI configurations around an internal branch e represent the two competing resolutions of that clade, comparing the log-likelihood of the best tree ℓ₀ against the best of its two NNI alternatives max(ℓ₁, ℓ₂) provides the foundation for the SH-like approximate Likelihood Ratio Test (SH-aLRT) and aBayes branch support metrics, offering a fast single-branch complement to nonparametric bootstrapping statistics.

How many NNI rearrangements exist for an unrooted binary tree with N taxa?

An unrooted binary tree with N terminal taxa has exactly N − 3 internal branches. Because each internal branch connects four subtrees (A, B, C, D) that can be partitioned in 3 ways—1 current arrangement ((A,B),(C,D)) and 2 alternative arrangements ((A,C),(B,D)) and ((A,D),(B,C))—there are exactly 2(N − 3) Nearest-Neighbor Interchange topologies at a 1-step distance from the current tree.

Why does greedy NNI hill-climbing get trapped in local optima?

Suppose taxon X is misplaced two branches away from its true sister clade on a phylogenetic tree. Moving taxon X across two internal branches requires two consecutive NNI swaps: the first NNI swap must break up an intervening monophyletic group (temporarily lowering the log-likelihood, Δℓ₁ < 0) before the second NNI swap can unite taxon X with its true sister group (Δℓ₁ + Δℓ₂ > 0). Because deterministic hill-climbing rejects any intermediate step with Δℓ < 0, it remains trapped unless supplemented by stochastic NNI perturbations or Subtree Pruning and Regrafting (SPR).

How are NNI moves used to calculate SH-aLRT branch support?

For any internal branch e in the maximum-likelihood tree τ₀, the two NNI rearrangements τ₁ and τ₂ across edge e represent the two most competitive alternative hypotheses that break the clade defined by e. The approximate Likelihood Ratio Test (aLRT) computes 2Δℓ = 2[ℓ(τ₀) − max(ℓ(τ₁), ℓ(τ₂))] using only local 5-branch optimization around edge e, assessing clade support in milliseconds per branch.

1. Robinson, D. F. (1971). "Comparison of labeled trees with valency three." Journal of Combinatorial Theory, Series B, 11(2), 105–119. https://doi.org/10.1016/0095-8956(71)90020-790020-7)
2. Guindon, S., & Gascuel, O. (2003). "A simple, fast, and accurate algorithm to estimate large phylogenies by maximum likelihood." Systematic Biology, 52(5), 696–704. https://doi.org/10.1080/10635150390235520
3. Nguyen, L.-T., Schmidt, H. A., von Haeseler, A., & Minh, B. Q. (2015). "IQ-TREE: A fast and effective stochastic algorithm for estimating maximum-likelihood phylogenies." Molecular Biology and Evolution, 32(1), 268–274. https://doi.org/10.1093/molbev/msu300
4. Anisimova, M., & Gascuel, O. (2006). "Approximate likelihood-ratio test for branches: A fast, accurate, and powerful alternative." Systematic Biology, 55(4), 539–552. https://doi.org/10.1080/10635150600755453