dna計算的研究與應用

dna計算的研究與應用

1國外dna計算機的研究1994年，美國科學家提出了計算dna的想法。通過控制dna分子之間的生化反應來完成手術(shù)。最大的優(yōu)點是dns分子擁有巨大的儲存能力和巨大的生化反應可能性。這一全新的計算理論，將在計算科學領域中產(chǎn)生極其深遠的影響。隨著傳統(tǒng)電子計算機制造工藝面臨極限，DNA計算機可望成為當今計算機的最有力挑戰(zhàn)者?，F(xiàn)有幾十個國家和地區(qū)的研究人員從事DNA計算機的研究，并取得許多突破性進展。2001年，以色列Weizmann科學研究所成功研制第一臺全自動運行的DNA計算機，它完全可以在生物體內(nèi)儲存和處理信息代碼，完成普通計算機的大部分功能。這使DNA計算機的研制向著實用化階段邁進了一大步。2002年，日本開發(fā)出全球第一臺能夠真正投入商業(yè)應用的DNA計算機，可用于基因的診斷。2006年，中國科學家通過應用DNA核酶成功研制一類新型“DNA邏輯門”，使系統(tǒng)的穩(wěn)定性大大增強。雖然DNA計算機的功能目前還比較簡單，但它的出現(xiàn)給計算科學領域的研究帶來了美好的前景。2計算dns2.1以?dna為芯片的新型計算機DNA計算是利用DNA雙螺旋結(jié)構(gòu)和堿基互補配對規(guī)律進行信息編碼，將要運算的對象映射成DNA分子鏈，通過生物酶的作用，生成各種數(shù)據(jù)池，再按照一定的規(guī)則將原始問題的數(shù)據(jù)運算高度并行地映射成DNA分子鏈的可控的生化反應過程。最后，利用分子生物技術(shù)（如聚合鏈反應PCR、超聲波降解、親和層析、克隆、誘變、分子純化、電泳、磁珠分離等），檢測所需要的運算結(jié)果。從數(shù)學上講，單鏈DNA可看作由符號A、C、G、T組成的串，同電子計算機中編碼0和1一樣，可表示成4字母的集合來譯碼信息。特定的酶可充當“軟件”來完成所需的各種信息處理工作。不同的酶用于不同的算子，如限制內(nèi)核酸酶可作為分離算子，DNA結(jié)合酶可作為綁結(jié)算子，DNA聚合酶可作為復制算子，外核酸酶可作為刪除算子等。這樣，通過對DNA雙螺旋進行豐富的、精確可控的化學反應以完成各種不同的運算過程，就可研制成一種以?DNA為芯片的新型計算機。已被證明DNA計算至少在理論上是通用的，可以解決圖靈機所能解決的所有問題。2.2超分子dna計算本質(zhì)上，DNA計算可以分為3類：分子內(nèi)、分子間和超分子DNA計算。Takahashi致力于分子內(nèi)DNA計算，借助于分子內(nèi)的形態(tài)轉(zhuǎn)移操作，用單DNA分子構(gòu)建可編程的狀態(tài)機。分子間DNA計算集中在不同DNA分子間的雜交反應，使其作為計算中的一個基本步驟，像Adleman的實驗。而超分子DNA計算是利用不同序列的原始DNA分子的自裝配過程進行的計算。目前，超分子DNA計算的創(chuàng)新及應用進入了一個新的臺階。例如，它已經(jīng)被用于藥物和DNA傳輸，對于生物傳感器也起到有效的作用。2.3dna計算模型DNA計算機的研制無疑要經(jīng)歷3個階段：首先是試管階段，驗證DNA計算原理的可行性；其次是表面階段，這也是一個過渡性階段，要克服試管中DNA分子的易丟失和操作難的缺點；最后是芯片階段，只有芯片化后，DNA計算機才能走向?qū)嵱谩＿@3個階段也就是DNA計算的3種實現(xiàn)方式。目前，DNA計算主要是在試管和表面兩種方式下進行，試管階段以1994年Alderman博士關于DNA計算的首篇文章為標志，諸如Lipton，Ouyang等人的研究均為試管階段；從1998年開始，基于表面的DNA計算模型逐步展開。相信生物芯片和表面技術(shù)的發(fā)展，DNA計算芯片的出現(xiàn)不會太遠。2.4實驗數(shù)據(jù)的可靠性問題經(jīng)過10多年的發(fā)展已有多種DNA計算模型被提出，如剪接模型、粘貼模型、等同檢測模型、插入/刪除系統(tǒng)、最小計算模型等，這些模型都被證明和圖靈機是等價的，也就是具有計算完備性。插入/刪除系統(tǒng)：插入/刪除系統(tǒng)是建立在上下文插入和刪除基礎上的DNA計算模型。Kari等人利用建立在該系統(tǒng)基礎上的遞歸可數(shù)語言特征，研究了形式語言和DNA計算的交叉性，證明了單個字母的插入/刪除系統(tǒng)同樣是計算完備的。在該系統(tǒng)中，如何選擇實際操作參數(shù)的數(shù)目，個體操作的速度，個體操作和序列操作的可靠性，信息載體的穩(wěn)定性及一個實驗中連續(xù)操作的數(shù)目都是要進一步研究的。剪接系統(tǒng)：Head在1987年利用形式語言對DNA序列進行分析的基礎上，提出了剪接系統(tǒng)的概念。1997年將其引入DNA計算領域，隨后，Paun等人對該系統(tǒng)的通用性、計算能力和剪接運算等方面進行了詳細的討論。剪接系統(tǒng)是目前研究較多、較為成熟的通用計算模型之一。粘貼系統(tǒng)：1996年，Roweis提出一種基于分子操作和隨機訪問內(nèi)存的DNA計算粘貼模型。它有著與剪接系統(tǒng)一樣的計算能力，而且與有限自動機理論有著密切的聯(lián)系，在運算過程中不需要DNA鏈的延伸，也不需要酶的作用，并且DNA鏈可重復使用。1998年，Kari等人受到粘貼模型的啟發(fā)，提出粘貼系統(tǒng)的概念隨后，Paun等人將粘貼系統(tǒng)的概念推廣到一個更為普遍的形式上。已有許多實例用粘貼模型來計算。但容錯性還需進一步地研究。等量檢測模型：1998年Yokomori提出了一種新的DNA計算模型DNA-EC。此模型是基于簡單的等量檢測計算理論。同檢測原理非常簡單，可在任何一種機器上實現(xiàn)，特別適合于分子計算，因為等量檢測只需對兩記憶單元進行等量性檢測，而記憶單元可描繪成雙鏈DNA序列形成的符號串。從嚴格的數(shù)學意義上講，等量檢測模型提供了一個極具吸引力的計算理論基礎，所需元素操作數(shù)目不多，模型簡單。但此模型的在實驗室中的可行性還有待研究。隨著DNA表面模型、DNA二級結(jié)構(gòu)、DNA空間構(gòu)造、DNA自裝配微結(jié)構(gòu)、鞭繩PCR的研究，新的模型必將出現(xiàn)，且這種模型是計算完備的、可編程、易實現(xiàn)的。3a/o計算以DNA計算模型為背景而產(chǎn)生的DNA計算機具有超大規(guī)模并行結(jié)構(gòu)，其最大的優(yōu)點在于驚人的存貯容量和運算速度。未來計算機的芯片和磁盤都可以用DNA溶液來代替。作為一種新型計算機，同樣需要具有輸入系統(tǒng)、輸出系統(tǒng)、運算系統(tǒng)和一定的通用性。這也是研究的重點與難點。3.1編碼約束條件10年來的研究表明，編碼問題是整個DNA計算機研制中最為核心的問題。它在一定程度上決定著DNA計算模式的未來走向：(1）它直接影響著DNA序列的合成質(zhì)量；(2）編碼的好壞直接影響著能否按照所設計的目標進行雜交；(3）編碼的好壞不僅直接影響著解空間的大小，而且與DNA計算機能否深入發(fā)展息息相關；(4）當前DNA計算的一個主要的難點是解的檢測問題。而編碼與酶切位點、發(fā)夾DNA分子或者熒光標記等的結(jié)合有望較好地解決這個問題。圍繞如何保證理想的生化反應和解的成功提取問題，人們提出了各種各樣的編碼約束條件。由于部分約束條件相互影響、相互制約，像GC含量和Tm值等。因此，當前各種模型和方法如遺傳算法模型，模板影射方法，最小子串方法等，所考慮的約束都不盡相同，他們從不同的角度進行編碼設計。最近文獻根據(jù)遺傳密碼的思想，按照三聯(lián)密碼子，將密碼子按照一定的規(guī)則將其分組，并從中選擇、組合所需要的編碼。這種方法有望解決假陽性問題。評價DNA編碼序列的好壞最好的方法是根據(jù)實驗驗證，鑒于實驗條件和實驗費用的限制，多采用模型評價。但是，根據(jù)相關約束條件建立一套通用的編碼序列評價體系是一件相當困難的事情。因為，一方面約束條件之間本身存在相互制約，并且不同的約束條件所要求的生物實驗條件和方法不同。再者，由于生化反應受多種條件的影響，微小的條件變化可能不會影響整體實驗效果及定性分析，但對于DNA計算來說，這種微小變化卻有可能是致命的。所以，選擇標準時應根據(jù)具體要求更改相應的評價體系。3.2dna數(shù)據(jù)存儲DNA分子是一種強有力且有效的天然信息存儲系統(tǒng)。它具有工作穩(wěn)定可靠、無磨損、信息容量大、存儲壽命長、信息質(zhì)量高、信息位的價格低、并行存取等優(yōu)點而被視為超高密度、超大容量的存儲器。因此，基于生物存儲的立體解決方案極有可能替代傳統(tǒng)的存儲系統(tǒng)。DNA存儲技術(shù)的研究是利用DNA分子巨大的信息儲藏能力和DNA分子能與多種生化酶相互反應的特點，來模擬并實現(xiàn)具有隨機讀寫能力的DNA數(shù)據(jù)存儲器。它不僅可以存儲大量信息，還可以利用其存儲安全性好的特點去存儲機密數(shù)據(jù)。它的研究也是整個生物分子計算機研究中的一個重要分支。Baum于1995年首次從理論上提出了構(gòu)建DNA存儲器的模型，稱可以構(gòu)建一個存儲容量比大腦還大的DNA存儲器。設想通過并行的雜交技術(shù)能實現(xiàn)并行相聯(lián)檢索，奠定了DNA存儲技術(shù)研究的基礎。在此基礎上，Rife于2002年用實驗證實了Baum模型的有效性。最近，Chen提出了具有學習和相聯(lián)檢索能力的存儲器。Kashiwamura在2003年構(gòu)建了一個具有高存儲密度和高特異性雜交的小型DAN存儲器，進行了實驗驗證。進一步與2005年證實了該存儲模型具有高精度的可控性并進行了大規(guī)模的計算機仿真。目前，DNA分子存儲技術(shù)的研究還處于萌芽階段，要投入應用以及取代目前存儲系統(tǒng)，尚有很多理論和技術(shù)問題需要解決。像作為數(shù)據(jù)載體的DNA分子的存取速度，反應過程中的單分子操作技術(shù)，反應的可靠性，通用的可編程生物存儲方法的實現(xiàn)等問題。3.3基于雙進制的其他加工過程運算作為一種新型計算機的運算系統(tǒng)，最基本的問題是解決算術(shù)和邏輯運算，并體現(xiàn)出DNA計算的優(yōu)點。在DNA計算機運算系統(tǒng)的研究中，首先取得突破性工作的是Frank等人引入位置算子、位置轉(zhuǎn)移算子和位節(jié)符等概念，用類似于電子計算機中的位數(shù)交換的方法，完成了二進制數(shù)的存取與進位，創(chuàng)造性地完成了對DNA分子生物運算過程的構(gòu)造與控制。進一步于1999年將其擴展到3進制乃至k進制的加法運算。1999年，Berard等人提出一種新的DNA加法模型，針對布爾邏輯輸入問題給出了解決方案。文獻給出了基于DNA計算模型的布爾矩陣和正實數(shù)矩陣乘法的運算算法，并將此方法進一步擴展，應用于矩陣的冪計算。以上問題的解決，使DNA計算機的實現(xiàn)向前邁進了一大步。但以上所提的模型無法進行負數(shù)的表示、減法運算以及除法運算，離實用的模型還有很大的距離。未來DNA計算機的運算系統(tǒng)不可能僅以四則運算為主要運算算子，還應以諸如連接酶、核酸內(nèi)切限制酶、DNA聚合酶、DNA與RNA修飾酶、核酸外切酶與核酸內(nèi)切酶等構(gòu)成的新型運算算子。3.4dna分子自動機在生物處理技術(shù)中的應用分子自動機是一種能夠在分子水平上按照自動機邏輯規(guī)則運行的生化反應系統(tǒng)，最大特點是反應過程完全通過生化反應自動完成。分子自動機模型的實驗研究則從如何利用DNA分子特性實現(xiàn)自動的狀態(tài)轉(zhuǎn)換入手。早在1973年，Bennent就提出了DNA圖靈模型，但是該模型僅僅為一個理論模型，與DNA分子自動機的實現(xiàn)還有很大的距離。2001年，以色列的Benenson等人用帶有粘性末端的雙鏈DNA分子與限制性內(nèi)切酶FOK1實現(xiàn)了一種可編程的2狀態(tài)有限自動機。為開發(fā)具有普遍意義的分子計算機提供了一種新思路。2003年該研究組還指出DNA分子除貯藏信息外，還貯藏能量，可利用這種能量來驅(qū)動分子計算。2004年Benenson等人開始將其提出的2狀態(tài)分子自動機模型應用于癌癥的基因診療研究，通過與癌癥發(fā)病相關基因的mRNA濃度調(diào)節(jié)上述自動機的狀態(tài)轉(zhuǎn)換分子活性。實驗在溶液環(huán)境中取得了成功，通過熒光標記與電泳等檢測手段顯示實驗結(jié)果與預期結(jié)果基本一致，表明分子自動機有可能解決疾病的基因診斷與治療問題。2005年Soreni等人進一步提出了3狀態(tài)的分子自動機模型。3.5基于遺傳算法的編碼搜索DNA計算的巨并行性以及海量存儲的特點，使其得以在多項式時間內(nèi)解決復雜計算問題。然而，當前所有DNA計算模型的策略是基于窮舉所有的候選解，再通過檢測來排除非解。但是，隨著計算變量數(shù)目的增加，這種算法的初始數(shù)據(jù)池大小將按指數(shù)級增長。所以，隨著問題的規(guī)模的不斷擴大，這種暴力窮舉法將是不可行的。因此，融入智能技術(shù)將可能打破這種暴力窮舉法的障礙，從一個相對較小的初始數(shù)據(jù)池中得到一種合理的解，避免窮舉所有候選解。遺傳算法是一種借鑒生物界自然選擇和進化機制發(fā)展起來的高并行、隨機、自適應搜索算法。由于其具有健壯性，特別適合于處理傳統(tǒng)搜索算法解決不好的復雜的和非線性問題。它是一種最有可能突破DNA計算中暴力窮舉法的限制的智能算法。Deaton等最早將遺傳算法用于DNA計算中的編碼搜索，當約束條件不多時，能夠得到滿足條件的編碼。遺傳算法應用于編碼搜索的最大難點在于影響編碼的因素太多，且各因素的權(quán)值不易確定。Yuan通過結(jié)合遺傳算法來避免窮舉的方法，并應用于解決圖的最大團問題。Kennedy和Eberhart通過對鳥群群體運動行為的研究于1995年提出了一種新的群智能算法———粒子群優(yōu)化算法（PSO）。與傳統(tǒng)的優(yōu)化算法相比，PSO算法求解過程不依賴于目標函數(shù)的解析性質(zhì)，同時能以較大概率收斂于全局最優(yōu)解。利用PSO算法進行編碼搜索將是一個極具潛力的方法。有望解決遺傳算法所遇到的障礙。蟻群系統(tǒng)是也是一種基于群智能的優(yōu)化算法，Huang通過在DNA計算中融入蟻群算法來修復或重構(gòu)計算過程中丟失的正確的解并成功應用于解決旅行商問題。總之，DNA計算與智能系統(tǒng)的結(jié)合在解決部分復雜問題具有許多潛在的優(yōu)點。4計算dns的應用程序和挑戰(zhàn)4.1dna計算方法的應用由于DNA計算采用的是一種新的運算邏輯和存儲方式，在解決某些復雜問題時將具有傳統(tǒng)計算機所無法比擬的優(yōu)勢。利用DNA計算已嘗試解決各種復雜計算問題，像HPP問題，最大團問題，可滿足性問題，著色問題和象棋問題等。Lipton認為所有NP問題都可以歸結(jié)為HPP問題，各種各樣的組合問題都被可以用DNA計算解決。然而，在解決NP完全問題上，自從2000年以后缺乏新的研究。目前，除解決NP問題，DNA計算還應用在以下幾個方面：(1）信息安全：DNA計算天生的并行計算優(yōu)勢對傳統(tǒng)密碼體系提出了挑戰(zhàn)。密碼學將是DNA計算的一個有著廣泛應用前景的應用領域，DNA計算機最先應用到的一個實際領域可能就是用來檢驗各種密碼體制的安全性。AES,RSA及ECC等密碼體制可能在未來的DNA計算機面前不堪一擊。(2）智能控制：利用DNA計算機理已開發(fā)出一種DNA編碼方法，該方法具有冗余和重疊的基因，可以選擇輸入變量和調(diào)節(jié)隸屬函數(shù)。并在人工DNA中可應用病毒和酶操作，獲取有效的模糊規(guī)則。此外，DNA序列已用于神經(jīng)網(wǎng)絡的建模于學習，并大大簡化了該網(wǎng)絡的參數(shù)數(shù)目。(3）生物化學和醫(yī)學等：DNA計算的發(fā)展能促進和指導生物化學獲得更規(guī)則、靈活和可靠的操作和技術(shù)，并產(chǎn)生出應用的具有特定性能的分子或“酶”。(4）布爾電路和數(shù)據(jù)流邏輯運算的仿真：這對構(gòu)建未來DNA計算機更有重要意義。4.2dna計算中的應用DNA計算的提出，徹底打破了現(xiàn)有的計算模式，使計算機具有模糊推理和神經(jīng)網(wǎng)絡運算功能以及類似人類的“智商”水平。但是DNA計算機缺乏一個固定模式。問題的多樣性將導致所采用的分子生物學技術(shù)的多樣性?？煞裨O計出可編程的DNA計算機？即，是否存在類似于電子計算機的通用計算模型———圖靈機那樣的通用DNA系統(tǒng)（模型）？如今，已經(jīng)提出了多種DNA計算模型，如剪接模型、粘貼模型、等量檢測模型等。但各有千秋，公認的DNA計算機的“圖靈機”還沒有誕生。另外，在當前所有DNA計算框架中，DNA串表達的計算狀態(tài)類