Closing the Complexity Gap of the Double Distance Problem

Area of Science:

• Computational comparative genomics
• Bioinformatics
• Algorithmic complexity

Background:

• Genome rearrangement analysis is crucial for understanding genome evolution, with practical applications increasing due to abundant sequenced genomes.
• The computational complexity of genome rearrangement problems varies significantly based on the model used, such as reversal distance for signed vs. unsigned permutations.
• The double distance, measuring rearrangements in duplicated genomes, presents a complex computational landscape with varying hardness depending on the distance metric (e.g., breakpoint vs. DCJ distance).

Purpose of the Study:

• To fully characterize the computational hardness landscape for computing the double distance across a family of rearrangement metrics.
• To resolve the complexity of the double distance for intermediate values of k, bridging the gap between known linear and NP-hard cases.

Main Methods:

• Analysis of computational complexity for the double distance problem.
• Investigating a family of distance measures parameterized by an even number k, ranging from breakpoint distance (k=2) to DCJ distance (k=∞).
• Determining the precise complexity for k=4 and k=6, and extending this to provide a complete hardness picture.

Main Results:

• The study provides a comprehensive understanding of the hardness landscape for computing the double distance.
• Previously unknown complexities for intermediate values of k (beyond k=2, 4, 6, and ∞) were elucidated.
• The research establishes a clear boundary between computationally tractable and intractable scenarios for double distance calculations.

Conclusions:

• The computational complexity of the double distance is now fully understood across a spectrum of rearrangement metrics.
• This work resolves ambiguities and provides a complete picture of the hardness landscape, aiding future research in comparative genomics and phylogenetic analysis.
• The findings are essential for developing efficient algorithms for analyzing genome duplications and rearrangements.