分子元胞自動(dòng)機(jī)的DNA自組裝實(shí)現(xiàn).pdf

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

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

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

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