《DNA計(jì)算模型》PPT課件

《《DNA計(jì)算模型》PPT課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、DNA計(jì)算模型任曉玲2012年4月17日一、引言DNA計(jì)算的原理DNA分子作為信息載體（A、C、G、T四種堿基）原始問(wèn)題映射為DNA分子鏈數(shù)據(jù)運(yùn)算映射為對(duì)DNA分子鏈的生物操作（高度并行）在分子生物實(shí)驗(yàn)室完成這一系列的分子生物操作運(yùn)算載體運(yùn)算工具：生化酶——連接酶、核算內(nèi)切酶、聚合酶等生化反應(yīng)系統(tǒng)：退火、雜交、連接等檢測(cè)系統(tǒng)：電泳技術(shù)（重量、極性）；熒光技術(shù)[1]；納米金粒子技術(shù)[2]（一次性檢測(cè)出某個(gè)組合結(jié)合的構(gòu)成情況）等一、引言DNA計(jì)算的特點(diǎn)1、高密度的存儲(chǔ)量：1gDNA所能存儲(chǔ)的信息量相當(dāng)于10000億張普通CD光盤；2、高度的并

2、行性：DNA串的并行操作數(shù)可達(dá)1014；3、極低的能耗：DNA計(jì)算的能耗僅僅相當(dāng)于當(dāng)前電子計(jì)算機(jī)的十億分之一。二、DNA計(jì)算模型對(duì)目前出現(xiàn)的DNA計(jì)算模型按照所使用的計(jì)算主體的分子形態(tài)進(jìn)行較為系統(tǒng)的分類：2.1、雙鏈DNA模型2.2、粘貼模型（單雙鏈交替）2.3、單鏈DNA模型RNA模型發(fā)夾模型2.4、表面模型2.5、閉環(huán)DNA模型2.6、三維DNA模型2.1、雙鏈DNA模型雙鏈DNA模型包括兩種形式。一種是根據(jù)堿基互補(bǔ)配對(duì)原則使單鏈DNA分子雜交形成的雙鏈模型，這一系列是指利Adleman-Liption的模型發(fā)展而來(lái)的計(jì)算模型，其核心

3、的生物反應(yīng)為雜交反應(yīng)。另一種是直接構(gòu)造DNA雙鏈分子，通過(guò)各種生物酶的催化來(lái)實(shí)現(xiàn)的雙鏈模型，其核心的生物反應(yīng)為酶切反應(yīng)和酶聯(lián)反應(yīng)。2.1、典型文章第一類JunzoWatada及其合作者使用傳統(tǒng)的雙鏈模型解決了基于“距離”的數(shù)據(jù)聚類問(wèn)題[3,4]。他們將距離進(jìn)行預(yù)處理，使其可以通過(guò)DNA序列的長(zhǎng)短進(jìn)行表示，然后對(duì)數(shù)據(jù)和邊進(jìn)行編碼，最終實(shí)現(xiàn)其自動(dòng)聚類。第二類文獻(xiàn)[5]將雙鏈模型與酶連鎖反應(yīng)（LCR）相結(jié)合，實(shí)現(xiàn)了對(duì)可滿足性問(wèn)題的求解。LCR所具有的漂亮的性質(zhì)使我們可以通過(guò)控制引物來(lái)使那些只有滿足條件的雙鏈才能再次形成粘性末端并進(jìn)行新一輪的鏈接

4、實(shí)驗(yàn)，這種方式是逐個(gè)連接變量的一種較好的實(shí)驗(yàn)操作。2.2、粘貼模型粘貼模型是一種由存儲(chǔ)鏈（含有個(gè)由個(gè)堿基組成的不重疊的單鏈分子）和粘貼鏈（與存儲(chǔ)鏈上個(gè)位置的某個(gè)位置特定互補(bǔ)配對(duì)的個(gè)堿基構(gòu)成的單鏈PNA或DNA分子構(gòu)成[6]）構(gòu)成的部分雙鏈分子結(jié)構(gòu)。其信息（一般為布爾變量的形式）被編寫在存儲(chǔ)鏈上，輸入一個(gè)初始試管，輸出若干個(gè)最終試管。分離已退火的粘貼鏈可以分析存儲(chǔ)復(fù)合物，從而讀出最終試管的輸出物，當(dāng)然試管中也有可能不含任何存儲(chǔ)復(fù)合物。文獻(xiàn)[7]中所使用的是一種原始的Adleman-Liption模型和粘貼模型相結(jié)合的混合模型（Hybird-

5、model），就是仍然使用Adleman的編碼方式來(lái)編碼信息，使用粘貼鏈序列來(lái)特定的表示二進(jìn)制的數(shù)據(jù)，從而將這兩部分混合地編到統(tǒng)一DNA分子鏈上，根據(jù)實(shí)際問(wèn)題的需要進(jìn)行運(yùn)算。于是將雙鏈DNA模型中的Adleman-Liption模型和粘貼模型相結(jié)合，可以有豐富的生物操作。具體總結(jié)如下：2.3、單鏈DNA模型單鏈DNA模型是指使用單鏈DNA或者RNA為載體的計(jì)算模型。根據(jù)其所形成的單鏈分子的形態(tài)具體的分為發(fā)夾結(jié)構(gòu)和線性（存儲(chǔ)）結(jié)構(gòu)。發(fā)夾結(jié)構(gòu)“發(fā)夾”是單鏈核酸分子(DNA或RAN)中由于局部互補(bǔ)雜交而形成的一種空間莖環(huán)結(jié)構(gòu)，因其形似發(fā)夾而得名

6、。其結(jié)構(gòu)如圖所示文獻(xiàn)[8]使用左圖發(fā)夾模型解決了3-SAT問(wèn)題帽子（cap）結(jié)構(gòu)的發(fā)夾，文獻(xiàn)[9]使用右圖這種結(jié)構(gòu)作為輔助結(jié)構(gòu)解決了3-SAT問(wèn)題鏈狀結(jié)構(gòu)另外一種線性存儲(chǔ)模型是使用單鏈DNA或者RNA鏈來(lái)編碼信息，然后通過(guò)分管-合管操作來(lái)實(shí)現(xiàn)對(duì)問(wèn)題的求解。特別指出的是文獻(xiàn)[10]中使用RNA作為計(jì)算底物，其刪除操作使用的是核糖核酸酶H，因?yàn)樵撁傅奶匦跃褪强梢郧懈頡NA的端，進(jìn)而消化DNA/RNA雙螺旋鏈，而單鏈結(jié)構(gòu)不被破壞。而2002年由L.Adleman等人提出的一種類似的DNA計(jì)算模型[11]在求解3-SAT問(wèn)題時(shí)，由于反應(yīng)底物使用的

7、是DNA，其刪除操作使用的是長(zhǎng)度分離法。而二者的編碼方法都是對(duì)變量及其非進(jìn)行單獨(dú)編碼，生成變量組成的多重集作為初始試管。2.4、表面模型是將對(duì)應(yīng)于問(wèn)題解空間的單鏈DNA分子固定于一塊經(jīng)過(guò)特殊化學(xué)處理的固體表面如膠片、塑料、玻璃、硅半導(dǎo)體等，然后對(duì)表面上的DNA分子重復(fù)進(jìn)行標(biāo)記（mark）、破壞（destroy）、去標(biāo)記（unmark）等操作，最終獲得運(yùn)算結(jié)果[12]。特點(diǎn)：固定于固體表面的單鏈分子為靜態(tài)結(jié)構(gòu)操作過(guò)程可實(shí)現(xiàn)自動(dòng)化重復(fù)利用性編碼方式相對(duì)固定表面模型的編碼方式2000年Wisconsin大學(xué)的L.Smith等在解決SAT問(wèn)題時(shí)，

8、其編碼方式是使用DNA序列編碼布爾變量的每一種可能的組合。2001年清華大學(xué)的Wu對(duì)其編碼方式進(jìn)行了改進(jìn)[13]，其編碼方式是對(duì)變項(xiàng)和變項(xiàng)的非分別進(jìn)行編碼。對(duì)所有變項(xiàng)進(jìn)行編碼，相應(yīng)的非編碼為補(bǔ)