Reversals and transpositions distance with proportion restriction.

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Comparative genomics relies on analyzing genome rearrangement events to understand evolutionary relationships.
• Existing weighted models for genome rearrangements may not accurately reflect biological frequencies.
• A need exists for algorithms that consider the proportion of different rearrangement types.

Purpose of the Study:

• To introduce a novel computational problem focused on finding the shortest sequence of genome rearrangements (reversals and transpositions) with proportional constraints.
• To analyze the computational complexity of this new problem under different gene orientation scenarios (known vs. unknown).
• To develop and evaluate approximation algorithms for this problem.

Main Methods:

• Formulated a new genome rearrangement problem with proportional restrictions on event types.
• Analyzed the computational complexity for both known and unknown gene orientation scenarios.
• Developed constant-factor approximation algorithms for both scenarios.
• Designed an improved asymptotic approximation algorithm for the known gene orientation case.
• Conducted experimental tests comparing new algorithms against existing methods without proportional restrictions.

Main Results:

• Established the complexity of the shortest sequence genome rearrangement problem with proportional event restrictions.
• Developed approximation algorithms with proven constant approximation factors.
• Demonstrated improved performance for the asymptotic approximation algorithm in the known orientation scenario.
• Experimental results showed competitive performance against non-restricted algorithms.

Conclusions:

• The proposed approach offers a more biologically plausible model for genome rearrangement analysis by incorporating event proportions.
• The developed approximation algorithms provide efficient solutions for this complex problem.
• This work advances comparative genomics by offering new tools for genome comparison and evolutionary inference.