【作者】 王伟；

【导师】 殷志祥；

【作者基本信息】 安徽理工大学 ， 控制理论与控制工程， 2008， 硕士

【摘要】 自从Adleman博士1994年成功地给出用DNA计算方法求解有向图的Hamilton有向路问题以来,关于DNA计算与DNA计算机的研究开始飞速的发展,无论在理论研究上,还是实验方式的研究上都取得了很大的进展。DNA计算是一种以生物分子DNA作为计算介质,以生物化学反应作为计算工具的一种新型计算方法。其主要思想是:利用DNA特殊的双螺旋结构和碱基配对规律进行信息编码,把要运算的对象映射成DNA分子链,在生物酶的作用下,生成各种数据池,然后按照一定的规则将原始问题的数据运算高度并行地映射成DNA分子链的可控的生化过程。最后,利用分子生物技术如聚合链式反应PCR、超声波降解、克隆、诱变、分子纯化、电泳和磁珠分离等,检测所需的运行结果。DNA计算的最大优点是充分利用海量的DNA分子中的遗传密码,以及巨量的并行性。因而以DNA计算模型为背景而产生的所谓新一代计算机,DNA计算机,必有海量的存储和极高的运行速度。本文从DNA计算所使用的DNA分子构形角度,对目前主流的计算模型:表面计算模型、质粒计算模型、粘贴计算模型和分子信标计算模型进行了介绍。粘贴系统是建立在粘贴运算基础上的语言生成器,也是一种遵循Watson-Crick互补性质进行退火操作的DNA计算抽象模型。本文利用粘贴系统的巨大并行性,首先设计了模拟有向哈密顿路问题的粘贴系统,然后通过此粘贴系统所产生语言的性质对有向哈密顿路问题进行分析,给出了有向图的若干结构性质以及图中存在有向哈密顿路的充要条件。在我们的构造中,模拟问题的粘贴系统至多运行n-1步,其中n是模拟问题的规模。更多还原

【Abstract】 Since doctor Adleman successfully gave the solution of directed Hamilton path about directed graph with DNA computing in 1994, there have been significant research efforts on the DNA computing and the DNA computer. Prodigious progress has been gained on both theory and experiment. In this dissertation, some results have been made on DNA computing and DNA computer by way of building DNA computing model of some problems about the graph theory and combinatorial optimization.DNA computing is a new calculation method that used biological molecule DNA as calculation medium and biochemical reaction as calculation tool. The basic theory of DNA computing is: Encode information using the special structure of DNA double helix and nucleotides match rule, and mapping the object to operating to DNA molecules strands, and under the control of enzyme building a data pool, then using the rules appointed mapping the DNA molecules strands to a high speed parallel data computing bio-chemistry procedure. At last, using molecule biology technoly such as polymerization chain reaction (PCR), ultrasonic degradation, clone, trap, molecules purify, electrophoresis, magnet-bead separate and so on, detect the result of the reaction. The appealing characteristics of DNA computing are vast genetic codes of DNA molecules as well as massive parallelism of bio-chemical reactions. Therefore, new generation of computer based on DNA computing model (so-called DNA computer) features vast memory space and fast running speed.In this paper, the main computing model, including surface-based, plasmids, sticker and molecular beacon computing models were thoroughly introduced, from conformation of DNA molecules point of view.The sticker system is a language generative mechanism based on sticker operations, where sticker operations are the mathematical abstractions of DNA strands recombinant behaviors under restriction exonucleases, endonucleases, DNAligases and DNA polymerases. In this dissertation, the ideas of simulating directed Hamilton path problems by sticker systems are designed using their massive parallelism; Then some properties of directed graphs and sufficiency and necessity conditions of existing Hamilton paths in graphs are presented based on the analysis to directed Hamilton path problems according to the properties of languages generated by the sticker systems.In our construction, the sticker systems simulating problems run at most n-1steps, where n is the size of problems.更多还原