Branch Swapping

Branch Swapping as a heuristic search method

    Heuristic methods are exploratory approaches that attempt an approximate solution to a particular 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 heuristic search method called Sub-tree Pruning & Re-grafting (SPR) takes a "provisional tree" of suspected minimum length, "prunes" one branch and experimentally adds it to each of the inter-nodes of the remaining tree. In the example, the 1+2 branch (sub-tree) is pruned and re-grafted to the 7 branch. The method explores variations on a known tree that is suspected to be close to the minimum length: this is computationally more efficient than examining large numbers of alternative trees of unknown length.

    A variant is Nearest-Neighbor Interchange (NNI), which takes three related branch tips and exchanges the outside one for one of the two inside ones. In this example, in the first network 2 would be interchanged with 1 & 3, or 5 & 6 with respect to 7.

    A third method 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 1234 tree re-connected to each branch in 567.

    TBR is the most "costly" in terms of computational 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.