Alan Rogers asks:
> I have a question about the "random addition sequence" option of PAUP and
> PHYLIP, which allows one to search from a wide variety of initial trees,
> each defined by the order in which taxa are introduced to the search
> algorithm. The question is: Is there any reason for confidence that the
> global optimum can be found by starting from any of these initial points?
> If not, wouldn't it be better to initialize each search with a random tree
> generated by some algorithm such as the coalescent?
There are no theorems that I am aware of guaranteeing that the strategy
of successive addition (each time in the best place) of species will
always be able to find the most parsimonious tree even if we try all possible
orders of addition of species. But I think most of us who have tried writing
these algorithms have a "gut feeling" that this will do better than
starting from a random tree, on the grounds that fewer starting points
would be required to find good trees. Starting from a random tree one
will initially have members of clades widely scattered and separated by
members of other clades. It would then take massive rearrangement to put the
groups together.
This indicates that starting from random trees the strategy of local
rearrangements will most often fail to come close to an optimal tree,
even though some of the billions of random trees would guarantee finding
the most parsimonious tree.
By the way, the next version of PHYLIP (3.5, due in a couple of months) will
allow multiple searches with different addition sequences to be done in one
run, with the overall most parsimonious trees found being saved. (David
Swofford had pointed out that PHYLIP 3.4 does not allow more than one random
addition sequence to be tried per run).
-----
Joe Felsenstein, Dept. of Genetics, Univ. of Washington, Seattle, WA 98195
Internet: joe at genetics.washington.edu (IP No. 128.95.12.41)
Bitnet/EARN: felsenst at uwavm
