Skip to contents

bab finds all most parsimonious trees.


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



an object of class phyDat.


a phylogenetic tree an object of class phylo, otherwise a pratchet search is performed.


defines how much information is printed during optimization.


Further arguments passed to or from other methods


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


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. On the positive side bab is not like many other implementations restricted to binary or nucleotide data.


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


Klaus Schliep based on work on Liam Revell


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