摘要： 分子生物学中基因无方向的反转基因组重排问题在数学上已被证明是一个N P2难问题。 目前, 较好的算法是Christie （2001） 的3ö22近似算法。本文给出一种适合于计算基因无方向的反转基因组重排问题的模拟退火算法, 定义了解的邻域结构。数据实验的结果表明该算法性能优于3ö22近似算法。 关键词： 基因组重排、反转排序、模拟退火算法。

(1. 鞍山科技大学 理学院, 辽宁 鞍山 114044; 2. 武汉大学 数学与统计学院, 湖北 武汉 430072) 摘 要: 分子生物学中基因无方向的反转基因组重排问题在数学上已被证明是一个 N P2难问题. 目前, 较好 的算法是 Ch ristie (2001) 的 3ö22近似算法. 本文给出一种适合于计算基因无方向的反转基因组重排问题的模 拟退火算法, 定义了解的邻域结构. 数据实验的结果表明该算法性能优于 3ö22近似算法