Approximating the DCJ distance of balanced genomes in linear time

Area of Science:

• Genomics
• Computational Biology
• Bioinformatics

Background:

• Genomic rearrangements are large-scale mutations causing structural variations.
• The double (DCJ) cut and join operation models most genome organization changes.
• Calculating the minimum DCJ operations (rearrangement distance) between genomes is NP-hard.

Purpose of the Study:

• To develop an efficient approximation algorithm for the DCJ distance problem.
• To address the computational complexity of determining genomic rearrangement distances.

Main Methods:

• Proposed a linear time approximation algorithm for DCJ distance.
• The algorithm achieves an O(k) approximation factor, where k is the maximum gene copy number.
• Utilized an O(k)-approximation for the minimum common string partition problem as an intermediate step.

Main Results:

• Developed a linear time approximation algorithm for DCJ distance.
• The algorithm provides an O(k) approximation factor.
• Demonstrated competitive efficiency and solution quality on simulated datasets.

Conclusions:

• The proposed algorithm offers an efficient and effective method for approximating DCJ distance.
• Experimental results validate the algorithm's performance on simulated genomic data.
• This approach advances the study of genomic rearrangements and structural variations.