基于批分离实验的最大独立集问题DNA算法

作     者：周康 万丹丹 赵洁 郑贺柱 

作者机构：武汉工业学院数理科学系湖北武汉430023 

基　　金：国家自然科学基金资助项目(61072143 60970065) 湖北省教育科学'十一五'规划课题资助项目(2010B290 2009B217) 湖北省教育厅科学技术研究重点资助项目(D20111702) 

出 版 物：《华中科技大学学报（自然科学版）》 (Journal of Huazhong University of Science and Technology(Natural Science Edition))

年 卷 期：2011年第39卷第6期

页      码：58-61页

摘      要：根据解决最大独立集问题的需要,讨论了简化的粘贴模型,该模型只由单链DNA的存储链和分离板组成.以分离实验为基础提出了批分离实验和生化操作过程,该实验可以快速分离存储链.基于批分离实验设计了最大独立集问题的DNA算法,并给出其生化实现过程:先形成所有顶点子集的初始解空间;接着用批分离实验对每个顶点进行检测,筛选全部满足不相邻要求的顶点子集,从而得到全部独立集;然后通过电泳实验得到全部最大独立集;最后通过检测实验输出实验结果.讨论并证明了算法的正确性和复杂性,算法的操作次数是线性的,通过仿真实验说明了算法的有效性和可行性.

主 题 词：DNA计算 粘贴模型 最大独立集问题 批分离实验 生化操作过程 

学科分类：0810[工学-土木类] 0808[工学-自动化类] 08[工学] 0812[工学-测绘类] 081202[081202] 

核心收录：

D　O　I：10.13245/j.hust.2011.06.018

馆 藏 号：203494873...