skbio.tree.nni#

skbio.tree.nni(tree, dm, allow_edge_estimation=True, inplace=True, balanced=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.

allow_edge_estimationbool, optional

Whether to perform an OLS-based estimation of edge values (True, default) or return a tree without edge values assigned (False).

inplacebool, optional

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

balancedbool, optional

Whether to use the minimum evolution framework or the balanced minimum evolution framework. The definition of average distance between subtrees either ignores subtree size (True, default) or calculates based on subtree size (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 and the BNNI algorithm (BNNI)[R2d0c0545a225-1]_.

The two versions of NNI are due to the relationship with minimum evolution and the use of average distances between subtrees. FastNNI is based on the Minimum Evolution (ME) problem while BNNI is based on the Balanced Minimum Evolution (BME) problem. In BME the sizes of subtrees are ignored while ME considers the size of subtrees in the calculation of average distance.

For both versions of NNI, 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 nni

>>> 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), here the BNNI version is used. 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