Can the 1.375 Approximation Ratio of Unsigned Genomes Distances be Improved?

Computing the genome rearrangement distances between two genomes has been classical combinatorial optimization problems since the 1990s, where reversals, translocations and double cut and joins (dcjs for short) are the most popular genome rearrangement operations. All the three distances can be computed in polynomial time for signed genomes but are NP-hard when the genomes are unsigned. Over the past three decades, people devoted to approximation algorithms for the three problems. So far as we know, the best approximation ratio is 1.375 for both reversal and translocation, and 1.408 for dcj. In this paper, we first design a proper approximation algorithm for the maximum independent set problem on graphs with a maximum degree of 3, by use of which, we devise an approximation algorithm for the unsigned dcj problem, improving the approximation ratio to 4173⁄3035 (≈1.37496) + ε, and running in O(n^{3 + (4log4+5log5)}⁄_ε), where n represents the length of the genomes and ε is an arbitrary small constant. Joined with the pre-processing method for the unsigned reversal problem and unsigned translocation problem respectively in [5, 16], our algorithm can also be extended to solve the unsigned reversal problem and the unsigned translocation problem, also guaranteeing the same approximation ratio of 4173⁄3035, beating the long-lasting best ratio of 1.375 since 2002. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.