| 用模拟退火算法求解无向排列的反转排序问题 |
| |
| 引用本文： | 陶玉敏,曾涛,莫舒园,石艳霞.用模拟退火算法求解无向排列的反转排序问题[J].鞍山科技大学学报,2004,27(3):166-170. |
| |
| 作者姓名： | 陶玉敏 曾涛 莫舒园 石艳霞 |
| |
| 作者单位： | [1]鞍山科技大学理学院，辽宁鞍山114044 [2]武汉大学数学与统计学院，湖北武汉430072 |
| |
| 摘 要： | 分子生物学中基因元方向的反转基因组重排问题在数学上已被证明是一个NP-难问题。目前，较好的算法是Christie(2001)的3／2-近似算法，本文给出一种适合于计算基因元方向的反转基因组重排问题的模拟退火算法，定义了解的邻域结构，数据实验的结果表明该算法性能优于3／2-近似算法。
|
| 关 键 词： | 基因组重排 反转排序 模拟退火算法 |
| 文章编号： | 1672-4410(2004)03-0166-05 |
| 修稿时间： | 2004年3月5日 |
Simulated annealing algorithm for problem ofsorting a unsigned permutation by reversals |
| |
| TAO Yu-min\,ZENG Tao\,MO Shu-yuan\,SHI Yan-xia\.Simulated annealing algorithm for problem ofsorting a unsigned permutation by reversals[J].Journal of Anshan University of Science and Technology,2004,27(3):166-170. |
| |
| Authors: | TAO Yu-min\ ZENG Tao\ MO Shu-yuan\ SHI Yan-xia\ |
| |
| Institution: | TAO Yu-min\+1,ZENG Tao\+2,MO Shu-yuan\+2,SHI Yan-xia\+1 |
| |
| Abstract: | 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. |
| |
| Keywords: | genome rearrangement sorting by reversals simulated annealing algorithm |
| 本文献已被 CNKI 维普 等数据库收录！ |
