本文選題：DNA計(jì)算 + NP-完全問(wèn)題�。� 參考：《安徽理工大學(xué)》2013年碩士論文

【摘要】：Adleman博士通過(guò)對(duì)含有7個(gè)頂點(diǎn)的有向哈密頓路的頂點(diǎn)進(jìn)行編碼,得到相應(yīng)的DNA鏈,再通過(guò)生物操作：連接,變性,PCR擴(kuò)增,電泳等等求解出了這一難題。實(shí)驗(yàn)的成功,開(kāi)啟了分子計(jì)算,尤其是DNA計(jì)算的新篇章。DNA鏈作為遺傳信息的載體,其自身的含有大量的遺傳密碼,及其計(jì)算時(shí)巨大的并行性不僅僅對(duì)解決像：可滿足性問(wèn)題,頂點(diǎn)覆蓋問(wèn)題,團(tuán)問(wèn)題,和獨(dú)立集問(wèn)題等NP-完全問(wèn)題提供了新思路,也吸引著專家學(xué)者們將DNA計(jì)算與其他學(xué)科或算法相結(jié)合用于解決更多的實(shí)際問(wèn)題。 本文首先介紹了最小生成樹(shù)和可滿足性問(wèn)題的一些背景知識(shí),及現(xiàn)在的研究現(xiàn)狀,其次對(duì)DNA計(jì)算的編碼及一些常用的計(jì)算模型進(jìn)行了總結(jié)。然后,詳細(xì)介紹了用凝膠電泳的方法求解最小支撐樹(shù)的相關(guān)問(wèn)題。利用DNA的熱力學(xué)特性,根據(jù)圖的邊權(quán)長(zhǎng)不同,給它們?cè)O(shè)計(jì)不同的DNA鏈,這些DNA鏈的溶解溫度也不同。根據(jù)溫度的不同,進(jìn)行電泳時(shí)DNA分子的形狀不同,電泳的速度也不同。再根據(jù)電泳速度分離出最小支撐樹(shù)的所有邊。以五個(gè)頂點(diǎn)的賦權(quán)圖為例并求它的最小支撐樹(shù),用來(lái)說(shuō)明該方法的簡(jiǎn)便性。接著,介紹了用基于DNA自組裝模型求解可滿足性問(wèn)題。先通過(guò)編碼可滿足性問(wèn)題變量的特殊補(bǔ)鏈,使其自組裝成分子信標(biāo)結(jié)構(gòu)；再與數(shù)據(jù)池中初始DNA鏈發(fā)生雜交反應(yīng),通過(guò)反應(yīng)前后分子信標(biāo)的熒光的變化來(lái)判斷是否是可滿足性問(wèn)題的解。若是可行解會(huì)產(chǎn)生熒光,通過(guò)拍照即可記錄可行解。該方法操作簡(jiǎn)單,便于觀察。 最后,總結(jié)全文,以DNA計(jì)算模型在圖論與離散數(shù)學(xué)中為例,討論了DNA計(jì)算模型的應(yīng)用,并展望DNA計(jì)算及DNA計(jì)算機(jī)的發(fā)展前景。
[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.
【學(xué)位授予單位】：安徽理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2013
【分類號(hào)】：TP38;Q523

【參考文獻(xiàn)】

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

1 劉文斌,高琳,王淑棟,劉向榮,許進(jìn);最大匹配問(wèn)題的DNA表面計(jì)算模型[J];電子學(xué)報(bào);2003年10期

2 朱翔鷗;劉文斌;孫川;;DNA計(jì)算編碼研究及其算法[J];電子學(xué)報(bào);2006年07期

3 周康;魏傳佳;劉朔;王防修;;可滿足性問(wèn)題的閉環(huán)DNA算法[J];華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年07期

4 許進(jìn);譚鋼軍;范月科;郭養(yǎng)安;;DNA計(jì)算機(jī)原理、進(jìn)展及難點(diǎn)(Ⅳ):論DNA計(jì)算機(jī)模型[J];計(jì)算機(jī)學(xué)報(bào);2007年06期

5 許進(jìn),董亞非,魏小鵬;粘貼DNA計(jì)算機(jī)模型(Ⅰ):理論[J];科學(xué)通報(bào);2004年03期

6 許進(jìn),李三平,董亞非,魏小鵬;粘貼DNA計(jì)算機(jī)模型(Ⅱ):應(yīng)用[J];科學(xué)通報(bào);2004年04期

7 趙健;錢璐璐;劉強(qiáng);張治洲;賀林;;基于線性自組裝的DNA加法[J];科學(xué)通報(bào);2006年21期

8 張成;楊靜;許進(jìn);;自組裝DNA/納米顆粒分子邏輯計(jì)算模型[J];科學(xué)通報(bào);2011年27期

9 陳漢奎,馮忻;溫度梯度凝膠電泳技術(shù)及應(yīng)用[J];生物化學(xué)與生物物理進(jìn)展;1999年03期

10 宋海洲;;求解度約束最小生成樹(shù)的快速近似算法[J];系統(tǒng)工程學(xué)報(bào);2006年03期

，

本文編號(hào)：1855936