Sorting genomes by reciprocal translocations, insertions, and deletions.

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Sorting by reciprocal translocations (SBT) is a key problem in comparative genomics.
• Existing SBT algorithms assume identical gene sets between genomes.
• Comparing genomes with different gene content requires new algorithmic approaches.

Purpose of the Study:

• To extend existing SBT algorithms to handle genomes with differing gene sets.
• To develop approximation algorithms for genome comparison involving reciprocal translocations, insertions, and deletions.
• To provide heuristics for finding shortest transformation sequences between genomes with distinct gene compositions.

Main Methods:

• Extension of Bergeron's SBT algorithm.
• Development of an approximation algorithm for subset/superset gene relationships.
• Implementation of a heuristic algorithm for genomes with non-overlapping gene sets.

Main Results:

• An approximation algorithm with a sorting sequence length of at most OPT + 2 for subset/superset gene scenarios.
• A heuristic algorithm providing bounds for the length of the sorting sequence for genomes with distinct gene sets.
• Demonstrated conceptual similarity to El Mabrouk's algorithm for genome sorting by reversals, insertions, and deletions.

Conclusions:

• The extended algorithm effectively compares genomes with different gene sets.
• The developed algorithms offer efficient solutions for genome rearrangement problems.
• This work advances comparative genomics by enabling more flexible genome comparison.