An improved approximation algorithm for the reversal and transposition distance considering gene order and intergenic...

Area of Science:

• Comparative genomics
• Bioinformatics
• Computational biology

Background:

• Genome rearrangement events, such as reversals and transpositions, are key to understanding evolutionary relationships between species.
• Previous models focused on gene order, but recent work incorporates intergenic region sizes for more accurate genomic comparisons.
• The SORTING BY INTERGENIC REVERSALS AND TRANSPOSITIONS problem is central to reconstructing genome evolution.

Purpose of the Study:

• To investigate genome sorting using reversals and transpositions, considering both known and unknown gene orientations.
• To explore a generalized transposition event for a more comprehensive analysis of genome rearrangements.
• To develop and evaluate approximation algorithms for these genome sorting problems.

Main Methods:

• Developed approximation algorithms for sorting by intergenic reversals and transpositions.
• Introduced a generalized transposition event to refine the analysis of genome rearrangements.
• Implemented a greedy strategy to enhance algorithm performance.

Main Results:

• Achieved a 4-approximation factor for sorting by reversals and classic transpositions, improving upon previous 4.5-approximation for unknown gene orientations.
• Developed a 3-approximation algorithm incorporating generalized transpositions.
• Simulated data showed improved performance compared to existing algorithms.

Conclusions:

• The new algorithms provide better approximation factors for genome rearrangement problems.
• Practical tests and real genome experiments demonstrate the algorithms' effectiveness and applicability.
• This research advances the field of comparative genomics by offering more precise tools for analyzing genome evolution.