Nearest Neighbor Interchange is a tree topology search strategy
which attempts to improve the likelihood of a given tree by performing the
following operations on the tree.
Each internal branch branch of a binary unrooted tree (as in Figure 1), has 4 subtrees
"connected" to it (a subtree may consist of a single node). NNI exchanges those
subtrees to obtain a new tree. There are only two exchanges which lead to new unrooted
binary trees (as in Figure 2 and Figure 3). The procedure is usually repeated for each
internal branch, until no further likelihood improvements can be obtained.
A binary unrooted tree with N>2 leaves will have N-3
internal branches, thus a pass of the NNI algorithm, which tries two trees per internal branch
will examine 2(N-3) new trees.
|
|
|
Figure 1.
Original Tree.
|
Figure 2.
Exchange 1 and 3.
|
Figure 3.
Exchange 2 and 3.
|
|