标题:A Randomized FPT Approximation Algorithm for Maximum Alternating-Cycle Decomposition with Applications
作者:Jiang, Haitao; Pu, Lianrong; Qingge, Letu; Sankoff, David; Zhu, Binhai
通讯作者:Zhu, Binhai;Zhu, BH
作者机构:[Jiang, Haitao; Pu, Lianrong] Shandong Univ, Sch Comp Sci & Technol, Jinan, Shandong, Peoples R China.; [Qingge, Letu; Zhu, Binhai] Montana State Un 更多
会议名称:24th International Computing and Combinatorics Conference (COCOON)
会议日期:JUL 02-04, 2018
来源:COMPUTING AND COMBINATORICS (COCOON 2018)
出版年:2018
卷:10976
页码:26-38
DOI:10.1007/978-3-319-94776-1_3
摘要:Comparing genomes in terms of gene order is a classical combinatorial optimization problem in computational biology. Some of the popular distances include translocation, reversal, and double-cut-and-join (abbreviated as DCJ), which have been extensively used while comparing two genomes. Let d(x), x is an element of {translocation, reversal, DCJ}, be the distance between two genomes such that one can be sorted/converted into the other using the minimum number of x-operations. All these problems are NP-hard when the genomes are unsigned. Computing d(x), x is an element of {translocation, reversal, DCJ}, between two unsigned genomes involves computing a proper alternating cycle decomposition of its breakpoint graph, which becomes the bottleneck for computing the genomic distance under almost all types of genome rearrangement operations and prohibits to obtain approximation factors better than 1.375 in polynomial time. In this paper, we devise an FPT (fixed-parameter tractable) approximation algorithm for computing the DCJ and translocation distances with an approximation factor 4/3+epsilon, and the running time is O*(2d*), where d* represents the optimal DCJ or translocation distance. The algorithm is randomized and it succeeds with a high probability. This technique is based on a new randomized method to generate approximate maximum alternating cycle decomposition.
收录类别:CPCI-S;EI;SCOPUS
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-85049685251&doi=10.1007%2f978-3-319-94776-1_3&partnerID=40&md5=e66c81e2eaa44328c4b1d06edaf96725
TOP