本文關(guān)鍵詞： DNA 計(jì)算 Tile 自組裝 DNA 編碼 整數(shù)分解　出處：《國(guó)防科學(xué)技術(shù)大學(xué)》2013年碩士論文　論文類型：學(xué)位論文

【摘要】：DNA計(jì)算是一種基于生化反應(yīng)的新型信息處理模式,是一種新興的非傳統(tǒng)計(jì)算手段,自1994年創(chuàng)始以來,DNA計(jì)算的發(fā)展十分迅速,受到國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。近年來,隨著分子生物學(xué)和納米技術(shù)的發(fā)展,自組裝DNA計(jì)算成為了DNA計(jì)算中一種重要的模型,具有很高的研究?jī)r(jià)值,自組裝DNA計(jì)算憑借其理論上的海量存儲(chǔ)能力、自發(fā)有序性和強(qiáng)大并行性,成為難計(jì)算問題的潛在解決方案之一。通過對(duì)DNA單鏈進(jìn)行合適的編碼,若干條DNA單鏈能夠雜交形成含有若干粘性末端的Tile分子。Tile分子正是自組裝DNA計(jì)算的基本單元。自組裝DNA計(jì)算是在一定的溫度、酸堿度和一些特異性的生物酶的作用下,依據(jù)DNA的堿基互補(bǔ)配對(duì)原則,不同Tile分子通過粘性末端之間的互補(bǔ)配對(duì)進(jìn)行匹配組裝的過程�？梢詫⒆越M裝的初始框架看作問題的輸入,Tile分子的粘性末端之間的相互匹配組裝看作是信息的傳遞,最終得到的組裝體可看作問題的輸出。相比于其它DNA計(jì)算模型,自組裝DNA計(jì)算在運(yùn)算過程中不需要繁瑣的生化實(shí)驗(yàn)操作,可以更好地提高運(yùn)算的并行性,降低由人工操作而累積的誤差。理論上已證明二維自組裝DNA計(jì)算模型有通用計(jì)算能力,和圖靈機(jī)是等價(jià)的。隨著納米技術(shù)、生物信息學(xué)、分子生物學(xué)的進(jìn)一步發(fā)展,自組裝DNA計(jì)算將有廣闊的應(yīng)用前景,尤其在優(yōu)化計(jì)算、密碼學(xué)等科學(xué)領(lǐng)域中可能有創(chuàng)新性應(yīng)用。本文在研究基于Tile自組裝的DNA計(jì)算原理的基礎(chǔ)上,總結(jié)了DNA編碼序列設(shè)計(jì)的影響參數(shù)和約束條件,設(shè)計(jì)了一種基于Tile自組裝的DNA編碼序列設(shè)計(jì)方案,并通過生物實(shí)驗(yàn)對(duì)設(shè)計(jì)結(jié)果的正確性和有效性進(jìn)行了驗(yàn)證。基于自組裝運(yùn)算的高度并行性和自發(fā)有序性,提出了一種結(jié)合DNA折紙術(shù)的基于自組裝DNA計(jì)算模型求解整數(shù)分解問題的非確定性算法,通過設(shè)計(jì)種子模塊、乘法模塊、復(fù)制與識(shí)別模塊,充分利用自組裝運(yùn)算的高度并行性能力,使算法能并行猜測(cè)多個(gè)可能的分解結(jié)果,理論上可在多項(xiàng)式時(shí)間內(nèi)得到問題的解。針對(duì)抽象Tile自組裝運(yùn)算模型的特點(diǎn),設(shè)計(jì)了能夠模擬抽象Tile自組裝過程并給出組裝結(jié)果的程序,該程序能夠按用戶的需求配置抽象DNA Tile分子并模擬自組裝過程,給出自組裝可能的結(jié)果,使研究人員能夠直觀地查看自組裝模型的運(yùn)算過程,進(jìn)行方案的正確性驗(yàn)證與組裝結(jié)果的預(yù)測(cè),為基于Tile自組裝的DNA算法設(shè)計(jì)提供工具。
[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.
【學(xué)位授予單位】：國(guó)防科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2013
【分類號(hào)】：TP384
，

本文編號(hào)：1501193