Fast algorithms and heuristics for phylogenomics under ILS and hybridization

Area of Science:

• Phylogenetics and Evolutionary Biology
• Computational Biology
• Genomics

Background:

• Phylogenomic analyses frequently encounter incongruent gene trees, complicating evolutionary history reconstruction.
• Incongruence arises from factors such as incomplete lineage sorting (ILS) and hybridization.
• Existing methods struggle with the computational complexity of analyzing large-scale phylogenomic data.

Purpose of the Study:

• To develop efficient computational methods for phylogenomic analyses.
• To address the challenges posed by incomplete lineage sorting (ILS) and hybridization in phylogenetic tree reconstruction.
• To enable the analysis of larger and more complex evolutionary datasets.

Main Methods:

• Development of a heuristic algorithm to accelerate the computation of gene tree probabilities under ILS.
• Introduction of two exact algorithms for computing gene tree probabilities and reconciling them with phylogenetic networks, considering both ILS and hybridization.
• Demonstration of scalability and accuracy improvements over existing techniques.

Main Results:

• The heuristic significantly speeds up gene tree probability computations under ILS, enabling analysis of previously infeasible data sizes with high accuracy.
• The exact algorithms substantially accelerate the analysis of gene trees and phylogenetic networks under both ILS and hybridization.
• The developed methods allow for the analysis of significantly larger datasets than currently possible.

Conclusions:

• The new heuristics and algorithms enhance the feasibility of large-scale phylogenomic analyses.
• These methods effectively account for incomplete lineage sorting (ILS) and hybridization.
• The study facilitates a more accurate reconstruction of reticulate evolutionary histories.