Comparing genomes with rearrangements and segmental duplications

Area of Science:

• Genomics
• Computational Biology
• Evolutionary Biology

Background:

• Genomic rearrangements and segmental duplications are key to genome evolution.
• Inferring these evolutionary events is a fundamental computational challenge.
• Existing algorithms struggle with combined rearrangements and duplication/loss events.

Purpose of the Study:

• To develop an exact algorithm for comparing two genomes considering general rearrangements and segmental duplications.
• To formulate genome comparison as an optimization problem solvable by integer linear programming.
• To improve the accuracy and applicability of inferring large-scale evolutionary events.

Main Methods:

• Formulated genome comparison as an integer linear programming (ILP) optimization problem.
• Developed an exact algorithm using ILP for general rearrangements and segmental duplications.
• Identified optimal substructures to simplify the problem while maintaining optimality.
• Applied the algorithm for in-paralog and ortholog assignment.

Main Results:

• The proposed ILP-based algorithm provides a practical and exact solution for genome comparison.
• The method significantly outperforms the state-of-the-art MSOAR on simulated datasets.
• On real data, the new algorithm shows slightly better performance than MSOAR in pairwise comparisons.

Conclusions:

• The developed algorithm offers a robust and accurate approach for analyzing genome evolution.
• This method enhances the ability to study large-scale evolutionary events, including rearrangements and duplications.
• The tool provides a valuable advancement for comparative genomics and evolutionary studies.