Skip to main content
`Ctrl`+`K`

# skbio.tree.bme

skbio.tree.bme(dm, neg_as_zero=True, **kwargs)

  Perform balanced minimum evolution (BME) for phylogenetic reconstruction.

  Added in version 0.6.3.

  Parameters:
    dm skbio.DistanceMatrix

      Input distance matrix containing distances between taxa.

    neg_as_zero bool, 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