Exploring the space of gene/species reconciliations with transfers

UMR AGAP - équipe GE²pop - Génomique évolutive et gestion des populationsReconciliations between gene and species trees have important applicationsin the study of genome evolution (e.g. sequence orthology prediction or quantificationof transfer events). While numerous methods have been proposed to infer them, littlehas been done to study the underlying reconciliation space. In this paper, we characterisethe reconciliation space for two evolutionary models: the DTL (duplication,loss and transfer) model and a variant of it—the no-TL model—which does not allowTL events (a transfer immediately followed by a loss). We provide formulae to computethe size of the corresponding spaces and define a set of transformation operatorssufficient to explore the entire reconciliation space.We also define a distance betweentwo reconciliations as the minimal number of operations needed to transform oneinto the other and prove that this distance is easily computable in the no-TL model.Computing this distance in the DTL model is more difficult and it is an open questionwhether it is NP-hard or not. This work constitutes an important step toward reconciliationspace characterisation and reconciliation comparison, needed to better assessthe performance of reconciliation inference methods through simulations