Rearrangement distance with reversals, indels, and moves in intergenic regions on signed and unsigned permutations

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• Genome rearrangement distance is key to understanding evolutionary mutations.
• Existing models vary in allowed events and genome representation.
• Intergenic regions and gene orientation impact distance calculations.

Purpose of the Study:

• To analyze genome rearrangement distance with conservative and non-conservative events.
• To investigate the impact of gene orientation information on distance estimation.
• To develop approximation algorithms for genome rearrangement problems.

Main Methods:

• Developed two models: one with conservative events (reversals, moves) and another with non-conservative events (insertions, deletions).
• Considered genomes with identical gene sets, accounting for intergenic regions.
• Analyzed scenarios with known and unknown gene orientation.

Main Results:

• Both models were proven to be NP-hard, regardless of gene orientation information.
• An approximation algorithm with a factor of 2 was developed for known gene orientation.
• A 4-approximation algorithm was proposed for unknown gene orientation.

Conclusions:

• Genome rearrangement distance problems remain computationally challenging.
• Approximation algorithms provide efficient solutions for estimating genome transformation.
• The developed algorithms offer practical tools for comparative genomics research.