A factor-(1.408+epsilon) approximation for sorting unsigned genomes by reciprocal translocations

摘要

Sorting genomes by translocations is a classic combinatorial problem in genome rearrangements. The translocation distance for signed genomes can be computed exactly in polynomial time, but for unsigned genomes the problem becomes NP-hard and the current best approximation ratio is 1.5 + epsilon. In this paper, we investigate the problem of sorting unsigned genomes by translocations. Firstly, we propose a tighter lower bound of the optimal solution by analyzing some special sub-permutations; then, by exploiting the two well-known algorithms for approximating the maximum independent set on graphs with a bounded degree and for set packing with sets of bounded size, we devise a new polynomial-time approximation algorithm, improving the approximation ratio to 1.408 + epsilon, where epsilon = 0 (1/ log n). (C) 2015 Elsevier B.V. All rights reserved.