Heuristic searches

Sikes dss95002 at uconnvm.uconn.edu
Tue Apr 7 10:09:14 EST 1998


To those experienced with heuristic searching using PAUP*:

I have stumbled upon what seems to be a means by which shortest trees can 
be found far quicker and with high confidence than by the method I 
previously used.  First the details: I have a large enough data set (76 
taxa) that I cannot do an exhaustive or Branch& Bound search.  It was 
taught to me that the most rigorous options for heuristic searching 
should include at least 100 replicates of randomly started independent 
searches (with other settings at the PAUP defaults)-

This, even on fast computers, would take many days.  I noticed, however, 
that much of the time was spent "swapping" tree branches on "islands" of 
suboptimal length (e.g. I knew that a tree of length 200 was possible but 
many of the islands found yielded trees no better than 210 or 220 etc.).  

So I examined the PAUP heuristic searching options and one option allows 
users to limit the number of trees found for a single replicate before 
starting another replicate.  Therefore, if one's dataset allows many mpts 
(which take hours to days to swap) one can set a limit of say 100 trees 
or 50 trees saved per "island".  With this setting PAUP can crank through 
100 or even 200 replicates in a few hours-(and, of course, if one wants 
to wait a few days one can get a few thousand replicates completed)

PAUP  will save the shortest trees in memory and once the run is complete 
you can start the search again specifying that PAUP use the "trees in 
memory" as the starting trees.  This will result in complete swapping on 
the "best" island(s) yielding all the mpts of that length (and maybe  
some shorter...).

The reason I am posting this is that it seems too good to be true- 
shaving 90% of the time off a large-dataset search must have some serious 
cons but I'd like to hear from someone who knows what the cons are (and 
if this has been rigorously tested in a systematic fashion & published)...

Thank You,

Derek Sikes


++++++++++++++++++++++++++++++++++++++++++++++
Derek Sikes
Dept. of Ecology and Evol. Biology U-43
University of Connecticut
Storrs, CT 06269  USA

dss95002 at uconnvm.uconn.edu
http://www.eeb.uconn.edu/grads/sikes.htm

"Remember that Truth alone is the matter you are in Search after; and if 
you have been mistaken, let no Vanity reduce you to persist in your 
mistake." Henry Baker, London, 1785
++++++++++++++++++++++++++++++++++++++++++++++





More information about the Mol-evol mailing list