ELynx.Tree.Distance

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

Various distance functions for trees.

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 the Tree data type represents rooted trees. However, rooted trees are much easier to handle computationally. In the future, a separate data type for unrooted trees may be introduced, 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 recomputes 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 recomputes bipartitions.

branchScore :: (HasLength e1, HasLength 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 recomputes bipartitions.