Branch Swapping as a heuristic search method
Heuristic methods
are exploratory approaches
that attempt an approximate solution to a computational
problem that may be difficult or impossible to solve
exactly.
Heuristic methods are often applied to the
problem of finding the shortest evolutionary tree for a large
number of taxa. One such method shown above is Sub-tree Pruning & Re-grafting (SPR). Given a "provisional tree" of
suspected minimum length [left], "prune" one branch [left]
and "regraft" it [middle] experimentally to each of the branches
and inter-nodes of the remaining tree. In the example [right], the
1+2 branch (sub-tree)
is pruned and re-grafted to the 7
branch (right), and then in turn to the 4, 5, & 6 branches. The method is
computationally more efficient than examining large numbers of
alternative trees of unknown length.
A variant is Nearest-Neighbor Interchange (NNI) [middle], which takes
three related branch tips and exchanges the outside one for one of
the two inside ones. In this example [left], in the first network
2 could be interchanged with 1 & 3,
or 7 with respect to 5
& 6.
A third variant is Tree Bisection and Re-connection
(TBR), in which the tree
is cut as nearly in half as possible and re-grafted on each of
the remaining branches or inter-nodes. In this example, the
first network would be cut between 3 & 4, and the 1+2+3
sub-tree re-connected to each branch in 4+5+6+7.
TBR is the most "costly"
in terms of computational CPU time, but is most likely to
find a shorter alternative solution, if one exists. NNI is
the least costly of the three, but is also the least likely to
find a shorter tree. SPR is intermediate on both
criteria. One strategy is to use a large number of TBR searches
to identify an optimal or near-optimal tree, and NNI to
assess bootstrap trees where finding the optimal tree in
every case is not so essential.
Figure modified from
Krane & Raymer 2004; All text material © 2025 by Steven M.
Carr