Back to Search
Start Over
A factor-(1.408 + ε) approximation for sorting unsigned genomes by reciprocal translocations.
- Source :
-
Theoretical Computer Science . Nov2015 Part 2, Vol. 607, p166-180. 15p. - Publication Year :
- 2015
-
Abstract
- 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 + ε . 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 + ε , where ε = O ( 1 / log n ) . [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 607
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 111565445
- Full Text :
- https://doi.org/10.1016/j.tcs.2015.04.036