基于Tile自组装的DNA计算研究

发布时间：2018-02-10 18:51

  本文关键词： DNA 计算 Tile 自组装 DNA 编码 整数分解　出处：《国防科学技术大学》2013年硕士论文　论文类型：学位论文

【摘要】：DNA计算是一种基于生化反应的新型信息处理模式,是一种新兴的非传统计算手段,自1994年创始以来,DNA计算的发展十分迅速,受到国内外学者的广泛关注。近年来,随着分子生物学和纳米技术的发展,自组装DNA计算成为了DNA计算中一种重要的模型,具有很高的研究价值,自组装DNA计算凭借其理论上的海量存储能力、自发有序性和强大并行性,成为难计算问题的潜在解决方案之一。通过对DNA单链进行合适的编码,若干条DNA单链能够杂交形成含有若干粘性末端的Tile分子。Tile分子正是自组装DNA计算的基本单元。自组装DNA计算是在一定的温度、酸碱度和一些特异性的生物酶的作用下,依据DNA的碱基互补配对原则,不同Tile分子通过粘性末端之间的互补配对进行匹配组装的过程。可以将自组装的初始框架看作问题的输入,Tile分子的粘性末端之间的相互匹配组装看作是信息的传递,最终得到的组装体可看作问题的输出。相比于其它DNA计算模型,自组装DNA计算在运算过程中不需要繁琐的生化实验操作,可以更好地提高运算的并行性,降低由人工操作而累积的误差。理论上已证明二维自组装DNA计算模型有通用计算能力,和图灵机是等价的。随着纳米技术、生物信息学、分子生物学的进一步发展,自组装DNA计算将有广阔的应用前景,尤其在优化计算、密码学等科学领域中可能有创新性应用。本文在研究基于Tile自组装的DNA计算原理的基础上,总结了DNA编码序列设计的影响参数和约束条件,设计了一种基于Tile自组装的DNA编码序列设计方案,并通过生物实验对设计结果的正确性和有效性进行了验证。基于自组装运算的高度并行性和自发有序性,提出了一种结合DNA折纸术的基于自组装DNA计算模型求解整数分解问题的非确定性算法,通过设计种子模块、乘法模块、复制与识别模块,充分利用自组装运算的高度并行性能力,使算法能并行猜测多个可能的分解结果,理论上可在多项式时间内得到问题的解。针对抽象Tile自组装运算模型的特点,设计了能够模拟抽象Tile自组装过程并给出组装结果的程序,该程序能够按用户的需求配置抽象DNA Tile分子并模拟自组装过程,给出自组装可能的结果,使研究人员能够直观地查看自组装模型的运算过程,进行方案的正确性验证与组装结果的预测,为基于Tile自组装的DNA算法设计提供工具。
[Abstract]:DNA computing is a new information processing mode based on biochemical reaction, which is a new unconventional computing method. Since its inception in 1994, it has developed very rapidly, and has been widely concerned by scholars at home and abroad in recent years. With the development of molecular biology and nanotechnology, self-assembled DNA computing has become an important model in DNA computing, which has high research value. Self-assembled DNA computing has its theoretical capacity of massive storage. Spontaneous ordering and strong parallelism have become one of the potential solutions to difficult computational problems. A number of DNA single strands can be hybridized to form Tile molecules. Tile molecules containing a number of viscous ends are the basic units for the calculation of self-assembled DNA. The self-assembled DNA calculations are carried out at a certain temperature, pH, and some specific biological enzymes. According to the principle of base complementary pairing of DNA, The matching assembly process of different Tile molecules through complementary pairing between viscous ends can be regarded as the matching assembly between the viscous ends of the self-assembled molecules as the input of the problem. The final assembly can be regarded as the output of the problem. Compared with other DNA computing models, the self-assembled DNA computation does not require tedious biochemical experimental operation in the operation process, so it can improve the parallelism of the operation better. In theory, it has been proved that the two-dimensional self-assembled DNA computing model is equivalent to the Turing machine and has a general computing capability. With the further development of nanotechnology, bioinformatics, molecular biology, Self-assembled DNA computing will have a wide application prospect, especially in the fields of optimization computation, cryptography and so on. This paper studies the principle of DNA computing based on Tile self-assembly. In this paper, the influence parameters and constraints of DNA coding sequence design are summarized, and a DNA coding sequence design scheme based on Tile self-assembly is designed. The correctness and validity of the design results are verified by biological experiments. Based on the high parallelism and spontaneous ordering of self-assembly operations, A non-deterministic algorithm for integer decomposition based on self-assembled DNA computing model combined with DNA origami is proposed. Seed module, multiplication module, replication and recognition module are designed. By making full use of the high parallelism of self-assembly operation, the algorithm can conjecture several possible decomposition results in parallel, and theoretically obtain the solution of the problem in polynomial time. According to the characteristics of abstract Tile self-assembly operation model, A program is designed to simulate the abstract Tile self-assembly process and give the assembly results. The program can configure the abstract DNA Tile molecules according to the user's requirements and simulate the self-assembly process, giving the possible results of the self-assembly. It enables researchers to directly view the operation process of the self-assembly model, verify the correctness of the scheme and predict the assembly results. It provides a tool for the design of DNA algorithm based on Tile self-assembly.
【学位授予单位】：国防科学技术大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP384
，

本文编号：1501193