neighbor_joining

biotite.sequence.phylo.neighbor_joining(distances)

Perform hierarchical clustering using the neighbor joining algorithm. [1][2]

In contrast to UPGMA this algorithm does not assume a constant evolution rate. The resulting tree is considered to be unrooted.

Parameters:

distancesndarray, shape=(n,n)

Pairwise distance matrix.

Returns:

treeTree

A rooted tree. The index attribute in the leaf TreeNode objects refer to the indices of distances.

Raises:

ValueError

If the distance matrix is not symmetric or if any matrix entry is below 0.

Notes

The created tree is binary except for the root node, that has three child notes

References

[1]

N. Saitou, M. Nei, “The neighbor-joining method: a new method for reconstructing phylogenetic trees.,” Molecular Biology and Evolution, vol. 4, pp. 406–425, July 1987. doi: 10.1093/oxfordjournals.molbev.a040454

[2]

J. A. Studier, K. J. Keppler, “A note on the neighbor-joining algorithm of Saitou and Nei.,” Molecular Biology and Evolution, vol. 5, pp. 729–731, July 1988. doi: 10.1093/oxfordjournals.molbev.a040527

Examples

>>> distances = np.array([
...     [0, 1, 7, 7, 9],
...     [1, 0, 7, 6, 8],
...     [7, 7, 0, 2, 4],
...     [7, 6, 2, 0, 3],
...     [9, 8, 4, 3, 0],
... ])
>>> tree = neighbor_joining(distances)
>>> print(tree.to_newick(include_distance=False))
(3,(2,(1,0)),4);

Gallery

Phylogenetic tree of a protein family

Phylogenetic tree of a protein family