| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 437185 | Theoretical Computer Science | 2006 | 7 Pages |
Abstract
Translocation is one of the basic operations for genome rearrangement. Translocation distance is the minimum number of translocations required to transform one genome into the other. In this paper, we show that computing the translocation distance for unsigned genomes is NP-hard. Moreover, we show that approximating the translocation distance for unsigned genomes within ratio 1.00017 is NP-hard.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
