标题:Can a Breakpoint Graph be Decomposed into None Other Than 2-Cycles?
作者:Pu, Lianrong; Jiang, Haitao
通讯作者:Jiang, Haitao
作者机构:[Pu, Lianrong; Jiang, Haitao] Shandong Univ, Sch Comp Sci & Technol, Jinan, Peoples R China.
会议名称:10th International Frontiers of Algorithmics Workshop (FAW)
会议日期:JUN 30-JUL 02, 2016
来源:Frontiers in Algorithmics, FAW 2016
出版年:2016
卷:9711
页码:205-214
DOI:10.1007/978-3-319-39817-4_20
关键词:Breakpoint graph; Genome rearrangement; Cycle decomposition
摘要:Breakpoint graph is a key data structure to study genome rearrangements. The problem of Breakpoint Graph Decomposition (BGD), which asks for a largest collection of edge-disjoint cycles in a breakpoint graph, is a crucial step in computing rearrangement distances between genomes. This problem for genomes of unsigned genes is proved NP-hard, and the best known approximation ratio is 1.4193+is an element of [1]. In this paper, we present a polynomial time algorithm to detect whether a breakpoint graph can be decomposed into none other than 2-cycles. Our algorithm can be used to detect if there exists a sorting scenario between two genomes without reusing any breakpoints.
收录类别:CPCI-S;EI;SCOPUS
WOS核心被引频次:1
Scopus被引频次:1
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-84976623944&doi=10.1007%2f978-3-319-39817-4_20&partnerID=40&md5=30e2b47de4484a19406666019f6df4b0
TOP