无向反转排序问题的遗传模拟退火求解

Estimation of genome reversal distance with genetic simulated annealing algorithm

在推断两个基因组的进化关系上反转排序是一个重要问题。无向排列排序问题已被证明是一个NP-困难问题,目前,最好的算法是3/2-近似算法。基于一个无向排列π的反转距离等于由π所生成的包含2n个有向排列集Sign(π)中最优排列的反转距离,给出应用遗传模拟退火算法计算基因组重排的反转距离的方法。实验结果显示,这个方法优于3/2-近似算法。

Sorting by reversals is an important problem in inferring the evolutionary relationship between two genomes. The unsigned permutation has been proved to be NP-hard. The best guaranteed error bounded is the 3/2-approximation algorithm. The paper propose a genetic simulated annealing algorithm for the problem of genome rearrangements of the unsigned permutation by reversals. It is based on the reversal distance of sorting unsigned permutation by reversal distance of sorting optimal permutaion in sign（π）. Sign （π） was generated from π with size 2^π. The experimental result shows that genetic simulated annealing algorithm outperforms the 3/2-approximation algorithm.