bab: 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 optimisation.
…
Further arguments passed to or from other methods
Value
bab returns all most parsimonious trees in an object of class
multiPhylo.
Details
This implementation is very slow and depending on the data may take very
long time. In the worst case all (2n-5)!! possible trees have to be
examined. For 10 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. It uses a very basic heuristic approach of
MinMax Squeeze (Holland et al. 2005) to improve the lower bound. On the
positive side bab is not like many other implementations restricted
to binary or nucleotide data.
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