Some Problems Related to the Space of Optimal Tree Reconciliations (Invited Talk)

Tree reconciliation is a general framework for investigating the evolution of strongly dependent systems as hosts and parasites or genes and species, based on their phylogenetic information. Indeed, informally speaking, it reconciles any differences between two phylogenetic trees by means of biological events. Tree reconciliation is usually computed according to the parsimony principle, that is, to each evolutionary event a cost is assigned and the goal is to find tree reconciliations of minimum total cost. Unfortunately, the number of optimal reconciliations is usually huge and many biological applications require to enumerate and to examine all of them, so it is necessary to handle them. In this paper we list some problems connected with the management of such a big space of tree reconciliations and, for each of them, discuss some known solutions.