Navigation Banner
 
  HyPhy Documentation: Standard Analyses: Methods: Nearest Neighbor Interchange

    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.

 
Sergei L. Kosakovsky Pond and Spencer V. Muse, 1997-2002