Motivations: The availability of a large number of assembled genomes opens the way to study the evolution of syntenic character within a phylogenetic context. The DeCo algorithm, recently introduced by erard et al. allows the computation of parsimonious evolutionary scenarios for gene adjacencies, from pairs of reconciled gene trees. However, as for many phylogenetic algorithms, the robustness of a parsimonious scenario to a change in the cost associated to the considered evolutionary events is an important question, as different cost schemes might lead to significant different solutions. This is especially important for genome rearrangement models, that consider rare evolutionary events. Results: Following the approach pioneered by Sturmfels and Pachter, we describe how to modify the DeCo dynamic programming algorithm into a parametric algorithm that allows the identification of classes of cost schemes that generates similar parsimonious evolutionary scenarios for gene adjacencies. Moreover, we extend this approach to assess the robustness (again to changes to the cost scheme of evolutionary events) of specific elements of evolutionary scenarios, here the presence/absence of specific ancestral gene adjacencies. We apply our method to a dataset of more than six thousands mammalian gene families, and show that computing the robustness to changes to cost schemes provides new and interesting insights on the evolution of gene adjacencies and the DeCo model.