Approximating the double-cut-and-join distance between unsigned genomes.

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• Genome rearrangement studies the evolutionary changes in genome structure.
• Double-cut-and-join operations are a key mechanism for modeling these changes.
• Sorting unsigned genomes with mixed linear and circular chromosomes presents computational challenges.

Purpose of the Study:

• To develop an efficient algorithm for sorting unsigned genomes using double-cut-and-join operations.
• To establish approximation ratios for genome sorting problems.
• To reduce the genome sorting problem to a known combinatorial optimization problem.

Main Methods:

• Formulation of the maximum cycle/path decomposition problem.
• Reduction to the degree-bounded k-set packing problem (k=2l).
• Development of a polynomial-time approximation algorithm.

Main Results:

• An approximation ratio of 13/9 + ε (≈1.4444 + ε) for general unsigned genomes.
• An improved approximation ratio of 69/49 + ε (≈1.4082 + ε) for genomes with a single linear chromosome.
• Demonstration of the problem's equivalence to maximum cycle/path decomposition in breakpoint graphs.

Conclusions:

• The proposed algorithm provides a significant advancement in efficiently sorting unsigned genomes.
• The reduction to k-set packing offers a novel approach to tackling genome rearrangement problems.
• The findings contribute to a better understanding of genome evolution and comparative genomics.