An Exact Algorithm to Compute the Double-Cut-and-Join Distance for Genomes with Duplicate Genes

Area of Science:

• Computational Biology
• Genomics
• Bioinformatics

Background:

• Calculating genomic edit distance is crucial for understanding genome evolution.
• The double-cut-and-join (DCJ) model is widely used for studying genomic rearrangements.
• Existing methods struggle with genomes containing duplicate genes, a computationally hard problem.

Purpose of the Study:

• To propose an integer linear programming (ILP) formulation for computing DCJ distance in genomes with duplicate genes.
• To develop an efficient preprocessing technique to optimize the ILP formulation.
• To compare the performance of the new method against existing tools like MSOAR.

Main Methods:

• Formulation of an integer linear programming (ILP) model for DCJ distance calculation.
• Development of a preprocessing algorithm to simplify the ILP model.
• Comparative analysis using simulated genomes and real genomic data (human, mouse, rat).

Main Results:

• The proposed ILP method accurately computes DCJ distance for genomes with duplicate genes.
• The method demonstrates superior performance compared to MSOAR, particularly for genomes with long duplicated segments.
• Successful application in assigning orthologous gene pairs across human, mouse, and rat genomes.

Conclusions:

• The ILP approach provides an effective solution for the NP-hard problem of DCJ distance in genomes with duplicates.
• This method advances the field of comparative genomics and evolutionary studies.
• The approach is validated by its performance on both simulated and biologically relevant datasets.