skbio.tree.nni(tree, dm, inplace=True)[source]#

Perform nearest neighbor interchange (NNI) on a phylogenetic tree.


Input phylogenetic tree to be rearranged.


Input distance matrix containing distances between taxa.

inplacebool, optional

Whether manipulate the tree in place (True, default) or return a copy of the tree (False).


Rearranged phylogenetic tree (if inplace is True).


NNI algorithm for minimum evolution problem on phylogenetic trees. It rearranges an initial tree topology by performing subtree exchanges such that the distance is minimized. This implementation is based on the FastNNI algorithm [1].

The input tree is required to be binary and rooted at a leaf node such that there is a unique descendant from the root.



Desper R, Gascuel O. Fast and accurate phylogeny reconstruction algorithms based on the minimum-evolution principle. J Comput Biol. 2002;9(5):687-705. doi: 10.1089/106652702761034136. PMID: 12487758.


Define a new distance matrix object describing the distances between five taxa: human, monkey, pig, rat, and chicken.

>>> from skbio import DistanceMatrix
>>> from skbio.tree import nj
>>> dm = DistanceMatrix([[0, 0.02,  0.18,  0.34,  0.55],
...                      [0.02,  0, 0.19, 0.35,  0.55],
...                      [0.18, 0.19,  0,  0.34,  0.54],
...                      [0.34, 0.35,  0.34,  0,  0.62],
...                      [0.55,  0.55,  0.54,  0.62,  0]],
...                      ['human','monkey','pig','rat','chicken'])

Also, provide a tree topology to be rearranged. The tree provided is required to be a binary tree rooted at a leaf node.

Note that the tree provided does not require to have assigned edge lengths.

>>> from skbio.tree import TreeNode
>>> tree =["(((human,chicken),(rat,monkey)))pig;"])
>>> print(tree.ascii_art())
                   |          \-chicken
-pig----- /--------|
                   |          /-rat

Perform nearest neighbor interchange (NNI). By default, the tree is rearrangede in place.

>>> nni(tree, dm)
>>> print(tree.ascii_art())
                   |          \-chicken
-pig----- /--------|
                   |          /-monkey

Besides rearranging the tree, estimated edge lengths are assigned to the tree.

>>> rat = tree.find('rat')
>>> print(rat.length)