Phylogenetic tree reconciliation is the approach of choice for investigating the co-evolution of sets of organisms such as hosts and parasites. It consists in a mapping between the parasite tree and the host tree using event-based maximum parsimony. Given a cost model for the events, many optimal reconciliations are however possible. Any further biological interpretation of them must therefore take this into account, making the capacity to enumerate all optimal solutions a crucial point.
Eucalypt is a polynomial-delay algorithm for enumerating all optimal reconciliations. To facilitate their interpretation, those solutions are also classified in terms of how many of each event they contain. Moreover, Eucalypt can also just count all solutions in polynomial time. Finally, Eucalypt may also run in a restricted mode where host-switches are allowed to happen only between species that are within some fixed distance along the hosttree.
For more details about the method, please refer to our paper:
B. Donati, C. Baudet, B. Sinaimeri, P. Crescenzi, and M.-F. Sagot. Eucalypt: Efficient tree reconciliation enumerator. Algorithms for Molecular Biology, 2014, (in press).