Reconstructing ancestral genomic sequences by co-evolution: formal definitions, computational issues, and biological...

Area of Science:

• Computational Biology
• Molecular Evolution
• Bioinformatics

Background:

• Ancestral genome inference is crucial in molecular evolution but often suffers from high error rates.
• Existing computational methods and data augmentation do not sufficiently reduce these errors.

Purpose of the Study:

• To formally define and address the computational problem of ancestral genome content inference using co-evolution.
• To develop and evaluate algorithms for improving ancestral genome reconstruction accuracy.

Main Methods:

• Defined a computational problem for ancestral genome inference incorporating co-evolutionary data.
• Developed a Fixed Parameter Tractable (FPT) algorithm and heuristic approximation algorithms.
• Applied the approach to reconstruct ancestral fungal genomes using a large dataset of protein families and co-evolutionary relations.

Main Results:

• The co-evolutionary approach significantly improved ancestral genome content inference, adding/removing hundreds of proteins compared to Maximum Likelihood (ML) and Maximum Parsimony (MP) methods.
• Algorithms demonstrated fast running times (under four minutes) with a high approximation ratio (<1.3) on simulated data.
• Biological analysis supported the plausibility of the reconstructed ancestral genomes.
• The method showed superior reconstruction of missing data in the Fungi evolutionary tree compared to ML and MP.

Conclusions:

• Co-evolution is a powerful factor for enhancing ancestral genome inference accuracy.
• The developed algorithms are efficient and effective for reconstructing ancestral genomic content.
• This approach offers a more biologically plausible and accurate reconstruction of evolutionary history.