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

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

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

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

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

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

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

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

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

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