bab: Branch and bound for finding all most parsimonious trees

In KlausVigo/phangorn: Phylogenetic Reconstruction and Analysis

Branch and bound for finding all most parsimonious trees

Description

bab finds all most parsimonious trees.

Usage

bab(data, tree = NULL, trace = 1, ...)

Arguments

data	an object of class phyDat.
tree	a phylogenetic tree an object of class phylo, otherwise a pratchet search is performed.
trace	defines how much information is printed during optimization.
...	Further arguments passed to or from other methods

Details

This implementation is very slow and depending on the data may take very long time. In the worst case all (2n-5)!! = 1 \times 3 \times 5 \times \ldots \times (2n-5) possible trees have to be examined, where n is the number of species / tips. For ten species there are already 2027025 tip-labelled unrooted trees. It only uses some basic strategies to find a lower and upper bounds similar to penny from phylip. bab uses a very basic heuristic approach of MinMax Squeeze (Holland et al. 2005) to improve the lower bound.
bab might return multifurcating trees. These multifurcations could be resolved in all ways.
On the positive side bab is not like many other implementations restricted to binary or nucleotide data.

Value

bab returns all most parsimonious trees in an object of class multiPhylo.

Author(s)

Klaus Schliep [e-mail] based on work on Liam Revell

References

Hendy, M.D. and Penny D. (1982) Branch and bound algorithms to determine minimal evolutionary trees. Math. Biosc. 59, 277-290

Holland, B.R., Huber, K.T. Penny, D. and Moulton, V. (2005) The MinMax Squeeze: Guaranteeing a Minimal Tree for Population Data, Molecular Biology and Evolution, 22, 235–242

White, W.T. and Holland, B.R. (2011) Faster exact maximum parsimony search with XMP. Bioinformatics, 27(10),1359–1367

See Also

pratchet, dfactorial

Examples

data(yeast)
dfactorial(11)
# choose only the first two genes
gene12 <- yeast[, 1:3158]
trees <- bab(gene12)

KlausVigo/phangorn documentation built on Nov. 5, 2024, 11 a.m.