# 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).