bab

0th

Percentile

Branch and bound for finding all most parsimonious trees

bab finds all most parsimonious trees.

Keywords
cluster
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

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.

Value

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

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

Aliases
  • bab
  • BranchAndBound
Examples
# NOT RUN {
data(yeast)
dfactorial(11)
# choose only the first two genes
gene12 <- subset(yeast, , 1:3158, site.pattern=FALSE)
trees <- bab(gene12)

# }
Documentation reproduced from package phangorn, version 2.5.5, License: GPL (>= 2)

Community examples

Looks like there are no examples yet.