Reconstructing the History of Syntenies Through Super-Reconciliation

Matteo Delabre, Nadia El-Mabrouk, Katharina Huber, Manuel Lafond, Vincent Moulton, Emmanuel Noutahi, Miguel Sautie Castellanos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)
8 Downloads (Pure)

Abstract

Classical gene and species tree reconciliation, used to infer the history of gene gain and loss explaining the evolution of gene families, assumes an independent evolution for each family. While this assumption is reasonable for genes that are far apart in the genome, it is clearly not suited for genes grouped in syntenic blocks, which are more plausibly the result of a concerted evolution. Here, we introduce the Super-Reconciliation model, that extends the traditional Duplication-Loss model to the reconciliation of a set of trees, accounting for segmental duplications and losses. From a complexity point of view, we show that the associated decision problem is NP-hard. We then give an exact exponential-time algorithm for this problem, assess its time efficiency on simulated datasets, and give a proof of concept on the opioid receptor genes.
Original languageEnglish
Title of host publicationComparative Genomics
Subtitle of host publication16th International Conference, RECOMB-CG 2018, Magog-Orford, QC, Canada, October 9-12, 2018, Proceedings
EditorsMathieu Blanchette, Aïda Ouangraoua
PublisherSpringer
Pages179-195
Volume11183
ISBN (Electronic)978-3-030-00834-5
ISBN (Print)978-3-030-00833-8
DOIs
Publication statusPublished - 8 Sep 2018

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume11183

Keywords

  • Gene tree
  • Reconciliation
  • Duplication
  • Loss
  • Synteny

Cite this