An exact solver for the DCJ median problem.

Area of Science:

• Computational Biology
• Genomics
• Bioinformatics

Background:

• The double-cut-and-join (DCJ) model is a fundamental framework for understanding genome rearrangements.
• The DCJ median problem seeks a reference genome that minimizes rearrangements to a set of genomes.
• Existing methods face challenges with multichromosomal genomes and complex rearrangement scenarios.

Purpose of the Study:

• To develop an accurate and efficient method for solving the multichromosomal double-cut-and-join (DCJ) median problem.
• To evaluate the performance of the proposed method against existing DCJ median solvers.
• To assess the suitability of the DCJ model for real biological datasets exhibiting various genomic events.

Main Methods:

• Implementation of a branch-and-bound algorithm tailored for multichromosomal DCJ median computations.
• Extensive simulations to test the accuracy and efficiency of the developed DCJ median solver.
• Comparative analysis against other established median solvers using simulated and real genomic datasets.

Main Results:

• The proposed branch-and-bound method provides accurate solutions for multichromosomal DCJ median problems.
• The DCJ median solver demonstrates superior performance compared to other solvers in most tested scenarios.
• Simulations indicate the DCJ model's effectiveness for datasets with both reversals and transpositions.

Conclusions:

• The developed branch-and-bound approach offers a robust solution for the multichromosomal DCJ median problem.
• The DCJ model and its associated median solver are well-suited for analyzing complex genomic rearrangement data.
• This work advances computational approaches for comparative genomics and evolutionary studies.