發(fā)布時間：2018-05-07 07:16

  本文選題：DNA計算 + NP-完全問題�。� 參考：《安徽理工大學》2013年碩士論文

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

【參考文獻】

相關期刊論文 前10條

1 劉文斌,高琳,王淑棟,劉向榮,許進;最大匹配問題的DNA表面計算模型[J];電子學報;2003年10期

2 朱翔鷗;劉文斌;孫川;;DNA計算編碼研究及其算法[J];電子學報;2006年07期

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

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

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

6 許進,李三平,董亞非,魏小鵬;粘貼DNA計算機模型(Ⅱ):應用[J];科學通報;2004年04期

7 趙健;錢璐璐;劉強;張治洲;賀林;;基于線性自組裝的DNA加法[J];科學通報;2006年21期

8 張成;楊靜;許進;;自組裝DNA/納米顆粒分子邏輯計算模型[J];科學通報;2011年27期

9 陳漢奎,馮忻;溫度梯度凝膠電泳技術及應用[J];生物化學與生物物理進展;1999年03期

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

，

本文編號：1855936