New algorithms for structure informed genome rearrangement.

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• Genome rearrangements are crucial for understanding evolutionary processes.
• Existing methods for measuring genome divergence have limitations in handling complex structural variations.
• PQ-trees offer a powerful data structure for representing and manipulating genome structures.

Purpose of the Study:

• To define novel computational problems for analyzing genome rearrangements.
• To develop efficient algorithms for calculating structure-informed genome rearrangement distances.
• To implement these algorithms in a software tool for comparative genomics.

Main Methods:

• Definition of two computational problems: one for permutations and a generalized version including insertions/deletions.
• Utilization of PQ-trees to model gene clusters and guide rearrangement operations (Reversal, Block Interchange).
• Development of three algorithms with varying time and space complexities, including one optimized for reduced space.

Main Results:

• The first algorithm solves the basic problem in O(n) time and space.
• The second algorithm addresses the generalized problem with insertions/deletions in O(n*m) time and space.
• A third algorithm achieves reduced space complexity for a specific variant.
• The MEM-Rearrange software tool was developed and applied to analyze 59 chromosomal gene clusters from 1487 prokaryotic genomes.

Conclusions:

• The proposed computational problems and algorithms provide a robust framework for structure-informed genome rearrangement analysis.
• The developed algorithms offer efficient solutions with tunable complexity.
• The MEM-Rearrange tool facilitates comparative and evolutionary analyses of prokaryotic genomes.