jebl.evolution.trees
Class GreedyUnrootedConsensusTreeBuilder
java.lang.Object
jebl.evolution.trees.ConsensusTreeBuilder<Tree>
jebl.evolution.trees.GreedyUnrootedConsensusTreeBuilder
- All Implemented Interfaces:
- TreeBuilder<Tree>
public final class GreedyUnrootedConsensusTreeBuilder
- extends ConsensusTreeBuilder<Tree>
Builds greedy consensus tree given a set of unrooted trees.
Each edge in a tree "supports" a split, i.e. the partition of the taxa into two clades
(which you get by deleting the edge). A Majority consensus tree is built by finding
clades appearing in at least 50% of the trees or more. A Greedy consensus tree is a
refinement of a Majority tree where the splits are sorted by amount of support, and are
applied in order only if they are compatible (consistent) with the tree at that
stage. A user supplied threshold gives a lower bound on amount of support. If set t0
50% the Greedy method reduces to the majority consensus tree. At 100% it reduces to the
Strict consensus tree.
The implementation is relatively simple but tricky in parts. Each tree is scanned, and
support for each split/clade is collected in one table. The clade is represented by a
bitset, which always contains the (arbitrary) first node. The scan is made by going
over all nodes ordered in such a way that the subtree of exactly one edge of the node
has been completely scanned, so the node "knows" the set of tips of that subtree without
needing to re-scan the tree.
After all trees are scanned an initial consensus tree is constructed with one root and
all tips as children. The split set is scanned in order of decreasing support, and each
supported clade refines the tree by creating a new descendant for the node containing
the clade and re-attaching the clade to that new node. This is done only if the split
is compatible with the tree, i.e. only if the split is completely contained in a proper
subset of descendants of one node. This process continues until only clades with support
lower that the threshold are left.
The length of the consensus tree branches is computed from the average over all trees
containing the clade. The lengths of tip branches are computed by averaging over all
trees.
While the consensus tree is logically unrooted, we generate a rooted tree because we
can store attributes such as support only for nodes.
- Author:
- Joseph Heled
| Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
build
public final Tree build()