ffdcj-sim

ffdcj-sim computes family-free Double-Cut-and-Join (DCJ) similarity between genomes, addressing the NP-hard problem of comparing genomes without predefined gene families.

Key Features:

• Exact ILP algorithm: Employs an exact Integer Linear Programming (ILP) algorithm to compute family-free DCJ similarity.
• APX-hardness demonstration: Reports the APX-hard nature of the family-free DCJ similarity problem.
• Combinatorial heuristics: Implements four combinatorial heuristics to approximate solutions for larger genomes where exact computation is computationally intensive.
• Computational experiments and comparisons: Provides computational experiments that compare the performance of the ILP algorithm against the proposed heuristics.

Scientific Applications:

• Large-scale genomic comparisons: Enables comparison of whole genomes when gene families are not predefined.
• Evolutionary biology and rearrangement analysis: Supports analysis of genome rearrangements and similarity without relying on gene family groupings.

Methodology:

Uses an exact ILP formulation to solve the family-free DCJ similarity problem, provides four combinatorial heuristics for larger instances, and evaluates methods via computational experiments; the problem is NP-hard and APX-hard.