分子元胞自動機的DNA自組裝實現(xiàn).pdf

1、1994年，美國南加州大學(xué)的Adleman教授利用操作DNA分子技術(shù)成功地解決了有向Hamilton路徑問題，開創(chuàng)了生物計算的新時代。1995年，Winfree提出了利用DNA分子瓦片自組裝做計算的重要思想，為DNA計算領(lǐng)域的發(fā)展奠定了堅實的理論和實驗基礎(chǔ)。 元胞自動機是上個世紀(jì)50年代烏爾姆和馮·諾伊曼提出的一種離散型動力系統(tǒng)，它是研究復(fù)雜系統(tǒng)行為的最初理論框架，也是人工智能的雛形。一維分子元胞自動機的DNA自組裝實現(xiàn)已有多種

2、方法被提出，而二維分子元胞自動機的DNA自組裝實現(xiàn)至今還沒有理想的模型被提出，本文將在這方面進(jìn)行一些探索性的研究，并給出兩個利用DNA自組裝方法實現(xiàn)的二維分子元胞自動機的理論模型。 本文首先在回顧Rothemund及其合作者和Yin Peng及其合作者利用DNA分子自組裝實現(xiàn)一維分子元胞自動機的工作的基礎(chǔ)上，分析了用四個臂的DNA瓦片分子的自組裝實現(xiàn)二維分子元胞自動機的可能性及其復(fù)雜程度，得出雖然用四個臂的DNA瓦片分子可以實現(xiàn)

3、二維分子元胞自動機但是自組裝過程比較復(fù)雜的結(jié)論。 其次，本文分別介紹了用八個臂的串形DNA瓦片分子自組裝和用在四個臂上帶有剪切酶識別位點的六個臂的TX瓦片自組裝實現(xiàn)二維分子元胞自動機的兩種方法。在后一種二維分子元胞自動機的實現(xiàn)方法中，本文創(chuàng)造性地解決了DNA計算中一個較為困難的問題——信息傳遞的問題。在實現(xiàn)二維分子元胞自動機的研究中信息傳遞的問題也就是在元胞狀態(tài)更新過程中鄰居的信息怎樣傳遞給當(dāng)前元胞和當(dāng)前時刻元胞的狀態(tài)信息怎樣傳

4、遞給下一時刻的元胞等，在本文中引入了一種用分子自動機檢測和用轉(zhuǎn)換分子修改信息的方法將這一問題解決了。 最后，本文討論了二維分子元胞自動機在模擬復(fù)雜系統(tǒng)中的應(yīng)用，包括對“能自我復(fù)制的元胞自動機”和“生命游戲”的模擬，這兩種元胞自動機的計算都是等價于圖靈通用計算機的計算的，從計算機模擬的結(jié)果可以看出二維分子元胞自動機是完全可以實現(xiàn)這些計算的。 基于自動機與喬姆斯基語言層次之間的關(guān)系的理論，本文實際上通過兩種途徑構(gòu)建了一種新的