Algorithms for computing the double cut and join distance on both gene order and intergenic sizes.

Area of Science:

• Genomics
• Computational Biology
• Bioinformatics

Background:

• Genome rearrangement studies traditionally overlooked intergene sizes.
• Intergene sizes significantly impact the accuracy of genome inference methods.
• A new model, wDCJ, is introduced to incorporate intergene size distribution.

Purpose of the Study:

• To define a generalized genome rearrangement model (wDCJ) that includes intergene sizes.
• To develop computational methods for calculating genome distances under the wDCJ model.
• To assess the practical efficiency of proposed algorithms.

Main Methods:

• Definition of the wDCJ (whole-genome Double Cut and Join) model.
• Derivation of a generic formula for wDCJ distance.
• Development of an approximation algorithm (ratio 4/3), a fixed-parameter tractable (FPT) algorithm, and an integer linear programming (ILP) formulation.

Main Results:

• The wDCJ distance computation is proven to be strongly NP-complete.
• An approximation algorithm with a 4/3 ratio is proposed.
• Exact algorithms including FPT and ILP formulations are presented.

Conclusions:

• Theoretical and empirical bounds suggest FPT and ILP algorithms are efficient in practice.
• The wDCJ model provides a more comprehensive approach to genome rearrangement analysis.
• The study advances computational methods for understanding genome evolution.