Evolution through segmental duplications and losses: a Super-Reconciliation approach

Mattéo Delabre, Nadia El-Mabrouk, Katharina T. Huber, Manuel Lafond, Vincent Moulton, Emmanuel Noutahi, Miguel Sautie CastellanosAlgorithms Mol. Biol 2020 · OpenReview

TL;DR

This paper introduces "Super-Reconciliation," a novel computational framework to infer the evolutionary history of gene families that are organized into syntenic blocks (neighboring genes). It extends traditional gene tree reconciliation by accounting for segmental duplications and losses across multiple gene families simultaneously, offering a more realistic model for concerted gene evolution.

What Problem Does This Paper Address?

Traditional gene tree reconciliation methods treat each gene family in isolation, assuming independent evolutionary paths. This works well for genes located far apart in the genome. However, genes within syntenic blocks (genomic regions with conserved gene order and content) are more likely to evolve together due to events like segmental duplications. Ignoring this concerted evolution can lead to inaccurate evolutionary histories. This paper addresses this gap by developing a method to reconcile multiple gene trees simultaneously, considering segmental duplications and losses that affect entire blocks of genes.

Methods

The core of the paper is the "Super-Reconciliation" problem, which aims to infer a parsimonious evolutionary history for a set of syntenic blocks. The authors propose two main approaches:

  • Exact Exponential-Time Algorithm: For the Duplication-Loss (DL) model without considering rearrangements, they show the problem is NP-hard and provide an exact algorithm to find the most parsimonious solution.
  • Polynomial-Time Algorithm: By relaxing the constraint of gene order consistency and allowing for rearrangements, they develop a polynomial-time algorithm that still minimizes segmental duplications and losses.

They also introduce concepts like "order consistency" for gene orders and "tree consistency" for gene trees, which are necessary conditions for a Super-Reconciliation to exist.

Datasets

The authors used simulated datasets to assess the time efficiency of their algorithms. They also present a proof of concept on real biological data: the opioid receptor genes and related families in human, mouse, chicken, spotted gar, and fruit fly.

Key Insights and Ideas

  • Concerted Evolution of Gene Blocks: The paper highlights that genes within syntenic blocks evolve in a coordinated manner, necessitating a reconciliation approach that considers multiple gene families together.
  • NP-Hardness of Parsimonious Super-Reconciliation: Reconstructing the most parsimonious evolutionary history for syntenic blocks, even without considering rearrangements, is computationally challenging.
  • Rearrangements Simplify the Problem: Surprisingly, by ignoring gene order and allowing for rearrangements, the Super-Reconciliation problem becomes tractable in polynomial time. This suggests that while gene order is important for detailed evolutionary scenarios, it can be a computational bottleneck.
  • Synteny Trees as Building Blocks: The approach leverages the concept of synteny trees, which represent the evolutionary history of gene blocks, and aims to reconcile these with individual gene trees.

Key Results

  • The Super-Reconciliation problem is NP-hard for minimizing duplications and losses when gene order is considered.
  • An exact exponential-time algorithm is provided for the DL model without rearrangements.
  • A polynomial-time algorithm is developed for the DL model that accounts for rearrangements by ignoring gene orders.
  • The algorithm was tested on simulated data, showing exponential time complexity with respect to the number of gene families but polynomial complexity with respect to tree depth.
  • A proof of concept on opioid receptor genes demonstrated the applicability of the method to real biological data, suggesting a history of three duplications and two losses before the divergence of bony fish and tetrapods, with two duplications potentially correlating with ancient whole-genome duplication events.

Limitations and Future Work

  • Tandem Duplications Ignored: The current model primarily focuses on transposed duplications (creating new syntenies) and does not explicitly handle tandem duplications (multiple copies within the same region). Extending the model to include tandem duplications is a significant future direction.
  • Rearrangements Not Fully Integrated: While the "Unordered Super-Reconciliation" accounts for rearrangements by ignoring gene order, it doesn't explicitly infer the rearrangement events themselves. A more complete model that infers both duplications/losses and rearrangements remains an open problem.
  • Multi-Labeled Trees: The presence of multiple gene copies within syntenies can lead to multi-labeled trees, which pose challenges for consistency definitions and supertree construction. Handling these "mul-trees" is an area for future research.
  • Computational Complexity: While the unordered version is polynomial, the ordered version remains NP-hard, limiting its application to very large datasets. Further algorithmic improvements or heuristic approaches might be needed.

Summary updated

Abstract

The 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 not appropriate for genes grouped into syntenic blocks, which are more plausibly the result of a concerted evolution. Here, we introduce the Super-Reconciliation problem which consists in inferring a history of segmental duplication and loss events (involving a set of neighboring genes) leading to a set of present-day syntenies from a single ancestral one. In other words, we extend the traditional Duplication-Loss reconciliation problem of a single gene tree, to a set of trees, accounting for segmental duplications and losses. Existency of a Super-Reconciliation depends on individual gene tree consistency. In addition, ignoring rearrangements implies that existency also depends on gene order consistency. We first show that the problem of reconstructing a most parsimonious Super-Reconciliation, if any, is NP-hard and give an exact exponential-time algorithm to solve it. Alternatively, we show that accounting for rearrangements in the evolutionary model, but still only minimizing segmental duplication and loss events, leads to an exact polynomial-time algorithm. We finally assess time efficiency of the former exponential time algorithm for the Duplication-Loss model on simulated datasets, and give a proof of concept on the opioid receptor genes.
BibTeX
@inproceedings{delabre2020evolution,
  author = {Mattéo Delabre and Nadia El-Mabrouk and Katharina T. Huber and Manuel Lafond and Vincent Moulton and Emmanuel Noutahi and Miguel Sautie Castellanos},
  title = {{Evolution through segmental duplications and losses: a Super-Reconciliation approach}},
  booktitle = {Algorithms Mol. Biol},
  year = {2020},
  url = {https://openreview.net/forum?id=HdimWMNA14},
}

Loading related content...

Figure