Branch and bound for finding all most parsimonious trees

bab finds all most parsimonious trees (Hendy and Penny 1982) .

Usage

bab(data, tree = NULL, trace = !getOption("quiet"), ...)

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

Value

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

Details

This implementation can be 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, Huber, Penny, and Moulton (2005) to improve the lower bound and optimtsations from White and Holland (2011) .
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.

References

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

Holland BR, Huber KT, Penny D, Moulton V (2005). “The MinMax Squeeze: Guaranteeing a Minimal Tree for Population Data.” Molecular Biology and Evolution, 22(2), 235-242. doi:10.1093/molbev/msi010 .

White WTJ, Holland BR (2011). “Faster exact maximum parsimony search with XMP.” Bioinformatics, 27(10), 1359-1367. ISSN 1367-4803. doi:10.1093/bioinformatics/btr147 .

Author

Klaus Schliep klaus.schliep@gmail.com based on work on Liam Revell

Examples


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