幾種DNA計算模型及其實現(xiàn).pdf

1、1994年,Adleman使用DNA分子解決了一個7節(jié)點的漢密爾頓路徑問題,由此開辟了DNA計算這個新興的研究領域。DNA計算的研究內(nèi)容是在分子生物學實驗的輔助下,以DNA為材料求解復雜的計算問題和構建可計算裝置。研究者認為,由于DNA分子能用于并行計算、能高密度存儲信息、能存在于細胞內(nèi),將來DNA計算有望彌補電子計算機的一些缺陷,在一些特殊領域發(fā)揮作用。
　　 本文對DNA有限狀態(tài)自動機和用DNA進行加法運算兩個領域進行了相關

2、研究。作者在理論上提出了計算模型,在實踐上做出了技術改進。全文由以下四部分組成。
　　 第一部分是有關:DNA計算的背景知識。首先介紹了DNA計算中常用的分子生物學技術,然后以幾個求解NP完全問題的算法為實例說明如何操縱DNA分子進行計算,最后對DNA計算過去十年來的發(fā)展做了簡要的回顧。
　　 第二部分是DNA有限狀態(tài)自動機的相關內(nèi)容。用DNA實現(xiàn)圖靈機模型是DNA計算研究的重要內(nèi)容,因為圖靈機是理論計算機的模型,可以模

3、擬任何的計算裝置。有限狀態(tài)自動機是一種實現(xiàn)了部分圖靈機功能的可編程自發(fā)計算裝置。本文在Benenson提出的DNA有限狀態(tài)自動機模型的基礎上做了一些技術上的改進。第一個改進是將熒光標記在輸入分子的5’端。這樣能方便的用毛細管電泳直接監(jiān)測所有的DNA計算中間產(chǎn)物,為優(yōu)化反應條件直接提供數(shù)據(jù)。第二個改進是成功的在固體表面實現(xiàn)了DNA有限狀態(tài)自動機反應。表面反應能便于實現(xiàn)DNA計算和自動控制技術的結合。該工作為進一步改造和發(fā)展DNA自動機模型

4、提供了技術上的支持。
　　 第三部分是用DNA進行加法計算的相關研究。由于加法器是計算機中最基本的運算模塊,研究者相繼提出各種DNA加法算法。本文提出了兩種DNA加法算法。首先提出一種并行的DNA加法算法。該算法的特點是能實現(xiàn)連續(xù)進位,輸入輸出鏈具有統(tǒng)一的形式。由于該算法實驗過程復雜,在實驗中只實現(xiàn)了一位的二進制加法。然后本文又提出一種基于線性自組裝的DNA加法算法。該算法的優(yōu)點是運算過程自發(fā)進行,實驗操作復雜度為常數(shù),即對于n

5、位二進制加法而言,實驗步驟數(shù)并不隨著n的增加而增加。通過幾個隨機的四位的二進制加法,證實了該算法在實驗操作上簡便可行。本文將自組裝加法算法與微機電系統(tǒng)(MEMS)相結合,構造了DNA加法器樣機。該加法器的計算元件是DNA分子,電子計算機控制微泵驅動陣列、微流路混合芯片、磁性反應器和電化學雜交芯片來分別完成自組裝加法算法中的實驗流程。這是實現(xiàn)DNA計算和MEMS技術相結合的新嘗試。
　　 第四部分是對本文工作的總結和對DNA計算未