title: Approximating the double-cut-and-join distance between unsigned genomes.
abstract: In this paper we study the problem of sorting unsigned genomes by double-cut-and-join operations, where genomes allow a mix of linear and circular chromosomes to be present. First, we formulate an equivalent optimization problem, called maximum cycle/path decomposition, which is aimed at finding a largest collection of edge-disjoint cycles/AA-paths/AB-paths in a breakpoint graph. Then, we show that the problem of finding a largest collection of edge-disjoint cycles/AA-paths/AB-paths of length no more than l can be reduced to the well-known degree-bounded k-set packing problem with k = 2l. Finally, a polynomial-time approximation algorithm for the problem of sorting unsigned genomes by double-cut-and-join operations is devised, which achieves the approximation ratio 13/9 + ε ≈ 1.4444 + ε, for any positive ε. For the restricted variation where each genome contains only one linear chromosome, the approximation ratio can be further improved to 69/49 + ε ≈ 1.4082 + ε.
authors.affiliation: Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore. chenxin@ntu.edu.sg
authors.forename: Xin
authors.initials: X
authors.lastname: Chen
authors.forename: Ruimin
authors.initials: R
authors.lastname: Sun
authors.forename: Jiadong
authors.initials: J
authors.lastname: Yu
mesh_terms: D000465:Algorithms; D002875:Chromosomes; D016678:Genome; D023281:Genomics / Q000379:methods*; D008957:Models, Genetic