DNA计算模型研究与探索

发布时间：2018-05-07 07:16

本文选题：DNA计算 + NP-完全问题　；参考：《安徽理工大学》2013年硕士论文

【摘要】：Adleman博士通过对含有7个顶点的有向哈密顿路的顶点进行编码,得到相应的DNA链,再通过生物操作：连接,变性,PCR扩增,电泳等等求解出了这一难题。实验的成功,开启了分子计算,尤其是DNA计算的新篇章。DNA链作为遗传信息的载体,其自身的含有大量的遗传密码,及其计算时巨大的并行性不仅仅对解决像：可满足性问题,顶点覆盖问题,团问题,和独立集问题等NP-完全问题提供了新思路,也吸引着专家学者们将DNA计算与其他学科或算法相结合用于解决更多的实际问题。本文首先介绍了最小生成树和可满足性问题的一些背景知识,及现在的研究现状,其次对DNA计算的编码及一些常用的计算模型进行了总结。然后,详细介绍了用凝胶电泳的方法求解最小支撑树的相关问题。利用DNA的热力学特性,根据图的边权长不同,给它们设计不同的DNA链,这些DNA链的溶解温度也不同。根据温度的不同,进行电泳时DNA分子的形状不同,电泳的速度也不同。再根据电泳速度分离出最小支撑树的所有边。以五个顶点的赋权图为例并求它的最小支撑树,用来说明该方法的简便性。接着,介绍了用基于DNA自组装模型求解可满足性问题。先通过编码可满足性问题变量的特殊补链,使其自组装成分子信标结构；再与数据池中初始DNA链发生杂交反应,通过反应前后分子信标的荧光的变化来判断是否是可满足性问题的解。若是可行解会产生荧光,通过拍照即可记录可行解。该方法操作简单,便于观察。最后,总结全文,以DNA计算模型在图论与离散数学中为例,讨论了DNA计算模型的应用,并展望DNA计算及DNA计算机的发展前景。
[Abstract]:By coding the vertices of the directed Hamiltonian path with seven vertices, Dr Adleman obtained the corresponding DNA chains, and then solved the problem by biological manipulation: ligation, denaturing PCR amplification, electrophoresis, and so on. The success of the experiment has opened up a new chapter in molecular computing, especially in DNA computing. As a carrier of genetic information, the DNA chain itself contains a lot of genetic codes, and the huge parallelism in its computation is not just a solution to the problem of satisfiability. NP-complete problems such as vertex covering problems, clusterproblems, and independent set problems provide new ideas and attract experts and scholars to combine DNA computation with other disciplines or algorithms to solve more practical problems. This paper first introduces some background knowledge of minimum spanning tree and satisfiability problem, and then summarizes the coding of DNA computation and some commonly used computing models. Then, the problem of solving the minimum support tree by gel electrophoresis is introduced in detail. Based on the thermodynamic properties of DNA, different DNA chains are designed according to the different edge weight lengths of the graphs, and the dissolution temperatures of these DNA chains are also different. According to the temperature, the DNA molecular shape is different, and the electrophoretic speed is different. Then all the edges of the minimum support tree are separated according to the electrophoresis speed. Taking the weighted graph of five vertices as an example and finding its minimum support tree, the simplicity of the method is illustrated. Then, the solution of satisfiability problem based on DNA self-assembly model is introduced. First, by encoding special complementary chains of satisfiability problem variables, they are self-assembled into molecular beacon structures, and then hybridized with the initial DNA chains in the data pool. The fluorescence changes of molecular beacons before and after the reaction are used to determine whether the solution is satisfiability. If the feasible solution produces fluorescence, the feasible solution can be recorded by taking pictures. The method is simple and easy to observe. Finally, taking DNA computing model as an example in graph theory and discrete mathematics, the application of DNA computing model is discussed, and the development prospect of DNA computing and DNA computer is prospected.
【学位授予单位】：安徽理工大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP38;Q523

【参考文献】