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