Sorting Unsigned Permutations by Weighted Reversals,Transpositions, and Transreversals |
| |
Authors: | Xiao-Wen Lou Da-Ming Zhu |
| |
Affiliation: | (1) Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, 80424, Taiwan;(2) Department of Computer Science and Information Engineering, Chang Gung University, Taoyuan, 33302, Taiwan |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 万方数据 SpringerLink 等数据库收录! |
|