标题:Can a breakpoint graph be decomposed into none other than 2-cycles?
作者:Pu, Lianrong; Lin, Yu; Zhu, Daming; Jiang, Haitao
作者机构:[Pu, Lianrong; Zhu, Daming; Jiang, Haitao] Shandong Univ, Sch Comp Sci & Technol, Jinan, Shandong, Peoples R China.; [Lin, Yu] Australian Natl Univ, 更多
通讯作者:Jiang, HT;Jiang, Haitao
通讯作者地址:[Jiang, HT]Shandong Univ, Sch Comp Sci & Technol, Jinan, Shandong, Peoples R China.
来源:THEORETICAL COMPUTER SCIENCE
出版年:2018
卷:734
页码:38-45
DOI:10.1016/j.tcs.2017.09.019
关键词:Algorithm; Complexity; Breakpoint graph; Genome rearrangement; Cycle; decomposition
摘要: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+epsilon. 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. (C) 2017 Elsevier B.V. All rights reserved.
收录类别:EI;SCOPUS;SCIE
资源类型:期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-85030839439&doi=10.1016%2fj.tcs.2017.09.019&partnerID=40&md5=4a4238b00804cc40020529567a2d7c3d
TOP