Sorting Signed Permutations by Intergenic Reversals.

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• Genome rearrangements, like reversals, are key to understanding genome evolution.
• The Sorting by Reversals (SbR) problem is well-studied for signed permutations but NP-hard for unsigned ones.
• Existing models often ignore intergenic region sizes, potentially limiting accuracy in genome distance estimation.

Purpose of the Study:

• To introduce and analyze the Sorting Signed Permutations by Intergenic Reversals problem.
• To incorporate intergenic region sizes and indels into genome rearrangement models.
• To develop approximation algorithms for these new problems.

Main Methods:

• Introduced the Sorting Signed Permutations by Intergenic Reversals problem.
• Proved NP-hardness using a reduction from the 3-partition problem.
• Developed a 2-approximation algorithm for the intergenic reversals problem.
• Proposed two approximation algorithms incorporating intergenic indels.

Main Results:

• The Sorting Signed Permutations by Intergenic Reversals problem is NP-hard.
• A 2-approximation algorithm was developed for sorting by intergenic reversals.
• New approximation algorithms were proposed to handle intergenic indels.
• The incorporation of intergenic regions offers potentially better genome distance estimators.

Conclusions:

• Considering intergenic region sizes and indels provides a more comprehensive model for genome rearrangements.
• The developed algorithms offer practical approaches for estimating genomic distances with these new features.
• This work advances the computational understanding of genome evolution by including previously overlooked genomic elements.