Sorting Unsigned Permutations by Weighted Reversals, Transpositions, and Transreversals
Sorting Unsigned Permutations by Weighted Reversals, Transpositions, and Transreversals
复制标题
DOI：
10.1007/s11390-010-9370-9
复制
发表时间：
2010-07
影响因子：
0.7
通讯作者：
Xiaowen Lou;Daming Zhu
中科院分区：
文献类型：
--
作者：
Xiaowen Lou;Daming Zhu
逆转、转座和反式逆转是基因组重排中的常见事件。基因组重排排序问题是使用最少数量的给定重排操作将一个基因组转换为另一个基因组。在许多情况下，整数排列用于表示基因组。它可以分为不相交的条带，每个条带表示一个连续整数块。单例是一个整数的条带。基因组重排问题转化为将排列等价排序为恒等排列的问题。 Hannenhalli 和 Pevzner 设计了一种多项式时间算法，用于解决 O(logn) 单例排列上的无符号反转排序问题。在本文中，我们首先描述了 Hannenhalli 和 Pevzner 算法可能失败的一种情况，并提出了一种纠正方法。此外，我们提出了一种 (1+ε) 近似算法，用于通过权重 1 的反转和权重 2 的转置/反转对具有 O(logn) 个单例的无符号排列进行排序。
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 withO(logn) 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 withO(logn) singletons by reversals of weight 1 and transpositions/transreversals of weight 2.