Flanked Transposition Distance for Two Strings

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• Transposition is a key genome rearrangement mechanism.
• Genome rearrangements are often linked to repeated DNA sequences.
• Flanked transpositions involve three identical repeated sub-strings.

Purpose of the Study:

• To investigate transforming one string into another using flanked transpositions.
• To establish conditions for string transformation via flanked transpositions.
• To analyze the computational complexity of flanked transposition problems.

Main Methods:

• Developed a necessary and sufficient condition for flanked transposition.
• Designed an O(n) decision algorithm to test the condition.
• Proved the NP-hardness of the minimum flanked transposition problem.
• Proposed an O(n^2) approximation algorithm for simple strings.

Main Results:

• A condition for string transformation using flanked transpositions was identified.
• An efficient O(n) algorithm can determine if transformation is possible.
• The problem of finding the minimum number of flanked transpositions is NP-hard.
• A 2-approximation algorithm was developed for simple strings.

Conclusions:

• Flanked transpositions offer a specific model for genome rearrangement analysis.
• Efficient algorithms exist for decision problems, but optimization remains challenging.
• The study provides theoretical foundations for understanding complex genome rearrangements.