图的最大团与最大独立集粘贴DNA计算模型  

Sticker Model for Maximum Clique Problem and Maximum Independent Set

作　　者：范月科[1] 强小利[2] 许进[2] 

机构地区：[1]华中科技大学分子生物计算机研究所,武汉430074 [2]北京大学信息科学技术学院,北京100871

出　　处：《计算机学报》2010年第2期305-310,共6页Chinese Journal of Computers

基　　金：国家自然科学基金(60533010;60910002;60974112;60971085;30970969);国家"八六三"高技术研究发展计划项目基金(2009AA012413);中国教育部博士点基金(20070001020)资助~~

摘　　要：粘贴模型(stickermodel)是DNA计算中一个很重要的模型.其主要原理就是采用单双链混合型DNA分子进行编码,其优点在于在生物操作过程中不需要DNA链的延伸,不需要生物酶的作用以及DNA链可重复使用等,因此引起了来自不同学科的学者们的广泛关注与兴趣.文中提出了一种求解图的最大团问题的DNA计算模型,该模型采用了两种基本并行计算处理思想,一种是将图分解成小的子图来处理的并行思想;另一种是进行并行生物操作.The sticker model is an important computing model in DNA computing which takes use of the combination of the single DNA strands and double strands to encode the information. The advantages can be concluded as follows （1） DNA strands can be used without augmentation~ （2） the DNA strands can be reused. In this paper, we proposed a DNA computing model to solve the maximum clique problem based on two parallel computing methods. One is to divide the graph into several subgraphs, and the other is to take bio-technology to fulfill the parallelism.

关 键 词：DNA计算 粘贴模型 最大团问题 

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