In article <87hdqe$hcv$1 at mercury.hgmp.mrc.ac.uk>,
Korbinian Strimmer <korbinian.strimmer at zoology.oxford.ac.uk> wrote:
>in response to Brice Quenoville <quenovib at si.edu>
>> 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.
>From Quenoville's reported results, the branch and bound for ML in PAUP* is
not doing as well as exhaustive search, and even takes longer! (I can't be
critical as in PHYLIP one can't even do it). One issue is that one would
have to optimize the branch lengths for each topology searched. If PAUP* is
being a bit quick-and-dirty about that, it might get into trouble as was
reported. It could get onto the wrong track and get a worse likelihood.
The reason no one has written a paper on branch and bound for ML is that
we don't know a good way to compute a tight bound. It thus won't be much
better than exhaustive search. The likelihood does get lower as one adds
species but there is no easy way to make a close, but pessimistic estimate
of by how much, without doing the adding and checking. That is what is
needed for B&B.
--
Joe Felsenstein joe at genetics.washington.edu
Dept. of Genetics, Univ. of Washington, Box 357360, Seattle, WA 98195-7360 USA
---
