reference to ML B&B

Korbinian Strimmer korbinian.strimmer at zoology.oxford.ac.uk
Sat Feb 5 07:30:26 EST 2000



> Some people told me here that "branch and bound"  is good for parsimony
> criteria but may get lost in ML search because it is dealing with
> probabilities and not number of steps. Is that so true that a branch and
> bound method is not highly commendable for ML search??

As far as I know "branch and bound" is a general exact search algorithm
(not necessarily restricted to tree topology search) that *guarantees* to
find precisely the same best solution as would an exhaustive search.
The advantage of "branch and bound" over an exhaustive search obviously is
that it is clever enough to exclude (possibly large) parts of the search  
space.

For parsimony tree reconstruction Hendy & Penny (1982) have shown that
"branch and bound" can be applied.  I wonder whether there is a paper
showing that this principle works with ML as well (ie as a means do an
exact search).  I haven't seen one but I am sure there is one and I must
have missed it somehow.

Any hints to such a paper?

Korbinian Strimmer

---







More information about the Mol-evol mailing list