Sorting Unsigned Permutations by Weighted Reversals, Transpositions, and Transreversals

作者：Lou, Xiao-Wen; Zhu, Da-Ming^*

来源：Journal of Computer Science and Technology, 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+epsilon)-approximation algorithm for sorting unsigned permutations with O(log n) singletons by reversals of weight 1 and transpositions/transreversals of weight 2.

• 出版日期2010-7
• 单位山东大学