On sorting unsigned permutations by double-cut-and-joins

摘要

The problem of sorting unsigned permutations by double-cut-and-joins (SBD) arises when we perform the double-cut-and-join (DCJ) operations on pairs of unichromosomal genomes without the gene strandedness information. In this paper we show it is a NP-hard problem by reduction to an equivalent previously-known problem, called breakpoint graph decomposition (BGD), which calls for a largest collection of edge-disjoint alternating cycles in a breakpoint graph. To obtain a better approximation algorithm for the SBD problem, we made a suitable modification to Lin and Jiang's algorithm which was initially proposed to approximate the BGD problem, and then carried out a rigorous performance analysis via fractional linear programming. The approximation ratio thus achieved for the SBD problem is 17/12 + ∈ ≈ 1.4167+∈, for any positive ∈.