Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875457 | Theoretical Computer Science | 2018 | 8 Pages |
Abstract
Breakpoint graph has been widely used as a key data structure in algorithm design for genome rearrangements. The problem of breakpoint graph cycle decomposition, which asks for a largest collection of edge-disjoint cycles, is crucial in computing rearrangement distances between genomes. This problem is NP-hard, and can be approximated to 1.4193+ϵ. It is still open for deciding whether a breakpoint graph can admit a cycle decomposition with none other than 2-cycles. In this paper, we present a linear time algorithm to detect whether a breakpoint graph can be decomposed into none other than 2-cycles.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Lianrong Pu, Yu Lin, Daming Zhu, Haitao Jiang,