skbio.tree.nni#

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

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:
treeskbio.TreeNode

Input phylogenetic tree to be rearranged.

dmskbio.DistanceMatrix

Input distance matrix containing distances between taxa.

balancedbool, optional

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

neg_as_zerobool, 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
On this page