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 | Schools: | School of Physical and Mathematical Sciences | 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 | Size | Format | |
---|---|---|---|---|
1471-2105-12-S9-S17.pdf | 318.09 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
20
8
Updated on Mar 26, 2024
Web of ScienceTM
Citations
20
10
Updated on Oct 25, 2023
Page view(s) 50
490
Updated on Mar 29, 2024
Download(s) 20
225
Updated on Mar 29, 2024
Google ScholarTM
Check
Altmetric
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.