skbio.tree.bme#

skbio.tree.bme(dm, neg_as_zero=True, **kwargs)[source]#

Perform balanced minimum evolution (BME) for phylogenetic reconstruction.

Added in version 0.6.3.

Parameters:
dmskbio.DistanceMatrix

Input distance matrix containing distances between taxa.

neg_as_zerobool, optional

If True (default), convert negative branch lengths into zeros.

Returns:
TreeNode

Reconstructed phylogenetic tree.

See also

gme
nni
nj

Notes

Balanced Minimum Evolution (BME) [1] is a refinement of the distance-based minimum evolution problem where the average distances between subtrees are independent of the sizes of the subtrees. This is referred to as a balanced (or simply BME) framework [2], as in contrast to the OLS framework used by GME (gme).

The BME algorithm implemented here uses a similar greedy algorithm as implemented in gme, but less scalable due to the need to update subtree distances as the tree topology changes. The algorithm is sub-O(n3) in time and O(n2) in space.

Refer to gme for the format of the output tree and subsequent treatments.

A BME-generated tree may be further improved by executing the BNNI algorithm implemented in nni (with balanced=True).

The same method was provided by FastME [3]. See gme for notes on this.

Note

Experimental feature: Add parallel=True will enable parallelization, which may increase the performance of the algorithm. This feature may not be stable and may be modified without notice in the future.

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]

Pauplin, Y. (2000). Direct calculation of a tree length using a distance matrix. J Mol Evol, 51, 41-47.

[3]

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

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 bme

>>> 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'])

Perform Balanced Minimum Evoltuion (BME) and construct the minimum evolution tree representing the relationship between those taxa. This is returned as a TreeNode object.

>>> tree = bme(dm)
>>> print(tree.ascii_art())
          /-monkey
         |
         |          /-pig
         |---------|
---------|         |          /-rat
         |          \--------|
         |                    \-chicken
         |
          \-human
On this page