基于粘贴模型的最大团问题算法  

Sticker model-based DNA algorithm of maximum clique problem

作　　者：周康[1] 刘朔[1] 覃磊[1] 易校尉[1] 

机构地区：[1]武汉工业学院数理科学系,湖北武汉430023

出　　处：《华中科技大学学报（自然科学版）》2010年第9期89-92,共4页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(60574041);湖北省教育厅重点科学技术研究资助项目(D20091805);湖北省自然科学基金资助项目(2007ABA407)

摘　　要：对粘贴模型的组成、基本实验及其生化实现过程进行了分析,根据解决最大团问题的需要简化了粘贴模型.在粘贴模型中,提出了基于电泳技术和分离实验的DNA序列检测方法,可以检测多种存储链.基于分离实验提出了最大团问题的DNA算法,并给出其生化实现过程:先形成所有非空顶点子集的初始解空间;然后对每条边用分离实验进行检测,保留全部满足不相邻要求的顶点子集,从而得到全部团;再通过电泳实验得到全部最大团.通过检测实验输出实验结果,证明了算法的可行性和有效性.The composition and basic experiments of sticker model and its realization process in basic biochemical experiments were analyzed. Sticker model was simplified to solve the maximum clique problem. In sticker model, DNA sequence detection method based on electrophoresis technology and separation experiment was put forward, which can be used to detect experimental results containing various memory chains. Based on separation experiment DNA algorithm of maximum clique problem and its biochemical realization process were put forward, first the initial solution space of all nonempty vertex subsets was created, and all vertex subsets lected from the initial solution space to detect each satisfying the requirement of nonadjacent were seedge doing separation experiment, so all cliques are obtained, then all maximum cliques are obtained by doing electrophoresis experiment. The validity and feasibility of the DNA algorithm are explained by a simulate experiment.

关 键 词：DNA计算 粘贴模型 最大团问题 电泳技术 分离实验 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]