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

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

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

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

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

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