【摘要】：近年來,量子計算機、生物計算機、DNA計算等領域的創(chuàng)新工作引起了世人的廣泛關注。其中,以DNA計算(DNA computing)為主的生物計算因具有超大規(guī)模并行計算能力和潛在的巨大數(shù)據(jù)存儲能力等優(yōu)勢,使其成為發(fā)展非傳統(tǒng)高性能計算的重要途徑之一,備受科學界的關注。DNA計算是一種模擬生物分子結(jié)構(gòu)并借助于分子生物技術(shù)進行計算的新方法,開創(chuàng)了以生化反應作為計算工具的先例,它是解決一類難以計算問題的一種新方法,特別是它在解決NP難問題時顯示出其巨大的潛力。 DNA分子自組裝是DNA計算領域的一個重要研究分支,指在一定的溫度,濃度,酸堿度以及特定酶的作用下,一些帶有輸入信息的DNA分子,根據(jù)Watson-Crick互補配對原則,自組裝生成新的帶有輸出信息的DNA分子的過程。自組裝DNA計算模型組合了DNA計算、Tiling理論和DNA納米技術(shù),成為目前備受關注的模型之一。本文的創(chuàng)新點如下： 首先,將DNA Tile自組裝計算模型應用于求解NP-完全問題。對一個只含3個變量的3-可滿足性問題進行討論,把它分為“非”運算子系統(tǒng)和“或”運算子系統(tǒng)。同時分別給出“非”操作和“或”操作的DNA Tile自組裝計算實例。通過組合這兩個操作,根據(jù)DNA Tile自組裝的運算規(guī)則,對于任一給定的一組解,能自動的判斷它是否滿足該范式。由于DNA計算具有高度的并行性,所以對于可滿足性問題的所有解能同時進行判斷。 其次,在實際的計算科學中,對一個可滿足性問題,它的范式中的每個子句,變量的個數(shù)往往是隨機的。因此,在上述思想的基礎上,先列出該范式中所包含的全部變量,然后在每個子句中加入該子句所沒有的變量,使之成為含有n個變量的k-可滿足性問題。對于加入的變量進行特殊的標記,它們在運算的過程中不影響該范式的真值解。 第三,討論應用DNA Tile自組裝計算模型求解矩陣的加法。對于矩陣的加法,主要是對兩個數(shù)加法運算的延拓。先通過一個實例來說明兩個數(shù)加法的運算過程,然后以一個矩陣中的所有數(shù)作為初始行,另一個矩陣中的所有數(shù)作為初始列,進行加法運算。 在本文的最后部分,應用DNA的分子自組裝來解決可滿足性問題。其原理主要是在堿基互補配對的基礎上,通過相應DNA鏈發(fā)夾結(jié)構(gòu)的不斷形成與展開,利用凝膠電泳操作將各種不同長度的DNA鏈分離出來,最終得到所求問題的解。
【學位授予單位】：安徽理工大學
【學位級別】：碩士
【學位授予年份】：2011
【分類號】：TP38;O242.1
【圖文】：

條DNA單鏈組成，這兩條單鏈通過堿基間的氫鍵(hydrogen一bond)禍合在一起。DNA分子間還滿足堿基互補配對原則:其配對規(guī)律為嚓吟與嚓嚨配對，即腺鏢吟(A)一定與胸腺嚓陡(T)配對，鳥嘿吟(G)一定與胞喀陡(C)配對，反之亦然。如圖3所示。5’end3’end。StrandXDeoxDeoxyriboseoe0Xib0SG3’ends’end圖3反向平行的DNA鏈 Fig3antiParallelDNAehains .2DNA計算原理DNA計算的基本原理可簡要地通過圖4所示的框圖來描述:對所要求解的問題進行DNA編碼，生成DNA分子鏈，然后通過一系列的生物操作，得出DNA結(jié)果鏈，通過測序等生物操作讀出結(jié)果鏈，就是所求問題的解。圖5給出了DNA計算的框圖形式。DNA計算機的實現(xiàn)主要經(jīng)歷三個階段:試管階段、表面階段、芯片階段。試管階段就是DNA計算所基于的生化反應是在一個或多個試管的溶液里進行，反應過程可以同時或分階段加入所需的反應物，如引物、各種DNA分子、堿基dNTP、緩沖液、酶等;表面方式是將對應于問題解空間的DNA分子固定于一塊經(jīng)過化學處理的固體表面，如硅半導體、膠片、玻璃、塑料等，然后對表面上的DNA分子重復進行標記、破壞、去標記等操作，最后獲得運算結(jié)果;芯片方式是DNA計算研究的最終目標

圖5oNA計算框圖FigsThediagramofDNAeomPuting計算的生物操作計算是通過對DNA分子進行某些特定的生化操作來完成，既有物理的，也有化學的。物理操作實質(zhì)上調(diào)控生化反應、酸堿度等�；瘜W操作主要是通過各種酶的操作。下面簡要操作:和退火DNA鏈個DNA分子的雙鏈而不破壞其單鏈結(jié)構(gòu)，其方法之一是加解。這意味著DNA的雙鏈解鏈—這個過程稱為變性(denatur解的溫度從85℃到95℃，DNA分子的這個熔解溫度是將個單鏈分子的溫度。如果這種加熱過的溶液再被緩慢冷卻

【參考文獻】

相關期刊論文 前4條

1 高琳,馬潤年,許進;基于質(zhì)粒DNA匹配問題的分子算法[J];生物化學與生物物理進展;2002年05期

2 殷志祥,張風月,許進;基于分子信標的DNA計算[J];生物數(shù)學學報;2003年04期

3 殷志祥,劉文斌,楊靜;分子信標DNA計算模型的研究進展與展望[J];生物學雜志;2005年05期

4 ;Arithmetic computation using self-assembly of DNA tiles:subtraction and division[J];Progress in Natural Science;2009年03期

相關碩士學位論文 前1條

1 陳瑞;發(fā)夾結(jié)構(gòu)、分子信標在DNA計算中的應用[D];華中科技大學;2005年

本文編號：2732157