elynx-tree-0.7.2.2: Handle phylogenetic trees
Copyright2021 Dominik Schrempf
LicenseGPL-3.0-or-later
Maintainerdominik.schrempf@gmail.com
Stabilityunstable
Portabilityportable
Safe HaskellSafe-Inferred
LanguageHaskell2010

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
(Read a, Ord a) => Read (Bipartition a) Source # 
Instance details

Defined in ELynx.Tree.Bipartition

Show a => Show (Bipartition a) Source # 
Instance details

Defined in ELynx.Tree.Bipartition

NFData a => NFData (Bipartition a) Source # 
Instance details

Defined in ELynx.Tree.Bipartition

Methods

rnf :: Bipartition a -> () #

Eq a => Eq (Bipartition a) Source # 
Instance details

Defined in ELynx.Tree.Bipartition

Ord a => Ord (Bipartition a) Source # 
Instance details

Defined in ELynx.Tree.Bipartition

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.