标题:SA New Approximation Algorithm for Unsigned Translocation Sorting
作者:Pu, Lianrong; Zhu, Daming; Jiang, Haitao
通讯作者:Zhu, DM
作者机构:[Pu, Lianrong; Zhu, Daming; Jiang, Haitao] Shandong Univ, Sch Comp Sci & Technol, Jinan, Peoples R China.
会议名称:16th International Workshop on Algorithms in Bioinformatics (WABI)
会议日期:AUG 22-24, 2016
来源:ALGORITHMS IN BIOINFORMATICS
出版年:2016
卷:9838
页码:269-280
DOI:10.1007/978-3-319-43681-4_22
关键词:Algorithm; Complexity; Approximation; Genome; Rearrangement;; Translocation
摘要:Translocation has long been learned as a basic operation to rearrange genomes. Signed translocation sorting can be solved in polynomial time. Unsigned translocation sorting turns to be NP-Hard and Max-SNP-Hard. The best known algorithm by now for unsigned translocation sorting can achieve a performance ratio 1.408. In this paper, we propose a new approximation algorithm for unsigned translocation sorting, which can achieve a performance ratio 1.375 in polynomial time.
收录类别:CPCI-S
资源类型:会议论文
TOP