Copyright | (c) Dominik Schrempf 2021 |
---|---|

License | GPL-3.0-or-later |

Maintainer | dominik.schrempf@gmail.com |

Stability | unstable |

Portability | portable |

Safe Haskell | None |

Language | Haskell2010 |

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 Source #

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 Source #

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 Source #

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.