FullSynesth: Syntenic Reconciliation of a Set of Consistent Gene Trees

We present FullSynesth, a tree reconciliation algorithm predicting the evolution of a set of homologous genomic regions or syntenies, inside a species tree. The considered evolutionary model involves segmental events (i.e. acting on multiple genes) including duplications (D), losses (L), synteny fissions and transfers possibly going through unsampled or extinct species. Formally, given a set of syntenies in a set of genomes and a set G of consistent gene trees for the gene families composing the syntenies, the problem is to infer a most parsimonious evolutionary history explaining the observed gene trees and syntenies given a species tree. The problem is known to be NP-hard for the DL distance. FullSynesth is based on Synesth explicating the evolution of a set of syntenies given a single synteny tree, which can be obtained from G by selecting a given supertree. Rather than trying each supertree in turn, FullSynesth is based on a two-in-one approach simultaneously building and reconciling a synteny supertree. This algorithm runs in polynomial time for a fixed number of gene trees. We show on simulated datasets that FullSynesth significantly improves the running time of Synesth applied to each possible supertree. An implementation of the algorithm is available at: https://github.com/UdeM-LBIT/FullSynesth.