最大团问题的三链DNA计算模型  

Triple-stranded DNA Computation Model of Maximum Clique Problem

作　　者：陈芳 殷志祥 CHEN Fang;YIN Zhixiang(Mathematics and Big Data Institute,Anhui University of Science and Technology,Huainan 232001,China)

机构地区：[1]安徽理工大学数学与大数据学院,安徽淮南232001

出　　处：《安庆师范大学学报（自然科学版）》2018年第3期30-33,共4页Journal of Anqing Normal University(Natural Science Edition)

基　　金：国家自然科学基金(61672001;61702008)

摘　　要：本文研究利用三链DNA求解最大团问题。首先将最大团问题中的顶点编码为DNA片段,进行生化反应,组合成所有可能的情况,然后利用三链模型对解进行筛选,最终得到图的最大团。该模型降低了编码的复杂度,提高了检测效率,其他的NP(Non-deterministic Polynomial)问题也可用此方法来求解。In this paper,we solve the maximal clique problem by using triple-stranded DNA.First,we encode the vertices of the largest clique problem into DNA fragments,perform biochemical reactions,and combine them into all possible cases.Then we use the triple-strand model to filter the solution and finally obtain the maximum clique of the group.The model reduces the complexity of coding and improves the detection efficiency.Other NP problems can also be solved by this method.

关 键 词：DNA计算 最大团问题 三链DNA 

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