淺析DNA計(jì)算及其發(fā)展?fàn)顩r

摘要：近年來，基于生化反應(yīng)機(jī)理的DNA計(jì)算模型受到科學(xué)領(lǐng)域內(nèi)許多不同學(xué)科領(lǐng)域?qū)W者們的關(guān)注。DNA計(jì)算已經(jīng)形成國際科學(xué)前沿領(lǐng)域內(nèi)研究的一個(gè)新的熱點(diǎn)。該文主要討論了DNA計(jì)算的原理，綜述了DNA計(jì)算的特點(diǎn)、DNA計(jì)算模型，并指出了DNA計(jì)算研究中存在的問題，最后就DNA計(jì)算的發(fā)展前景進(jìn)行了展望。

關(guān)鍵詞：DNA計(jì)算；計(jì)算模型；DNA計(jì)算發(fā)展前景

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2011)04-0920-02

Analysis DNA Computing and its Development

XIAO Zhen-nan1， JIANG Han-yang1，2，WANG Xiang-wen1

(1.Department of Computer Science and Technology， Hunan Technological and Economic Vocational College， Hengyang 421001， China;2. Department of Computer Science， Hengyang Normal University， Hengyang 421000， China)

Abstract: In recent years， based on the biochemical reaction mechanism of DNA computing model by many different scientific disciplines within the field of scholarly concern. DNA computing has become the forefront of international scientific research within the field of a new hot spot. This paper discusses the principle of DNA computing， DNA computing summarized the characteristics， DNA computing model， and pointed out the study of DNA computing problems， and finally to the development of DNA computing prospect.

Key words: DNA computing; computing model; prospects of DNA computing

DNA計(jì)算利用DNA特殊的雙螺旋結(jié)構(gòu)和堿基互補(bǔ)配對(duì)的原則對(duì)問題進(jìn)行編碼，把要運(yùn)算的對(duì)象映射成DNA分子鏈，在生物酶的作用下，生成問題的可能解即初始數(shù)據(jù)。然后按照一定的規(guī)則將原始問題的數(shù)據(jù)運(yùn)算并行地映射成DNA分子鏈的可控的生化過程。最后利用現(xiàn)代生物技術(shù)等手段獲得運(yùn)算結(jié)果。

1994年，Aldeman博士介紹了用DNA來解決復(fù)雜的數(shù)學(xué)問題想法。Aldeman是美國南加州大學(xué)的一名計(jì)算機(jī)科學(xué)家，在閱讀James Watson寫的《分子生物學(xué)的基因》得出了結(jié)論：DNA是有潛力的計(jì)算。Aldeman博士在實(shí)驗(yàn)室采用現(xiàn)代分子生物技術(shù)，在試管中利用DNA分子解決了具有7個(gè)頂點(diǎn)的有向Hamihon回路問題(Hamilton pathproblem。HPP)，該研究開創(chuàng)了用DNA分子解決經(jīng)典困難計(jì)算問題的先河。它的新穎性不在于算法。也不在于速度，而在于采用了迄今為止還沒有作為計(jì)算機(jī)硬件的生物工業(yè)技術(shù)來實(shí)現(xiàn)，并且開發(fā)了DNA潛在的并行性。隨著傳統(tǒng)電子計(jì)算機(jī)的制造工藝瀕I臨極限，DNA計(jì)算成為了傳統(tǒng)硅介質(zhì)計(jì)算機(jī)的最有利挑戰(zhàn)者。這一研究成果引起了世界范圍內(nèi)各個(gè)科學(xué)研究領(lǐng)域科學(xué)家的廣泛關(guān)注，繼而開辟了一個(gè)嶄新的研究領(lǐng)域--DNA計(jì)算。

目前，國內(nèi)北京大學(xué)、上海交通大學(xué)、西安交通大學(xué)系統(tǒng)工程研究所和華中科技大學(xué)分子生物計(jì)算機(jī)研究所等高校、科研單位和計(jì)算機(jī)專家在DNA計(jì)算科學(xué)研究領(lǐng)域取得了很好的研究成果。其中上海交通大學(xué)Bio—X生命科學(xué)研究中心和中科院上海生命科學(xué)院營養(yǎng)科學(xué)研究所于試管中完成了DNA計(jì)算機(jī)的雛形研制。在實(shí)驗(yàn)上把自動(dòng)機(jī)與表面DNA計(jì)算結(jié)合到了一起，這在中國還是首次。

1 DNA計(jì)算原理

DNA計(jì)算的原理來自分子生物學(xué)的研究成果。DNA鏈的巨大并行性和Watson—Crick的互補(bǔ)結(jié)構(gòu)使這樣的計(jì)算對(duì)解決一些問題。特別是一些傳統(tǒng)電子計(jì)算機(jī)還無法解決的問題，有了良好并且廣闊的發(fā)展前景。DNA計(jì)算原理圖如圖1所示。

DNA的來源廣闊．生物乃至人的體內(nèi)就擁有大量的DNA鏈。DNA是由聚合鏈組成．通常這樣的鏈稱為DNA鏈，DNA鏈由核苷酸構(gòu)成，核苷酸由4個(gè)不同的堿基：A(腺嘌呤)、G(鳥嘌呤)、C(胞嘧啶)、T(胸腺嘧啶)。而根據(jù)Watson—Crick互補(bǔ)雙鏈結(jié)構(gòu)．這樣的堿基配對(duì)相互吸引：A與T連接。G與C連接。正如電子計(jì)算機(jī)由0和1的編碼來編寫和表示信息一樣，由字母表Σ={A、T、G、Cl組成的DNA單鏈可以看做是編寫和表示信息的方法．而基于DNA鏈的一些生物操作(PCR操作、親和層析、超聲波降解、磁珠分離、凝膠電泳等)可以認(rèn)為對(duì)這個(gè)字母表的計(jì)算方式。這種計(jì)算，不僅是一種物理性質(zhì)的符號(hào)變換，也是一種化學(xué)性質(zhì)的變換，這種計(jì)算方式是前所未有的，是劃時(shí)代的。

2 DNA計(jì)算模型

DNA計(jì)算模型的研究已經(jīng)引起了數(shù)學(xué)、計(jì)算機(jī)科學(xué)、生命科學(xué)等領(lǐng)域研究者的廣泛關(guān)注。DNA計(jì)算研究的最終目的是構(gòu)造出具有巨大并行性的DNA計(jì)算機(jī)。在目前所獲得的DNA計(jì)算模型中，最能引起學(xué)者們興趣與關(guān)注的模型有如下幾種：粘貼模型、剪接系統(tǒng)模型、表面與芯片DNA計(jì)算模型、布爾電路模擬等。國內(nèi)開始DNA計(jì)算的研究始于1996年。到目前為止，我國關(guān)于DNA計(jì)算的研究已經(jīng)取得許多可喜的研究成果。如最小頂點(diǎn)覆蓋問題的Sticker模型，布爾電路模擬，DNA計(jì)算與遺傳算法，神經(jīng)網(wǎng)絡(luò)算法的結(jié)合，DNA計(jì)算中的編碼等。

目前，DNA計(jì)算模型主要分為基于DNA分子結(jié)構(gòu)特征的DNA計(jì)算模型和基于生物操作與實(shí)現(xiàn)的計(jì)算模型。

2.1 基于DNA分子結(jié)構(gòu)特征的DNA計(jì)算模型

1) 基于DNA分子結(jié)構(gòu)特征

粘貼模型是由Roweis等人于1996年提出來的。它是一種基于分子操作和隨機(jī)訪問內(nèi)存的一種DNA計(jì)算模型，是一種通用計(jì)算機(jī)系統(tǒng)。粘貼模型采用單鏈和雙鏈的混合形式進(jìn)行編碼，將一條長(zhǎng)鏈劃分為若干段。其中有些是單鏈，有些是雙鏈，單雙鏈隨機(jī)分布。若用單鏈表示數(shù)據(jù)0，用雙鏈表示數(shù)據(jù)1，則一條這祥的一個(gè)長(zhǎng)鏈可用來表示二進(jìn)制數(shù)據(jù)。由于單鏈和雙鏈根據(jù)不同的生物操作可發(fā)生變化，因而DNA鏈相當(dāng)于一個(gè)隨機(jī)數(shù)據(jù)存儲(chǔ)器。粘貼模型的優(yōu)點(diǎn)是在運(yùn)算過程中不需要DNA鏈的延伸，也不需要酶的作用，并且DNA鏈可重復(fù)使用。

2) 基于DNA分子結(jié)構(gòu)特征的其它計(jì)算模型

除了粘貼模型外，目前研究比較熱的還有剪切系統(tǒng)模型、插入—?jiǎng)h除系統(tǒng)模型、發(fā)夾DNA計(jì)算模型、質(zhì)粒DNA計(jì)算模型等。

2.2 基于生物操作與實(shí)現(xiàn)的DNA計(jì)算模型

基于生物操作與實(shí)現(xiàn)的DNA計(jì)算模型主要包括試管型、表面型兩種。

3 DNA計(jì)算的優(yōu)點(diǎn)

1) 運(yùn)算速度快

普通的計(jì)算機(jī)的運(yùn)算速度為106次/秒，目前最快的超級(jí)計(jì)算機(jī)的計(jì)算速度為1012次/秒，而對(duì)于分子計(jì)算機(jī)，如果是兩個(gè)DNA的連接視為一次操作，又假定4*1014個(gè)邊DNA片斷有一半發(fā)生了連接反應(yīng)，則分子計(jì)算機(jī)的運(yùn)算速度為1014次/秒。

2) 低能耗

生化反應(yīng)所需要的能量消耗很小， 完成同樣的運(yùn)算DNA計(jì)算所消耗的能量是大型機(jī)的十億分之一。

3) 存儲(chǔ)容量高

DNA存儲(chǔ)信息的密度是1bit/nm3，而當(dāng)前錄像帶的信息存儲(chǔ)密度僅為1bit/1212nm3。

4) 可以真正實(shí)現(xiàn)并行工作

傳統(tǒng)電子計(jì)算機(jī)主要是串行工作，而分子計(jì)算機(jī)可視為多CPU的并行工作，可以實(shí)現(xiàn)現(xiàn)有計(jì)算機(jī)無法真正實(shí)現(xiàn)的模糊推理和神經(jīng)網(wǎng)絡(luò)運(yùn)算功能。對(duì)于分子計(jì)算機(jī)，一個(gè)DNA分子相當(dāng)于一個(gè)CPU，在1molDNA溶液中就含有1023個(gè)分子，則可以實(shí)現(xiàn)1023量級(jí)的并行計(jì)算。

5) DNA計(jì)算存在的問題

隨著生物技術(shù)的不斷發(fā)展，DNA計(jì)算將會(huì)被用來解決更多的實(shí)際問題，特別對(duì)一些復(fù)雜巨系統(tǒng)中的問題。它將會(huì)給數(shù)學(xué)、計(jì)算機(jī)科學(xué)、生物學(xué)、化學(xué)和工程等學(xué)科帶來飛速的發(fā)展。但DNA計(jì)算本身也存在一些問題網(wǎng)：

1) 沒有統(tǒng)一的操作

由于其本身的生物技術(shù)的多樣性，基于DNA計(jì)算的基本操作并沒有統(tǒng)一。通常在不同的解決方案里會(huì)提出同樣的操作名稱，但其對(duì)應(yīng)的生物操作并不相同。對(duì)于研究者來講。在查閱相關(guān)資料時(shí)．不得不把更多的精力放在分子生物學(xué)操作上，這對(duì)于用DNA計(jì)算解決問題是不利的。特別是隨著問題規(guī)模的增大，所需要的DNA分子數(shù)目和各種酶的數(shù)量會(huì)呈指數(shù)增長(zhǎng)，而生物操作錯(cuò)誤和統(tǒng)計(jì)誤差的概率會(huì)被放大。

2) 自動(dòng)化程度不高

在DNA計(jì)算中人的參與還是比較多的，隨著DNA計(jì)算研究的發(fā)展，現(xiàn)在已經(jīng)出現(xiàn)了一些半自動(dòng)的DNA計(jì)算機(jī)，但還是無法離開人類的參與，從某些角度上來講，也大大制約了DNA計(jì)算的發(fā)展。

3) 缺乏良好的人機(jī)對(duì)話界面

DNA計(jì)算機(jī)要想真正地取代傳統(tǒng)電子計(jì)算機(jī)，就目前而言，在人機(jī)對(duì)話界面上還有待改進(jìn)，無法便利地輸入問題和獲得解，在這些方面還是無法離開傳統(tǒng)計(jì)算機(jī)。

4 DNA計(jì)算的發(fā)展前景

目前，關(guān)于DNA計(jì)算和DNA計(jì)算機(jī)的研究發(fā)展速度十分驚人。無論在理論研究上，還是實(shí)驗(yàn)方式的研究上都有很大的進(jìn)展舊。基于固體表面的DNA計(jì)算可不在溶液中進(jìn)行。這項(xiàng)成果大大降低了DNA計(jì)算的出錯(cuò)率。粘貼計(jì)算模型的出現(xiàn)使得在運(yùn)算過程中不需要DNA鏈的延伸，也不需要酶的作用。并且DNA鏈可重復(fù)使用，對(duì)DNA鏈的增長(zhǎng)起到了控制作用。

DNA計(jì)算應(yīng)用廣泛。利用DNA計(jì)算可以解決某些NP完全問題；實(shí)現(xiàn)數(shù)據(jù)加密、解密；進(jìn)行智能控制；解決生物化學(xué)、組合化學(xué)、醫(yī)學(xué)等領(lǐng)域問題；實(shí)現(xiàn)Boolean電路和數(shù)據(jù)流邏輯運(yùn)算等。

DNA計(jì)算是跨學(xué)科的研究熱點(diǎn)。涉及到DNA計(jì)算的學(xué)科有生物學(xué)、化學(xué)、數(shù)學(xué)和計(jì)算機(jī)科學(xué)等。

DNA計(jì)算研究方向廣泛，涉及到DNA計(jì)算的的主要研究方向有DNA nanotechnology、表面實(shí)驗(yàn)、算法設(shè)計(jì)和計(jì)算模型等。

5 小結(jié)

綜上所述，DNA計(jì)算的發(fā)展前景是非常廣闊的，隨著生物技術(shù)的發(fā)展，特別是越來越多的研究者的參與，DNA計(jì)算的研究將會(huì)出現(xiàn)一個(gè)嶄新的局面。很多制約現(xiàn)在DNA計(jì)算的問題慢慢會(huì)得到解決。雖然在很多方面，DNA計(jì)算還存在問題，但在特定的領(lǐng)域和復(fù)雜問題上，它已顯現(xiàn)出巨大的潛力。這一新領(lǐng)域的發(fā)展和研究值得關(guān)注和重視。

參考文獻(xiàn)：

[1] 高琳，許進(jìn)，張軍英.DNA計(jì)算的研究進(jìn)展與展望[J].電子學(xué)報(bào)，2001，29(7).

[2] 許進(jìn)，譚鋼軍，范月科，等.DNA計(jì)算機(jī)原理、進(jìn)展及難點(diǎn)(1V):論DNA計(jì)算機(jī)模型[J].計(jì)算機(jī)學(xué)報(bào)，2007(6).

[3] 王慶虎，鄭虹.一種新的求解最小生成樹問題的DNA算法[J].電腦知識(shí)與技術(shù)，2009(1).

[4] 鄭卉.DNA計(jì)算原理研究及展望[J].重慶電子工程職業(yè)學(xué)院學(xué)報(bào)，2009，18(2).

[5] 葉子.DNA計(jì)算方法及應(yīng)用[J].科技創(chuàng)新導(dǎo)報(bào)，2010(6).

[6] 支凌迎.DNA計(jì)算研究概述與分析[J].系統(tǒng)工程與電子技術(shù)，2009(6).