化學(xué)中的計(jì)算——dna計(jì)算的發(fā)展與模型概述

《化學(xué)中的計(jì)算——dna計(jì)算的發(fā)展與模型概述》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

1、化學(xué)中的計(jì)算型概述DNA計(jì)算的發(fā)展與模尹曉堯李非伯曉晨駱志剛左小磊國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院并行與分布重點(diǎn)實(shí)驗(yàn)室里事醫(yī)學(xué)研宄院輻射醫(yī)學(xué)研宄所中國(guó)科學(xué)院上海應(yīng)用物理研宄所物理生物學(xué)研宄室電子計(jì)算機(jī)的發(fā)展給人類社會(huì)進(jìn)步帶來了極大的推動(dòng)作用，但是隨著電子計(jì)算機(jī)制造工藝趨于極限，人們迫切需要找到一種新的計(jì)算體系來滿足口益增長(zhǎng)的計(jì)算需求。DNA計(jì)算因其超強(qiáng)的信息存儲(chǔ)、大規(guī)模的并行計(jì)算能力和超低的能耗而受到了廣泛的關(guān)注。自1994年Adieman在實(shí)驗(yàn)室利用DNA完成了一個(gè)6頂點(diǎn)哈密爾頓路求解問題開始，各種計(jì)算模型紛紛涌現(xiàn)

2、。木文首先對(duì)DNA計(jì)算的基本原理和實(shí)驗(yàn)操作手段進(jìn)行了簡(jiǎn)單的介紹，然后對(duì)DNA相關(guān)的理論進(jìn)行了闡述，包括DNA計(jì)算屮序列編碼設(shè)計(jì)的理論、DNA計(jì)算模型復(fù)雜度分析與通用計(jì)算能力的證明；在此基礎(chǔ)上，對(duì)突破性的DNA計(jì)算模型進(jìn)行了概括，進(jìn)而根據(jù)實(shí)驗(yàn)操作的具體手段將所有已知模型進(jìn)行了分類，按照類別進(jìn)行了綜述，并隨后挑選了該類別中經(jīng)典的模型進(jìn)行更為直觀的分析。更進(jìn)一步，在文章的最后，結(jié)合筆者的工作對(duì)DNA計(jì)算領(lǐng)域的前景進(jìn)行了展望。關(guān)鍵詞：DNA計(jì)算;NP難問題;并行重疊組裝模型;粘貼模型;剪接模型;DNATile組裝;

3、牛.化信號(hào);邏輯門;計(jì)算機(jī)研宄者們將計(jì)算問題劃分為三類:容易、困難和不可計(jì)算。對(duì)于容易類的計(jì)算問題，目前的電子計(jì)算機(jī)可以輕易地勝任;但是對(duì)于網(wǎng)難類的計(jì)算問題，即我們常說的NP（nondeterministicpolynomial,非多項(xiàng)式吋間可解）問題時(shí)，隨著問題規(guī)模的増大，計(jì)算所需要的時(shí)間呈指數(shù)級(jí)別増長(zhǎng)，傳統(tǒng)計(jì)算機(jī)難以維持。此外，隨著計(jì)算機(jī)制造工藝的不斷發(fā)展，芯片上集成的晶體管數(shù)量逐漸接近極限，量子效應(yīng)越發(fā)明顯，電子計(jì)算機(jī)的發(fā)展速度與計(jì)算需求之間的鴻溝進(jìn)一步擴(kuò)大。因此，科學(xué)家們致力于尋找其他全新的計(jì)算機(jī)結(jié)

4、構(gòu)，試圖有效地解決這些問題。DNA計(jì)算是一種以DNA分子與相關(guān)的某些生物酶作為基本材料，以某些生化反應(yīng)為棊礎(chǔ)的新的計(jì)算模式。其棊本思想是利用DNA分子特殊的雙螺旋結(jié)構(gòu)和堿基互補(bǔ)配對(duì)Watson-Crick原理，將所要處理的問題編碼為特定的DNA分子，通過一系列的生物化學(xué)反應(yīng)和基礎(chǔ)的實(shí)驗(yàn)操作，來實(shí)現(xiàn)運(yùn)算的過程，這種生物計(jì)算的思想開創(chuàng)了一種新的計(jì)算模式。DNA計(jì)算因?yàn)槠涑瑥?qiáng)的優(yōu)勢(shì)而受到了廣泛的關(guān)注，具體來說：（1）高度并行性，DNA計(jì)算機(jī)在一周內(nèi)的運(yùn)算量相當(dāng)于所有電子計(jì)算機(jī)問世以來的總運(yùn)算量；（2）儲(chǔ)存量大，D

5、NA作為遺傳信息的載體其信息存儲(chǔ)容量之大可達(dá)到一立方米溶液中存儲(chǔ)一萬億億比特的二進(jìn)制數(shù)據(jù)，遠(yuǎn)遠(yuǎn)超過目前所有電子計(jì)算機(jī)的總存儲(chǔ)量；（3）耗能低，DNA計(jì)算所消耗的能量只有一臺(tái)電子計(jì)算機(jī)完成同樣計(jì)算所消耗能量的十億分之一。DN八計(jì)算思想的提出己經(jīng)有了大半個(gè)世紀(jì)，早在1961年，F(xiàn)eynmanXll提出了分子計(jì)算的概念，但是由于受到當(dāng)時(shí)的實(shí)驗(yàn)條件、材料、生物技術(shù)等方面的限制，他的構(gòu)想并沒有真正得以實(shí)現(xiàn)。人們對(duì)分子生物學(xué)理論的認(rèn)識(shí)和研宂的深入，以及新的生物技術(shù)和實(shí)驗(yàn)方法的不斷涌現(xiàn)，為分子計(jì)算的實(shí)現(xiàn)打好了基礎(chǔ)。198

6、2年，提出了利用DNA分子構(gòu)造各種簡(jiǎn)單構(gòu)件的思想。1994年，八dlemanUl首次提出了哈密爾頓有向路問題的DNA分子生物計(jì)算方法，并成功地在裝有DNA溶液的試管屮進(jìn)行了實(shí)驗(yàn)，開創(chuàng)了計(jì)算科學(xué)的一個(gè)新領(lǐng)域，具有十分重大的意義，這一重大成果很快引起了數(shù)學(xué)、計(jì)算機(jī)、生物學(xué)等領(lǐng)域的研允者們的廣泛關(guān)注。1995年，LiptcmM提出基于DNA計(jì)算求解可滿足性問題的模型，將DNA序列映射為布爾矢量，通過一系列的溶液分離與合并操作，最終篩選出滿足條件的解。Seemarin首次提出了利用DNA分子構(gòu)成自組裝Tile結(jié)構(gòu)，

7、他利用其屮一種DXTile結(jié)構(gòu)建立多種復(fù)雜的算法模型對(duì)于二維的自組裝模型，Winfroo稱其為“Tile自組裝模型”，它是建立在Wang等皿提出來的Tile理論基礎(chǔ)上的；1995年，Winfi、ee［10］提出利用DNATile自組裝模型進(jìn)行計(jì)算的重要思想，并證明了二維自組裝模型有通用計(jì)算能力;2000年，Mao等［11］首次通過實(shí)驗(yàn)給出了自組裝DNA計(jì)算模型求解累積異或運(yùn)算的實(shí)現(xiàn)過程和方法。1997年，Ouyang等Uil提出了求解6頂點(diǎn)圖的最大團(tuán)問題的DNA計(jì)算模型，該方法通過分析原圖的補(bǔ)圖，利用酶切的

8、方法來縮小解搜索空間，并且對(duì)頂點(diǎn)的0和1進(jìn)行了不同長(zhǎng)度的編碼，使得可以通過瓊脂糖凝膠電泳測(cè)得的DNA序列的長(zhǎng)度來判斷最大團(tuán)的大小。其后，EngX^l提出了一種基于DNA表面計(jì)算求解可滿足性問題的計(jì)算模型。1997年，Hagiya等U41首次將單鏈0嫩分子形成的發(fā)卡結(jié)構(gòu)用于Boolcanu-formula的學(xué)習(xí)問題，利用該結(jié)構(gòu)實(shí)現(xiàn)丫分子的自動(dòng)控制問題。Head等［15］首次使用質(zhì)粒DNA模型求解了一個(gè)6頂點(diǎn)閣的最大