Super short operations on both gene order and intergenic sizes.

Area of Science:

• Computational Biology
• Genomics
• Bioinformatics

Background:

• Genome rearrangements are used to estimate evolutionary distance by modeling genomes as ordered gene sequences.
• Previous studies often overlooked intergenic regions, focusing solely on gene order.
• Mathematical models of genome rearrangements have explored various constraints and costs.

Purpose of the Study:

• To develop methods for computing genome distance that incorporate both gene order and intergenic region sizes.
• To investigate constrained genome rearrangement operations, specifically super short reversals (SSRs) and super short transpositions (SSTs).

Main Methods:

• Introduced super short operations (SSOs), including SSRs and SSTs, affecting up to two genes.
• Developed approximation algorithms for genome distance calculation using these SSOs.
• Analyzed algorithm performance with and without considering gene orientation.

Main Results:

• Achieved 3-approximation algorithms for genome distance when gene orientation is ignored.
• Achieved 5-approximation algorithms when gene orientation is considered.
• Demonstrated improved approximation factors (e.g., 2, 1.5, 3, 2) when the input permutation has more inversions.

Conclusions:

• The developed algorithms provide more accurate genome distance estimations by including intergenic region information.
• The efficiency of the algorithms improves with increased genomic inversions.
• This work advances computational methods for comparative genomics.