标题:A (1.408+epsilon)-Approximation Algorithm for Sorting Unsigned Genomes by Reciprocal Translocations
作者:Jiang, Haitao; Wang, Lusheng; Zhu, Binhai; Zhu, Daming
通讯作者:Jiang, HT
作者机构:[Jiang, Haitao; Zhu, Daming] Shandong Univ, Sch Comp Sci & Technol, Jinan 250100, Peoples R China.; [Wang, Lusheng] City Univ Hong Kong, Dept Comp S 更多
会议名称:8th International Frontiers of Algorithmics Workshop (FAW)
会议日期:JUN 28-30, 2014
来源:FRONTIERS IN ALGORITHMICS, FAW 2014
出版年:2014
卷:8497
页码:128-140
摘要: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+epsilon. 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+epsilon, where epsilon = O(1/log n).
收录类别:CPCI-S
WOS核心被引频次:4
资源类型:会议论文
TOP