Multiple Optimal Reconciliations Under the Duplication-Loss-Coalescence Model.

Area of Science:

• Computational Biology
• Phylogenetics
• Bioinformatics

Background:

• Gene trees often differ from species trees due to evolutionary events like gene duplication, horizontal gene transfer, gene loss, and coalescence.
• Reconciliation methods, particularly those using maximum parsimony, are employed to resolve topological incongruence between gene and species trees.
• The space of maximum parsimony reconciliations (MPRs) under the duplication-loss-coalescence (DLC) model is not well understood.

Purpose of the Study:

• To develop algorithms for computing the size of the MPR space under the DLC model.
• To create algorithms for sampling uniformly at random from the MPR space under the DLC model.
• To provide the first insights into the MPR space under the DLC model using a biological data set.

Main Methods:

• Development of novel algorithms for MPR space computation and sampling.
• Analysis of algorithm runtime complexity, demonstrating fixed-parameter tractability.
• Application of the developed methods to a real-world biological data set.

Main Results:

• The developed algorithms are efficient, with runtime polynomial in tree size for a fixed number of genes per species.
• The study provides the first computational insights into the MPR space under the DLC model.
• Plurality reconciliation and its associated evolutionary events appear to be representative of the overall MPR space.

Conclusions:

• The new algorithms efficiently address the challenge of understanding MPR space under the DLC model.
• The findings offer a significant advancement in the field of phylogenetic reconciliation.
• The study highlights the potential of plurality reconciliation as a representative model for evolutionary events.