标题：SA New Approximation Algorithm for Unsigned Translocation Sorting
作者：Pu, Lianrong; Zhu, Daming; Jiang, Haitao
作者机构：[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
关键词：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.