《DNA計算模型》PPT課件

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

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

2、行性：DNA串的并行操作數(shù)可達(dá)1014；3、極低的能耗：DNA計算的能耗僅僅相當(dāng)于當(dāng)前電子計算機的十億分之一。二、DNA計算模型對目前出現(xiàn)的DNA計算模型按照所使用的計算主體的分子形態(tài)進行較為系統(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ù)堿基互補配對原則使單鏈DNA分子雜交形成的雙鏈模型，這一系列是指利Adleman-Liption的模型發(fā)展而來的計算模型，其核心

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

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

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

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

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

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