An Improved Genetic Algorithm for Problem of Genome Rearrangement

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.

An improved genetic algorithm for problem of genome rearrangement

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 lengthn,π=)π₁,⃛,π_n), into a setS(π) containing 2 ⁿ signed permutations, so that the reversal distance of π is equal to the reversal distance of the optimal signed permutation inS(π). Then analyze the structural features ofS(π) by crealing 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. Foundation item: Supported by the National Natural Science Foundation of China (30170214) Biography: MO Zhongxi (1953-), male, Associate professor, research direction: bioinformatics.