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.

Note

The FastNNI and BNNI algorithms are mathematically equivalent to the “NNI_OLS” and “NNI_BalME” methods provided by the FastME program [2], respectively. This function was implemented following the original paper [1], and there is no guarantee that it will precisely mirror FastME’s output. Although in practices it usually generates identical or equally optimal trees as FastME does.

The set of taxa in the tree (accessible via subset) must match those in the distance matrix. The tree may be rooted or unrooted, but it must be strictly bifurcating. One can apply is_bifurcating to check if the tree is strictly bifurcating:

tree.is_bifurcating(strict=True, include_self=False)

If not, one can apply bifurcate and prune to convert the tree into a bifurcating one.

A special case is when the root node itself is a taxon (and it is connected to only one child), a format that can be generated by some phylogenetic analyses (e.g., by calling root_at on a tip). This format is currently unsupported by this function. One needs to reroot the tree in such a case.

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.

References

[1] (1,2)

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