并行型Ramsey数DNA计算模型  

The Parallel Type of DNA Computing Model for Solving Ramsey Number Problem

作　　者：许进[1,2] 范月科[1] 

机构地区：[1]华中科技大学分子生物计算机研究所,武汉430074 [2]北京大学信息科学技术学院高可信软件技术教育部重点实验室,北京100871

出　　处：《计算机学报》2009年第12期2320-2324,共5页Chinese Journal of Computers

摘　　要：求解Ramsey数的困难在于需要搜索的解空间太大,而传统的电子计算机无法在有效的时间和存储空间上进行求解.由于DNA计算具有巨大的并行性和高密度存储能力等优点,文中研究了Ramsey数的DNA计算模型.针对传统的Ramsey数DNA计算模型存在的DNA序列量过多和序列过长的不足,利用DNA分子的特性以及生物操作将非解尽可能较早地消除,提出了并行型Ramsey数DNA计算模型,并以R(3,10)为例,给出了具体的求解步骤.The difficulty of solving the Ramsey number is that the solution space is too large to solve by traditional computer in effective time and storage space. Moreover, for the traditional DNA computing model, lots of oligonuleotides should be designed and generated much longer DNA sequences which are not convenient for bio-operation. This paper proposes a DNA computing model for Ramsey number based on the enormous parallelism and high-density storage capacity of DNA molecules. The advantage of this model is that many false solutions could be deleted as early as possible. Finally, the authors take R（3,10） as an example and give the concrete steps for solving the problem.

关 键 词：并行型 DNA计算 RAMSEY数 

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