| 基于批分离实验的最大独立集问题DNA算法 |
| |
| 引用本文： | 周康,万丹丹,赵洁,郑贺柱.基于批分离实验的最大独立集问题DNA算法[J].华中科技大学学报(自然科学版),2011(6):58-61. |
| |
| 作者姓名： | 周康 万丹丹 赵洁 郑贺柱 |
| |
| 作者单位： | 武汉工业学院数理科学系; |
| |
| 基金项目： | 国家自然科学基金资助项目(61072143,60970065); 湖北省教育科学“十一五”规划课题资助项目(2010B290,2009B217); 湖北省教育厅科学技术研究重点资助项目(D20111702) |
| |
| 摘 要： | 根据解决最大独立集问题的需要,讨论了简化的粘贴模型,该模型只由单链DNA的存储链和分离板组成.以分离实验为基础提出了批分离实验和生化操作过程,该实验可以快速分离存储链.基于批分离实验设计了最大独立集问题的DNA算法,并给出其生化实现过程:先形成所有顶点子集的初始解空间;接着用批分离实验对每个顶点进行检测,筛选全部满足不相邻要求的顶点子集,从而得到全部独立集;然后通过电泳实验得到全部最大独立集;最后通过检测实验输出实验结果.讨论并证明了算法的正确性和复杂性,算法的操作次数是线性的,通过仿真实验说明了算法的有效性和可行性.
|
| 关 键 词： | DNA计算 粘贴模型 最大独立集问题 批分离实验 生化操作过程 |
Batch separation experiment-based DNA algorithm of maximum independent set problem |
| |
| Zhou Kang Wan D,an Zhao Jie Zheng Hezhu.Batch separation experiment-based DNA algorithm of maximum independent set problem[J].JOURNAL OF HUAZHONG UNIVERSITY OF SCIENCE AND TECHNOLOGY.NATURE SCIENCE,2011(6):58-61. |
| |
| Authors: | Zhou Kang Wan D an Zhao Jie Zheng Hezhu |
| |
| Institution: | Zhou Kang Wan Dandan Zhao Jie Zheng Hezhu(Department of Mathematics and Physics,Wuhan Polytechnic University,Wuhan 430023,China) |
| |
| Abstract: | Simplified sticker model was discussed based on the requirement of the maximum independent set problem.The simplified sticker model was only composed of DNA single-strand and separation glass.Batch separation experiment and its biochemical operation process were put forward on the basis of separation experiment,which can rapidly separate memory strand.DNA algorithm of maximum independent set problem was designed based on batch separation experiment.The biochemical realization process of the DNA algorithm wa... |
| |
| Keywords: | DNA(deoxyribonucleic acid) computing sticker model maximum independent set problem batch separation experiment biochemical operation process |
| 本文献已被 CNKI 等数据库收录！ |
