In view of the fact that the problem of sorting unsigned permutation by reversal is NP-hard, while the problem of sorting signed permutation by reversal can be solved easily, in this paper, we first transform an unsig...In view of the fact that the problem of sorting unsigned permutation by reversal is NP-hard, while the problem of sorting signed permutation by reversal can be solved easily, in this paper, we first transform an unsigned permutation of length n,π （π1 ,… ,πn）, into a set S（π） containing 2^n signed permutations, so that the reversal distance of π is equal to the reversal distance of the optimal signed permutation in S（π）. Then analyze the structural features of S（π） by creating a directed graph and induce a new computing model of this question. Finally, an improved genetic algorithm for solving the new model is proposed. Experimental results show that the proposed model and algorithm is very efficient in practice.展开更多
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 ...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 rearrange- ment 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（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 with O（log n） singletons by reversals of weight 1 and transpositions/transreversals of weight 2.展开更多
分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在cREW-PRAM模型上,算法使用O(n^2)处理...分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在cREW-PRAM模型上,算法使用O(n^2)处理器,时间复杂度为D(log^2n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system,LARPBS)模型上,算法使用O(n^3)处理器,计算时间复杂度为D(logn).展开更多
基金Supported by the National Natural Science Foun-dation of China (30170214)
文摘In view of the fact that the problem of sorting unsigned permutation by reversal is NP-hard, while the problem of sorting signed permutation by reversal can be solved easily, in this paper, we first transform an unsigned permutation of length n,π （π1 ,… ,πn）, into a set S（π） containing 2^n signed permutations, so that the reversal distance of π is equal to the reversal distance of the optimal signed permutation in S（π）. Then analyze the structural features of S（π） by creating a directed graph and induce a new computing model of this question. Finally, an improved genetic algorithm for solving the new model is proposed. Experimental results show that the proposed model and algorithm is very efficient in practice.
基金Supported by the National Natural Science Foundation of China under Grant No.60970003the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant No.20090131110009the Key Science-Technology Project of Shandong Province of China under Grant No.2006GG2201005
文摘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 rearrange- ment 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（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 with O（log n） singletons by reversals of weight 1 and transpositions/transreversals of weight 2.
文摘分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在cREW-PRAM模型上,算法使用O(n^2)处理器,时间复杂度为D(log^2n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system,LARPBS)模型上,算法使用O(n^3)处理器,计算时间复杂度为D(logn).
