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 host tree.
The code of Eucalypt may be recovered here. It is under the Cecill License. The nexus files which were used in our study can be found here. A documentation is available here.
Eucalypt comes also with a viewer, CophyTrees. More information is available here.
Finally, the robustness of the host-symbiont tree reconciliation method under editing or small perturbations of the input has been explored. More information, and other inputs and codes, can be found here.
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, 10(1):11, 2015.
Contacts: Blerina Sinaimeri and Marie-France Sagot
