本文選題：DNA計(jì)算 + 自組裝�。� 參考：《陜西師范大學(xué)》2012年碩士論文

【摘要】：由于電子計(jì)算機(jī)的發(fā)展受到來(lái)自器件工藝技術(shù)與制造成本等方面的限制,促使科學(xué)家研究新型信息處理模式。生物計(jì)算越來(lái)越受到人們的關(guān)注,尤其是DNA計(jì)算。DNA計(jì)算是一種以DNA分子與某些相關(guān)的生物酶等作為最基本材料,基于生化反應(yīng)的新型的分子計(jì)算方法。十多年的研究表明：DNA計(jì)算在求解圖與組合優(yōu)化中的一些困難的NP-完全問(wèn)題上具有內(nèi)在并行性、海量信息存儲(chǔ)能力等獨(dú)特優(yōu)勢(shì)。正是由于DNA計(jì)算的優(yōu)勢(shì),使得在未來(lái)的科學(xué)領(lǐng)域內(nèi),有望在優(yōu)化計(jì)算、密碼學(xué)、數(shù)學(xué)等眾多領(lǐng)域得到突破性的創(chuàng)新與應(yīng)用。目前國(guó)際上關(guān)于DNA計(jì)算機(jī)的研究形成一個(gè)新的科學(xué)前沿?zé)狳c(diǎn),正在極大地吸引不同學(xué)科、不同領(lǐng)域的眾多的科學(xué)家,特別是生物工程、計(jì)算機(jī)科學(xué)、數(shù)學(xué)、物理、化學(xué)、控制科學(xué)以及信息等領(lǐng)域內(nèi)的科學(xué)家。 本研究工作的目的是研究如何用DNA分子的特殊性質(zhì)以及各種可能的生物技術(shù)以及當(dāng)前飛速發(fā)展的納米技術(shù),建立用于解決圖與組合優(yōu)化問(wèn)題等NP完全問(wèn)題的計(jì)算模型,尤其是利用了當(dāng)前DNA分子自組裝的性質(zhì)建立自組裝計(jì)算的模型。這些模型的建立不僅為解決圖與組合優(yōu)化問(wèn)題等NP完全問(wèn)題提供了與以往電子計(jì)算機(jī)不同的算法,而且可以極大的降低算法的復(fù)雜度,解決當(dāng)前電子計(jì)算機(jī)無(wú)法解決的指數(shù)爆炸問(wèn)題,具有極大的理論價(jià)值和應(yīng)用價(jià)值。 本研究工作在已有研究成果的基礎(chǔ)上,利用納米技術(shù),提出了兩種解決圖與組合優(yōu)化問(wèn)題的DNA自組裝計(jì)算模型。 (1)首先,本論文介紹一種利用DNA三維自組裝計(jì)算模型解決圖的最大團(tuán)問(wèn)題的理論方法。首先,引入一種簡(jiǎn)單的求解最大團(tuán)問(wèn)題的非確定性算法；其次,根據(jù)算法設(shè)計(jì)不同類型的DNA自組裝基元；最后說(shuō)明自組裝過(guò)程及解的檢測(cè)方法。該計(jì)算模型的計(jì)算時(shí)間為線性,所需的自組裝基元種類為常數(shù),可以有效地降低求解最大團(tuán)問(wèn)題的復(fù)雜度。 (2)另外,本論文還提出了一種利用DNA納米金顆粒共聚體的自組裝過(guò)程解決圖論中一個(gè)NP完全問(wèn)題—連通度問(wèn)題的DNA計(jì)算方法,構(gòu)建了解決圖的連通度問(wèn)題的三維DNA自組裝計(jì)算模型。根據(jù)設(shè)計(jì)的算法,首先需要根據(jù)具體的圖的連通度問(wèn)題設(shè)計(jì)用于自組裝的DNA納米金顆粒共聚體,然后根據(jù)算法經(jīng)過(guò)一系列實(shí)驗(yàn)過(guò)程來(lái)求解連通度問(wèn)題。這種生物化學(xué)算法可以降低求解連通度問(wèn)題的復(fù)雜度,所使用的生物化學(xué)實(shí)驗(yàn)技術(shù)也很成熟且便于操作,為下一步DNA自組裝計(jì)算模型的應(yīng)用提供了可行的方案。本研究方法還將DNA鏈置換技術(shù)、DNA分子與納米金顆粒自組裝技術(shù)結(jié)合起來(lái),說(shuō)明了對(duì)微觀納米顆粒的控制能力及潛在應(yīng)用。 經(jīng)過(guò)本研究的工作,可以證明DNA分子計(jì)算與納米技術(shù)相結(jié)合,不僅可以提供自下而上的構(gòu)造微觀納米結(jié)構(gòu)的方法,也可以為將來(lái)DNA計(jì)算機(jī)的研制提供可靠的模型和有效的生物化學(xué)算法。
[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.
【學(xué)位授予單位】：陜西師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2012
【分類號(hào)】：TB383.1

【參考文獻(xiàn)】

相關(guān)期刊論文 前4條

1 張社民;方剛;;連通度問(wèn)題的三維DNA結(jié)構(gòu)進(jìn)化算法[J];計(jì)算機(jī)工程與應(yīng)用;2007年07期

2 陳智華;;基于DNA計(jì)算自組裝模型的Diffie-Hellman算法破譯(英文)[J];計(jì)算機(jī)學(xué)報(bào);2008年12期

3 黃玉芳;程珍;周康;肖建華;石曉龍;;基于DNA Tiles自組裝的布爾邏輯運(yùn)算[J];計(jì)算機(jī)學(xué)報(bào);2009年12期

4 方剛;張社民;許進(jìn);;邊連通度問(wèn)題的三維DNA圖結(jié)構(gòu)解法[J];系統(tǒng)工程與電子技術(shù);2006年01期

，

本文編號(hào)：1757931