Heuristics for the Reversal and Transposition Distance Problem.

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• Genome rearrangement problems, such as sorting signed permutations by reversals and transpositions, are fundamental in comparative genomics.
• Developing efficient algorithms is crucial for understanding evolutionary relationships between species.

Purpose of the Study:

• To introduce and evaluate three novel heuristics: Sliding Window, Look Ahead, and Iterative Sliding Window.
• To improve the quality and efficiency of solutions for the Sorting Signed Permutations by Reversals and Transpositions Problem.

Main Methods:

• Implementation of existing algorithms to generate baseline solutions.
• Application and assessment of the proposed Sliding Window, Look Ahead, and Iterative Sliding Window heuristics.
• Investigation of classical and restricted versions (prefix, prefix/suffix operations) of the problem.

Main Results:

• Sliding Window heuristic offers linear time complexity, making it ideal when speed is critical.
• Look Ahead heuristic prioritizes solution quality, providing more accurate results.
• Iterative Sliding Window heuristic provides flexibility, balancing running time and solution quality.

Conclusions:

• The proposed heuristics effectively improve solutions for genome rearrangement problems.
• The choice of heuristic depends on specific application requirements regarding time constraints and desired solution accuracy.
• These heuristics have broad applicability to various genome rearrangement scenarios.