经典Ramsey数DNA计算模型(Ⅱ)：基于位序列的DNA计算模型  

Classical Ramsey Number DNA Computing Model(Ⅱ): Add-Bit-Sequence DNA computing Model

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

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

出　　处：《计算机学报》2008年第12期2081-2089,共9页Chinese Journal of Computers

摘　　要：Ramsey数问题是组合数学乃至整个数学中最具魅力的研究领域,也是最困难的数学问题之一.对于经典Ramsey数,至今只有9个Ramsey数得到解决.按照传统的算法,其搜索空间太大,当前的电子计算机无法胜任.研究表明,DNA计算在求解困难的NP-完全问题上优于电子计算机.目前已经建立了众多求解NP-完全问题的DNA计算模型,但未见到用于求解Ramsey数的DNA计算模型.作者建立了一种新颖的DNA计算模型,用于一般经典Ramsey数的求解.全文共分两篇,该文属第二篇,在首篇工作的基础上,建立了所谓的经典Ramsey数位序列DNA计算模型,文中对模型的存储库的建立、解的检测子系统以及运算子系统等问题展开了较为详细地讨论,并给出了使用该模型求解经典Ramsey数详细的方法与步骤.Classical Ramsey number problem is a NP complete problem. It takes exponential time to solve classical Ramsey number problem with traditional electronics computer. It is necessary to study new computation methods because traditional electronics computer faces with greatly difficulty in solving NP complete problem. DNA computing possesses high parallelism in data and higher storage capacity than normal systems. Hence, in theory, it is feasible to solve NP complete problems with DNA computing. A novel DNA computing model based on add-bit-sequence is proposed for the classical Ramsey number problems in this paper. The model consists of memory sub-system, operation sub-system and detection sub-system. The DNA computing model is a novel method for solving classical Ramsey number problems. The designed method and process of DNA sequence in the memory sub-system are provided, such as restriction, algorithm and probe. The operation sub-system is set up with PCR technique, and the sub-system for detect is described. As for the encoding problem of storage sub-system, the authors give three steps as follows： Give a number for encoding according to the possible Ramsey number＇s size, and estimate the length of each encoding string; Determine the restrictive conditions for DNA sequences in light of biological techniques, such as the types of hybridization; Ensure the length of each encoding string on the basis of the above two conditions. As for how to delete the incorrect solutions, take the r（5,5） for example： Delete the DNA strands which denote the K5 from X; after finishing the first step, add bit to the rest DNA strands. Additionally, take the same steps as the first step to delete the incorrect solutions K5 or Ns. In order to make the sub-system based on DNA computer work, the authors consider using the following biological techniques, such as restriction and PCR to delete the incorrect solutions.

关 键 词：经典RAMSEY数 DNA计算 位序列DNA计算模型 

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