skbio.tree.nni#

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

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

Parameters:
treeskbio.TreeNode

Input phylogenetic tree to be rearranged.

dmskbio.DistanceMatrix

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).

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