Skip to main content
`Ctrl`+`K`

# skbio.tree.nni

skbio.tree.nni(tree, dm, inplace=True)

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

  Parameters:
    tree skbio.TreeNode

      Input phylogenetic tree to be rearranged.

    dm skbio.DistanceMatrix

      Input distance matrix containing distances between taxa.

    inplace bool, optional

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

  Returns:
    TreeNode

      Rearranged phylogenetic tree (if `inplace` is `True`).

  Notes

  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.

  References

  [1]

  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.

  Examples

  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 = TreeNode.read(["(((human,chicken),(rat,monkey)))pig;"])
      >>> print(tree.ascii_art())
                                    /-human
                          /--------|
                         |          \-chicken
      -pig----- /--------|
                         |          /-rat
                          \--------|
                                    \-monkey

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

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

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

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