【作者】 马莹；

【导师】 殷志祥；

【作者基本信息】 安徽理工大学 ， 计算机科学与应用技术， 2007， 硕士

【摘要】 DNA计算是一种模拟生物分子DNA的结构并借助于分子生物技术进行计算的新方法。它开创了以化学反应作为计算工具的先例,具有广阔的应用前景。1994年,Adleman首次在Science公布了DNA计算的理论,利用DNA计算解决了图论中的哈密顿路径问题,并成功地进行了实验。Adleman的DNA计算完全是一种新的概念。它突破了传统计算机体系结构的束缚。DNA计算的基本思想是:利用DNA特殊的双螺旋结构和碱基互补配对规律进行信息编码,把要运算的对象映射成DNA分子链,在生物酶的作用下,生成各种数据池(datapool),然后按照特定的规则将原始问题的数据运算高度并行地映射成DNA分子链的可控的生化过程。最后,利用分子生物技术如聚合链反应PCR、超声波降解、亲和层析、克隆、诱变、分子纯化、电泳、磁珠分离等,检测所需要的运算结果。DNA计算的核心问题是将经过编码后的DNA链作为输入,在试管内或其它载体上经过一定时间完成可以控制的生物化学反应,并以此来完成运算,使得从反应后的产物中能得到全部的解空间。本文主要讨论了三类图论中问题的DNA计算模型,具体如下:最小支撑树问题的DNA算法:最小支撑树问题是图论中一个重要的、应用性很强的问题。求一个给定图的最小支撑树,常见的方法是Kruskal避圈法和破圈法。但这两种方法都需要判断图的圈,这是非常繁琐的。在这一章中,我们利用最小支撑树的基本定义及DNA编码,借助生物的基本操作电泳、探针分离及测序,给出了最小支撑树的DNA算法。通过该算法,最多只需n-1步就可以找到图的最小支撑树(n为图的定点数)。图的顶点着色问题的DNA算法:利用DNA粘贴模型的巨大并行性,从图顶点着色问题的本质出发,先把图的顶点着色问题分解成顶点独立集问题和顶点划分问题并给出这两个问题的DNA粘贴算法,然后调用这两个算法以解决图的顶点着色问题。实例证明DNA粘贴算法在理论上可以实现的。无向赋权图哈密顿路径问题的DNA算法:我们通过链中G、C含量的不同来表示不同的权值,对于权值较高的边使其具有高的GC含量否则具有较低的GC含量;因为GC配对是形成三共价键其解链温度(Tm)大于AT形成的二个共价键的结合,我们就很容易的能够根据它们解链温度的不同来提取出权值低的路径。我们采用粘贴短链随机生成所有路径,提取解时采用加热变性与PCR反应同时进行的方式,首先变性的个体具有较低的权值优先得到扩增,这样的特点很好的解决了权值表示及分离的问题。权值的表示方法对于其他相关问题也很有借鉴意义。针对GC碱基对进行配对时形成的三共价键能量高于AT结合时二共价键的特对权值进行编码并利用改进的PCR反应给出了较好的解决途径。为DNA计算模型在处理权值方面提供了好的方法。更多还原

【Abstract】 DNA computing is a new method of simulating biology molecular DNA-structure and relying molecular biology technology on computing. It set up the precedent of chemistry as a computing tool, and it has a splendid future.Adleman first published his method of DNA computing on science in 1994, using DNA computing solved the problem of Hamilton path in graph theory, and got success in experiment. The DNA computing is a complete new concept. It has broken through the bondage of traditional structure of computer. 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 technology such as polymerization chain reaction (PCR), ultrasonic degradation, hybridization, clone, trap, molecules purify, electrophoresis, magnet-bead separate and so on, detect the result of the reaction. So the core matter is leting the encoded DNA strands as input, and in test tube or other carrier take place specific bio-chemistry reactions controlled, then achieve the computing procedure to give the whole result space after the reaction.The efforts in this paper mainly include the following DNA computing model of three contents of the graph theory :The way of DNA computing of the minimal spanning tree :the minimal spanning tree problem is important and has profound implication .The algorithm of solving the minimum spanning tree has lots of methods.The methods of Kruskal escaping circle and destroying circle which are often used to solve the minimum spanning tree must solve circle.This is very tiring.In this paper , according to the basic definition of minimum spanning tree and DNA computing, we give a algorithm of DNA computing by way of molecule biology technology such as electroporesis and probe separate and sequencing.Through this method , we can find a graph of the minimum spanning tree most using n minus one walking.Using the huge parallelism of DNA sticker models , we first decompose the vertex-coloring problems of graph into vertex-independent set problems and vertex-partition problems from the essence of problems and show DNA sticker algorithms of the two problems. Then we solve vertex-coloring probles of graph transferring the two algorithms.No-direction weight Hamilton path problem. Hamilton path is about connected chart, has a path routed every vertex once and only once we call it Hamilton path. If has a Hamilton path that can go back to the vertex begin we call it Hamilton loop, while the contrast we call Hamilton path. If every edge give correspond weight the problem become the Hamilton path with weight. Adleman’s experiment research the direction Hamilton path problem with no weight. While we discuss in this paper is about Hamilton path with weight, so we have to treat two things about the weight and the direction. And the main problem is to solve the problem of weight, as to the direction we could give a transform of a no-direction edge to two direction edge. To weight we take use of different GC content to represent different weight, let heavy weight edge with higher GC content or have the lower; As to match of GC it form a three covalent bond has a higher divide-temperature (Tm ) compared with the two covalent bond of AT, so we could detect the path with lower weight easily according to their different divide-temperature. We adopt the method of stick short piece to random produce all path, detect the result we adopt the way of pyrogenation and PCR take place together, first metamorphic unit have lower weight and be amplified first, and this point solve the problem of weight express and separate. This kind of expression of weight has a good elicitation meaning towards such problems.更多还原