用模拟退火算法求解无向排列的反转排序问题

Simulated annealing algorithm for problem ofsorting a unsigned permutation by reversals

分子生物学中基因无方向的反转基因组重排问题在数学上已被证明是一个NP-难问题.目前,较好的算法是Christie(2001)的3/2-近似算法.本文给出一种适合于计算基因无方向的反转基因组重排问题的模拟退火算法,定义了解的邻域结构.数据实验的结果表明该算法性能优于3/2-近似算法.

The problem of genome rearrangement of the unsigned permutation by reversals in molecular biology has been proved to be a NP-hard problem.At present,a better algorithm is the 3/2-approximation one of Christie(2001).The paper proposes a simulated annealing algorithm for the problem of genome rearrangements of the unsigned permutation by reversals,and define the neighborhood structure of its solution.The experimental results show that this algorithm outperforms the 3/2-approximation algorithm.