skbio.tree.gme#

skbio.tree.gme(dm, allow_edge_estimation=True)[source]#

Perform greedy minimum evolution (GME) for phylogenetic reconstruction.

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

Returns:
TreeNode

Reconstructed phylogenetic Tree with estimated edge values (if allow_edge_estimation is True).

Notes

Greedy Minimum Evolution (GME) is a distance-based algorithm for phylogenetic reconstruction utilizing the minimum evolution principle for selecting a tree topology with the lowest sum of branch lengths according to a given method of estimating branch lengths. Ordinary Least Squares (OLS) is a natural framework for edge estimation as it is statistically consistent with minimum evolution and is used for GME.

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 gme

>>> 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 Greedy Minimum Evoltuion (GME) and construct the minimum evolution tree representing the relationship between those taxa. This is returned as a TreeNode object.

>>> tree = gme(dm)
>>> print(tree.ascii_art())
                    /-monkey
-human--- /--------|
                   |          /-pig
                    \--------|
                             |          /-chicken
                              \--------|
                                        \-rat

Notice that, unlike neighbor joining, the tree is rooted at a taxa/leaf node. This will allow it to have nearest neighbor interchange performed on it without needing to re-root the tree.

On this page