标题:Sorting Unsigned Permutations by Weighted Reversals, Transpositions, and Transreversals
作者:Lou, Xiao-Wen; Zhu, Da-Ming
作者机构:[Lou, X.-W] School of Computer Science and Technology, Shandong University, Jinan 250101, China;[ Zhu, D.-M] School of Computer Science and Technology 更多
通讯作者:Zhu, DM
通讯作者地址:[Zhu, DM]Shandong Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China.
来源:计算机科学技术学报(英文版)
出版年:2010
卷:25
期:4
页码:853-863
DOI:10.1007/s11390-010-9370-9
关键词:approximation algorithm;genome rearrangement;sorting;reversal;transposition
摘要:Reversals,transpositions and transreversals are common events in genome rearrangement.The genome rearrangement sorting problem is to transform one genome into another using the minimum number of given rearrangement operations.An integer permutation is used to represent a genome in many cases.It can be divided into disjoint strips with each strip denoting a block of consecutive integers.A singleton is a strip of one integer.And the genome rearrangement problem turns into the problem of sorting a permutation into the identity permutation equivalently.Hannenhalli and Pevzner designed a polynomial time algorithm for the unsigned reversal sorting problem on those permutations with O(log n)singletons.In this paper,first we describe one case in which Hannenhalli and Pevzner\'s algorithm may fail and propose a corrected approach.In addition,we propose a(1+ε)-approximation algorithm for sorting unsigned permutations with O(log n)singletons by reversals of weight 1 and transpositions/transreversals of weight 2.
收录类别:EI;SCOPUS;SCIE
WOS核心被引频次:1
Scopus被引频次:1
资源类型:期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-78650293292&doi=10.1007%2fs11390-010-9370-9&partnerID=40&md5=6a8f41a12e372ce200cacfa314de6950
TOP