Tree Searching

For heuristic methods like parsimony and likelihood, we have to search around tree space for trees that result in better scores. The procedure often goes like

  1. Pick a start tree
  2. Calculate the score (parsimony or likelihood)
  3. Rearrange the tree (using one of the methods below)
  4. Calculate the score of the new tree
  5. Keep the tree that has the higher score
  6. Until the tree is “good enough” go back step 3

There are three major methods that most phylogenetics packages use to rearrange trees while doing heuristic searches. Let’s look at each of these.

Nearest Neighbor Interchange

The simplest method for rearrangement is Nearest Neighbor Interchange, abbreviated NNI. The easiest way to think of an NNI move is to think of a branch in an unrooted tree (not a node, but a branch) and then imagine removing the four nodes that connect to that branch and then reattaching those four nodes, randomly. In effect, you can only pick two nodes and switch them with similar results.

The procedure might look like this. Here is the unrooted tree in question

species1 +----------\               /----------+species4
                     /      |      \
species2 +----------/       |       \----------+species5

If we swap two nodes that are connected by a branch

species5 +----------\               /----------+species4
                     /      |      \
species2 +----------/       |       \----------+species5
Subtree Pruning and Regraft
Tree Bisection and Reconnection

Leave a Reply