DNA自组装计算模型及其应用

发布时间：2018-04-16 07:50

本文选题：DNA计算 + 自组装　；参考：《陕西师范大学》2012年硕士论文

【摘要】：由于电子计算机的发展受到来自器件工艺技术与制造成本等方面的限制,促使科学家研究新型信息处理模式。生物计算越来越受到人们的关注,尤其是DNA计算。DNA计算是一种以DNA分子与某些相关的生物酶等作为最基本材料,基于生化反应的新型的分子计算方法。十多年的研究表明：DNA计算在求解图与组合优化中的一些困难的NP-完全问题上具有内在并行性、海量信息存储能力等独特优势。正是由于DNA计算的优势,使得在未来的科学领域内,有望在优化计算、密码学、数学等众多领域得到突破性的创新与应用。目前国际上关于DNA计算机的研究形成一个新的科学前沿热点,正在极大地吸引不同学科、不同领域的众多的科学家,特别是生物工程、计算机科学、数学、物理、化学、控制科学以及信息等领域内的科学家。本研究工作的目的是研究如何用DNA分子的特殊性质以及各种可能的生物技术以及当前飞速发展的纳米技术,建立用于解决图与组合优化问题等NP完全问题的计算模型,尤其是利用了当前DNA分子自组装的性质建立自组装计算的模型。这些模型的建立不仅为解决图与组合优化问题等NP完全问题提供了与以往电子计算机不同的算法,而且可以极大的降低算法的复杂度,解决当前电子计算机无法解决的指数爆炸问题,具有极大的理论价值和应用价值。本研究工作在已有研究成果的基础上,利用纳米技术,提出了两种解决图与组合优化问题的DNA自组装计算模型。 (1)首先,本论文介绍一种利用DNA三维自组装计算模型解决图的最大团问题的理论方法。首先,引入一种简单的求解最大团问题的非确定性算法；其次,根据算法设计不同类型的DNA自组装基元；最后说明自组装过程及解的检测方法。该计算模型的计算时间为线性,所需的自组装基元种类为常数,可以有效地降低求解最大团问题的复杂度。 (2)另外,本论文还提出了一种利用DNA纳米金颗粒共聚体的自组装过程解决图论中一个NP完全问题—连通度问题的DNA计算方法,构建了解决图的连通度问题的三维DNA自组装计算模型。根据设计的算法,首先需要根据具体的图的连通度问题设计用于自组装的DNA纳米金颗粒共聚体,然后根据算法经过一系列实验过程来求解连通度问题。这种生物化学算法可以降低求解连通度问题的复杂度,所使用的生物化学实验技术也很成熟且便于操作,为下一步DNA自组装计算模型的应用提供了可行的方案。本研究方法还将DNA链置换技术、DNA分子与纳米金颗粒自组装技术结合起来,说明了对微观纳米颗粒的控制能力及潜在应用。经过本研究的工作,可以证明DNA分子计算与纳米技术相结合,不仅可以提供自下而上的构造微观纳米结构的方法,也可以为将来DNA计算机的研制提供可靠的模型和有效的生物化学算法。
[Abstract]:Because the development of computer is limited by the technology of device and the cost of manufacture, scientists are encouraged to study the new information processing mode.People pay more and more attention to biological computing, especially DNA computing. DNA computing is a new molecular calculation method based on biochemical reaction, which uses DNA molecules and some related biological enzymes as the most basic materials.For more than ten years, it has been shown that the solution to some difficult NP-complete problems in graph and combinatorial optimization by the weight DNA computing has some unique advantages, such as inherent parallelism, storage capacity of mass information, and so on.It is precisely because of the advantage of DNA computing that it is expected to be innovated and applied in many fields such as optimization, cryptography, mathematics and so on.At present, the international research on DNA computer has become a new scientific frontier hot spot, which is attracting a lot of scientists from different disciplines and fields, especially bioengineering, computer science, mathematics, physics and chemistry.Scientists in fields such as control science and information.The purpose of this work is to study how to use the special properties of DNA molecules, various possible biotechnology and the rapid development of nanotechnology to establish a computational model for solving NP-complete problems such as graph and combinatorial optimization problems.In particular, the model of self-assembly calculation is established by using the properties of self-assembly of DNA molecules.The establishment of these models not only provides different algorithms for solving NP-complete problems such as graph and combinatorial optimization problems, but also greatly reduces the complexity of the algorithms.It is of great theoretical and practical value to solve the exponential explosion problem which can not be solved by computer at present.In this paper, based on the existing research results, two DNA self-assembly models for solving graph and combinatorial optimization problems are proposed by using nanotechnology.First of all, this paper introduces a theoretical method of solving the maximum cluster problem of graphs by using DNA three-dimensional self-assembly computing model.Firstly, a simple non-deterministic algorithm is introduced to solve the maximum cluster problem; secondly, different types of DNA self-assembly primitives are designed according to the algorithm; finally, the self-assembly process and the solution detection method are described.The computational time of the model is linear and the type of self-assembled elements is constant, which can effectively reduce the complexity of solving the maximum cluster problem.In addition, a DNA method for solving a NP-complete problem of connectivity in graph theory by using the self-assembly process of DNA nanocrystalline copolymers is also proposed in this paper.A three-dimensional DNA self-assembly model for solving the connectivity problem of graphs is constructed.According to the designed algorithm, first of all, the DNA nanocrystalline gold copolymer used for self-assembly should be designed according to the connectivity problem of the graph, and then the connectivity problem should be solved through a series of experiments according to the algorithm.This biochemical algorithm can reduce the complexity of solving connectivity problems, and the biochemistry experimental techniques used are very mature and easy to operate, which provides a feasible scheme for the application of DNA self-assembly computing model in the next step.This method also combines DNA strand replacement technology with gold nanoparticles self-assembly technology, which shows the control ability and potential application of micro nanoparticles.Through the work of this study, it can be proved that the combination of DNA molecular calculation and nanotechnology can not only provide a bottom-up method for structuring micro nanostructures,It can also provide reliable model and effective biochemistry algorithm for the development of DNA computer in the future.
【学位授予单位】：陕西师范大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TB383.1

【参考文献】