Skip to main content
`Ctrl`+`K`

# skbio.tree.nni

skbio.tree.nni(tree, dm, balanced=True, neg_as_zero=True)

  Perform nearest neighbor interchange (NNI) to improve a phylogenetic tree.

  Added in version 0.6.2.

  Changed in version 0.6.3: Computational efficiency significantly improved.

  Parameters:
    tree skbio.TreeNode

      Input phylogenetic tree to be rearranged.

    dm skbio.DistanceMatrix

      Input distance matrix containing distances between taxa.

    balanced bool, optional

      Use the OLS framework (False) or the balanced framework (True, default).

    neg_as_zero bool, optional

      If True (default), convert negative branch lengths into zeros.

  Returns:
    TreeNode

      Rearranged phylogenetic tree.

  Notes

  Nearest neighbor interchange (NNI) is a method for tree rearrangement aiming at optimizing a given tree topology according to certain criteria. It iteratively swaps neighboring branches that could result in a better tree, until no such swaps remain in the optimized tree.

  This function performs NNI for the minimum evolution (ME) problem on phylogenetic trees. The implementation is based on [1]. Two versions of the method are provided: the FastNNI algorithm (`balanced=False`) based on an ordinary least squares (OLS) framework (see also `gme`) and the BNNI algorithm (`balanced=True`) based on a balanced framework (see also `bme`). The former is more scalable than the latter.

  The input tree may be rooted or unrooted, and it must be strictly bifurcating. One can apply `is_bifurcating` or `bifurcate` to check or make a bifurcating tree. The set of taxa in the tree (accessible via `subset`) must match those in the distance matrix.

  The output tree is unrooted, with the first taxon in the distance matrix placed as a child of the root node. Branch lengths are assigned according to the framework of choice. See also `nj` regarding rooting an unrooted tree and dealing with potential negative branch lengths.

  The same methods were provided by FastME [2]. See `gme` for notes on this.

  References

  [1]

  Desper, R., & Gascuel, O. (2002). Fast and accurate phylogeny reconstruction algorithms based on the minimum-evolution principle. J Comput Biol, 9(5), 687-705.

  [2]

  Lefort, V., Desper, R., & Gascuel, O. (2015). FastME 2.0: a comprehensive, accurate, and fast distance-based phylogeny inference program. Mol Biol Evol, 32(10), 2798-2800.

  Examples

      >>> from skbio import DistanceMatrix, TreeNode
      >>> from skbio.tree import nni

  Define a distance matrix describing the distances between five taxa.

      >>> 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'])

  Provide a tree to be rearranged. The tree must be bifurcating. Branches lengths are not required.

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

  Perform nearest neighbor interchange (NNI). This will rearrange tree topolgy to better approach the minimum evolution criterion.

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

  Besides rearranging tree topology, estimated branch lengths are assigned to the tree.

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