Copyright | (c) Dominik Schrempf 2020 |
---|---|
License | GPL-3.0-or-later |
Maintainer | dominik.schrempf@gmail.com |
Stability | unstable |
Portability | portable |
Safe Haskell | None |
Language | Haskell2010 |
Creation date: Thu Jan 17 16:08:54 2019.
The purpose of this module is to facilitate usage of Tree
s in phylogenetic
analyses. A phylogeny is a Tree
with unique leaf labels, and unordered
sub-forest.
Using the Tree
data type has some disadvantages.
- All trees are rooted. Unrooted trees can be treated with a rooted data structure, as it is used here. However, some functions may be meaningless.
- Changing branch labels, node labels, or the topology of the tree are slow operations, especially, when the changes are close to the leaves of the tree.
- Internally, the underlying
Tree
data structure stores the sub-forest as an ordered list. Hence, we have to do some tricks when comparing phylogenies (seeequal
), and comparison is slow. - Uniqueness of the leaves is not ensured by the data type, but has to be
checked at runtime. Functions relying on the tree to have unique leaves do
perform this check, and return
Left
with an error message, if the tree has duplicate leaves.
Note: Tree
s are rooted.
Note: Tree
s encoded in Newick format correspond to rooted trees. By
convention only, a tree parsed from Newick format is usually thought to be
unrooted, when the root node is multifurcating and has three children. This
convention is not used here. Newick trees are just parsed as they are, and a
rooted tree is returned.
Trees with multifurcating root nodes can be rooted using outgroup
.
Trees with bifurcating root nodes can be changed with rootAt
or midpoint
;
a list of all rooted trees is returned by roots
.
Synopsis
- equal :: (Eq e, Eq a) => Tree e a -> Tree e a -> Bool
- intersect :: (Semigroup e, Eq e, Ord a) => Forest e a -> Either String (Forest e a)
- bifurcating :: Tree e a -> Bool
- outgroup :: (Semigroup e, Splittable e, Ord a) => Set a -> a -> Tree e a -> Either String (Tree e a)
- midpoint :: (Semigroup e, Splittable e, Measurable e) => Tree e a -> Either String (Tree e a)
- roots :: (Semigroup e, Splittable e) => Tree e a -> Either String (Forest e a)
- rootAt :: (Semigroup e, Splittable e, Eq a, Ord a) => Bipartition a -> Tree e a -> Either String (Tree e a)
- data Phylo = Phylo {}
- toPhyloTree :: (Measurable e, Supported e) => Tree e a -> Tree Phylo a
- measurableToPhyloTree :: Measurable e => Tree e a -> Tree Phylo a
- supportedToPhyloTree :: Supported e => Tree e a -> Tree Phylo a
- phyloToLengthTree :: Tree Phylo a -> Either String (Tree Length a)
- phyloToSupportTree :: Tree Phylo a -> Either String (Tree Support a)
- phyloToSupportTreeUnsafe :: Tree Phylo a -> Tree Support a
- data PhyloExplicit = PhyloExplicit {}
- toExplicitTree :: Tree Phylo a -> Either String (Tree PhyloExplicit a)
Functions
equal :: (Eq e, Eq a) => Tree e a -> Tree e a -> Bool Source #
The equality check is slow because the order of children is considered to be arbitrary.
bifurcating :: Tree e a -> Bool Source #
Check if a tree is bifurcating.
A Bifurcating tree only contains degree one (leaves) and degree three nodes (internal bifurcating nodes).
outgroup :: (Semigroup e, Splittable e, Ord a) => Set a -> a -> Tree e a -> Either String (Tree e a) Source #
Resolve a multifurcating root using an outgroup.
A bifurcating root node with the provided label is introduced. The affected
branch is split
.
Note, the degree of the former root node is decreased by one.
If the root node is bifurcating, use rootAt
.
Return Left
if
- the root node is not multifurcating;
- the tree has duplicate leaves;
- the provided outgroup is not found on the tree or is polyphyletic.
midpoint :: (Semigroup e, Splittable e, Measurable e) => Tree e a -> Either String (Tree e a) Source #
Root tree at the midpoint.
Return Left
if
- the root node is not bifurcating.
roots :: (Semigroup e, Splittable e) => Tree e a -> Either String (Forest e a) Source #
For a rooted tree with a bifurcating root node, get all possible rooted trees.
The root node (label and branch) is moved.
For a tree with l=2
leaves, there is one rooted tree. For a bifurcating
tree with l>2
leaves, there are (2l-3)
rooted trees. For a general tree
with a bifurcating root node, and a total number of n>2
nodes, there are
(n-2) rooted trees.
Moving a multifurcating root node to another branch would change the degree
of the root node. Hence, a bifurcating root is required. To resolve a
multifurcating root, please use outgroup
.
Connect branches according to the provided Semigroup
instance.
Upon insertion of the root, split the affected branch into one out of two equal entities according to a given function.
Return Left
if the root node is not bifurcating
.
rootAt :: (Semigroup e, Splittable e, Eq a, Ord a) => Bipartition a -> Tree e a -> Either String (Tree e a) Source #
Root a tree at a specific position.
Root the tree at the branch defined by the given bipartition. The original root node is moved to the new position.
The root node must be bifurcating (see roots
and outgroup
).
Connect branches according to the provided Semigroup
instance.
Upon insertion of the root, split the affected branch according to the
provided Splittable
instance.
Return Left
, if:
- the root node is not bifurcating;
- the tree has duplicate leaves;
- the bipartition does not match the leaves of the tree.
Branch labels
Branch label for phylogenetic trees.
Branches may have a length and a support value.
Instances
Eq Phylo Source # | |
Ord Phylo Source # | |
Read Phylo Source # | |
Show Phylo Source # | |
Generic Phylo Source # | |
Semigroup Phylo Source # | |
NFData Phylo Source # | |
Defined in ELynx.Tree.Phylogeny | |
ToJSON Phylo Source # | |
Defined in ELynx.Tree.Phylogeny | |
FromJSON Phylo Source # | |
type Rep Phylo Source # | |
Defined in ELynx.Tree.Phylogeny type Rep Phylo = D1 ('MetaData "Phylo" "ELynx.Tree.Phylogeny" "elynx-tree-0.5.0-LNeltioHkaNAWvI1l3dP6J" 'False) (C1 ('MetaCons "Phylo" 'PrefixI 'True) (S1 ('MetaSel ('Just "brLen") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Maybe Length)) :*: S1 ('MetaSel ('Just "brSup") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Maybe Support)))) |
toPhyloTree :: (Measurable e, Supported e) => Tree e a -> Tree Phylo a Source #
Set all branch lengths and support values to Just
the value.
Useful to export a tree with branch lengths in Newick format.
measurableToPhyloTree :: Measurable e => Tree e a -> Tree Phylo a Source #
phyloToLengthTree :: Tree Phylo a -> Either String (Tree Length a) Source #
If root branch length is not available, set it to 0.
Return Left
if any other branch length is unavailable.
phyloToSupportTree :: Tree Phylo a -> Either String (Tree Support a) Source #
Set branch support values of branches leading to the leaves and of the root branch to maximum support.
Return Left
if any other branch has no available support value.
phyloToSupportTreeUnsafe :: Tree Phylo a -> Tree Support a Source #
Set all unavailable branch support values to maximum support.
data PhyloExplicit Source #
Explicit branch label with branch length and branch support value.
Instances
toExplicitTree :: Tree Phylo a -> Either String (Tree PhyloExplicit a) Source #
Conversion to a PhyloExplicit
tree.
See phyloToLengthTree
and phyloToSupportTree
.