5 Finding the best reconstruction(s)


In this context the "best" reconstruction is defined as that with the greatest number of cospeciation events (see Page, in press). TREEMAP offers two ways of finding the best, a simple heuristic search and an exhaustive search.

5.1 Heuristic search


The heuristic search uses a simple algorithm that attempts to find a single optimal reconstruction introducing successive host-switches until the number of cospeciations no longer increases. It is quick but is not guaranteed to find the best reconstruction (although in practise it does rather well). Note that it finds only one reconstruction - there may be others that are equally good, or better.

The heuristic algorithm is a useful way of quickly estimating the maximum number of cospeciation events. It is also used by the randomisation tests described below.


The reconstruction found by the program is not automatically stored, so if you want to keep it you will have to store it using the Store command (see above).


5.2 Exact search


TREEMAP also features an exact algorithm that will find all the optimal reconstructions. This algorithm is (a lot) slower than the heuristic method.


Be warned that if you use the exact search all currently stored reconstructions will be lost as TREEMAP uses that storage space for the optimal reconstructions. Also, the exact search can take a long time. However, the program can sit in the background allowing you to get on with other tasks (Windows version only).


Choose the Exact command from the Reconstruction menu. TREEMAP will display a dialog box showing its progress. You can abandon the search by clicking on the Cancel or Stop button.

Once the search is completed the optimal reconstructions are stored in memory and can be accessed using the popup menu in the Reconstruction window (see above).