ELynx.Data.Tree.Distance

Creation date: Thu Jun 13 17:15:54 2019.

Various distance functions for phylogenetic trees (and trees with branch lengths in general).

The functions provided in this module return distances for unrooted trees. See comments of symmetric, branchScore, and bipartitionToBranch, as well as the documentation of treedist.

It is a little unfortunate that Tree data type, which represents rooted trees, is also used in this module. However, rooted trees are much easier to handle. In the future, a separate data type for unrooted trees may be introduced. In theory, this is quite straight forward, for example, using algebraic graphs. Difficulties may arise because the branches of an unrooted tree are undirected.

Documentation

symmetric :: Ord a => Tree e1 a -> Tree e2 a -> Either String Int

Symmetric (Robinson-Foulds) distance between two trees.

Although a rooted tree data type is used, the distance between the unrooted trees is returned.

Return Nothing if the trees contain different leaves.

XXX: Comparing a list of trees may recompute bipartitions.

incompatibleSplits :: (Show a, Ord a) => Tree e1 a -> Tree e2 a -> Either String Int

Number of incompatible splits.

Similar to symmetric but all bipartitions induced by multifurcations are considered. For a detailed description of how the distance is calculated, see bipartitionCompatible.

A multifurcation on a tree may (but not necessarily does) represent missing information about the order of bifurcations. In this case, it is interesting to get a set of compatible bifurcations of the tree. For example, the star tree

(A,B,C,D);

induces the following bipartitions:

A|BCD
B|ACD
C|ABD
D|ABC

However, the tree is additionally compatible with the following hidden bipartitions:

AB|CD
AC|BD
AD|BC

For an explanation of how compatibility of partitions is checked, see compatible. Before using compatible, bipartitions are simply converted to partitions with two subsets.

A bipartition is incompatible with a tree if it is incompatible with all induced multifurcations of the tree.

XXX: Comparing a list of trees with this function recomputes bipartitions.

branchScore :: (Measurable e1, Measurable e2, Ord a) => Tree e1 a -> Tree e2 a -> Either String Double

Compute branch score distance between two trees.

Although a rooted tree data type is used, the distance between the unrooted trees is returned.

XXX: Comparing a list of trees with this function recomputes bipartitions.