Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/100350
Title: Approximating the double-cut-and-join distance between unsigned genomes
Authors: Chen, Xin
Sun, Ruimin
Yu, Jiadong
Keywords: Mathematical Sciences
Issue Date: 2011
Source: Chen, X., Sun, R., & Yu, J. (2011). Approximating the double-cut-and-join distance between unsigned genomes. BMC Bioinformatics, 12(Suppl 9):S17.
Series/Report no.: BMC bioinformatics
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 + e ≈ 1.4444 + e, 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 + e ≈ 1.4082 + e.
URI: https://hdl.handle.net/10356/100350
http://hdl.handle.net/10220/17879
ISSN: 1471-2105
DOI: 10.1186/1471-2105-12-S9-S17
Rights: © 2011 Chen et al; licensee BioMed Central Ltd. This is an open access article distributed under the terms of the Creative Commons Attribution License(http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
1471-2105-12-S9-S17.pdf318.09 kBAdobe PDFThumbnail
View/Open

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.