elynx-tree-0.6.0.0: Handle phylogenetic trees

ELynx.Tree.Bipartition

Description

Creation date: Fri Aug 30 15:28:17 2019.

Synopsis

# Documentation

groups :: Tree e a -> Tree e [a] Source #

Each node of a tree is root of an induced subtree. Set the node labels to the leaves of the induced subtrees.

# Data type

data Bipartition a Source #

A bipartition of a tree is a grouping of the leaves of the tree into two non-overlapping, non-empty sub sets.

For unrooted trees:

• Each branch partitions the leaves of the tree into two subsets, or a bipartition.

For rooted trees:

• A bifurcating root node induces a bipartition; see bipartition.
• Each inner node induces a bipartition by taking the leaves of the sub tree and the complement leaf set of the full tree.

The order of the two subsets of a Bipartition is meaningless. That is, Bipartitions are weird in that

Bipartition x y == Bipartition y x

is True. Also,

Bipartition x y > Bipartition y x

is False, even when x > y. That's why we have to make sure that for

Bipartition x y

we always have x >= y. We ensure by construction that the larger subset comes first, and so that equality checks are meaningful; see bp and bpUnsafe.

#### Instances

Instances details
 Eq a => Eq (Bipartition a) Source # Instance detailsDefined in ELynx.Tree.Bipartition Methods(==) :: Bipartition a -> Bipartition a -> Bool #(/=) :: Bipartition a -> Bipartition a -> Bool # Ord a => Ord (Bipartition a) Source # Instance detailsDefined in ELynx.Tree.Bipartition Methodscompare :: Bipartition a -> Bipartition a -> Ordering #(<) :: Bipartition a -> Bipartition a -> Bool #(<=) :: Bipartition a -> Bipartition a -> Bool #(>) :: Bipartition a -> Bipartition a -> Bool #(>=) :: Bipartition a -> Bipartition a -> Bool #max :: Bipartition a -> Bipartition a -> Bipartition a #min :: Bipartition a -> Bipartition a -> Bipartition a # (Read a, Ord a) => Read (Bipartition a) Source # Instance detailsDefined in ELynx.Tree.Bipartition Methods Show a => Show (Bipartition a) Source # Instance detailsDefined in ELynx.Tree.Bipartition MethodsshowsPrec :: Int -> Bipartition a -> ShowS #show :: Bipartition a -> String #showList :: [Bipartition a] -> ShowS # NFData a => NFData (Bipartition a) Source # Instance detailsDefined in ELynx.Tree.Bipartition Methodsrnf :: Bipartition a -> () #

bp :: Ord a => Set a -> Set a -> Either String (Bipartition a) Source #

Create a bipartition from two sets.

Ensure that the larger set comes first.

Return Left if one set is empty.

bpUnsafe :: Ord a => Set a -> Set a -> Bipartition a Source #

Create a bipartition from two sets.

Ensure that the larger set comes first.

toSet :: Ord a => Bipartition a -> Set a Source #

Conversion to a set containing both partitions.

bpHuman :: Show a => Bipartition a -> String Source #

Show a bipartition in a human readable format. Use a provided function to extract information of interest.

# Work with Bipartitions

bipartition :: Ord a => Tree e a -> Either String (Bipartition a) Source #

For a bifurcating root, get the bipartition induced by the root node.

Return Left if - the root node is not bifurcating; - a leave set is empty.

bipartitions :: Ord a => Tree e a -> Either String (Set (Bipartition a)) Source #

Get all bipartitions of the tree.

Return Left if the tree contains duplicate leaves.

getComplementaryLeaves :: Ord a => Set a -> Tree e (Set a) -> [Set a] Source #

Report the complementary leaves for each child.

bipartitionToBranch :: (Semigroup e, Ord a) => Tree e a -> Either String (Map (Bipartition a) e) Source #

Convert a tree into a Map from each Bipartition to the branch inducing the respective Bipartition.

Since the induced bipartitions of the daughter branches of a bifurcating root node are equal, the branches leading to the root have to be combined in this case. See http://evolution.genetics.washington.edu/phylip/doc/treedist.html and how unrooted trees are handled.

Further, branches connected to degree two nodes also induce the same bipartitions and have to be combined.

For combining branches, a binary function is required. This requirement is encoded in the Semigroup type class constraint (see prune).

Return Left if the tree contains duplicate leaves.