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

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

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

【參考文獻(xiàn)】

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

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

2 殷志祥,張風(fēng)月,許進(jìn);基于分子信標(biāo)的DNA計(jì)算[J];生物數(shù)學(xué)學(xué)報(bào);2003年04期

3 殷志祥,劉文斌,楊靜;分子信標(biāo)DNA計(jì)算模型的研究進(jìn)展與展望[J];生物學(xué)雜志;2005年05期

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

相關(guān)碩士學(xué)位論文 前1條

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

本文編號(hào)：2732157