分子下推自動機(jī)理論及應(yīng)用研究.pdf

1、DNA分子計(jì)算的工作原理是對生物系統(tǒng)進(jìn)行編碼，以生物化學(xué)反應(yīng)為基礎(chǔ)，利用生物技術(shù)實(shí)現(xiàn)生物系統(tǒng)的狀態(tài)轉(zhuǎn)移來實(shí)現(xiàn)計(jì)算過程。自從Adleman 博士1994年成功地給出用DNA計(jì)算方法求解有向圖的Hamilton 有向路問題以來，在短短的10多年內(nèi)，DNA計(jì)算引起了學(xué)術(shù)界的廣泛關(guān)注，取得了豐碩的成果。
　　 DNA計(jì)算具有并行度高，能耗低的特點(diǎn)。利用DNA計(jì)算的方法構(gòu)造的分子自動機(jī)是一種納米尺度的計(jì)算機(jī)構(gòu)，與傳統(tǒng)的DNA計(jì)算的不同之處

2、在于，它能夠?qū)崿F(xiàn)自動機(jī)的功能，在納米尺度進(jìn)行高度并行的邏輯、推理等運(yùn)算。因此分子自動機(jī)提供了一種研究DNA計(jì)算和納米計(jì)算的新思路，對其進(jìn)行編碼理論和運(yùn)行機(jī)理上的研究將有助于開拓DNA計(jì)算新的應(yīng)用領(lǐng)域。本文的主要工作包括：
　　 首先分析了Yakoov等人構(gòu)造的分子有限自動機(jī)，總結(jié)出該種分子有限自動機(jī)的硬件(限制性內(nèi)切酶)、軟件(狀態(tài)轉(zhuǎn)換分子)、有限自動機(jī)的狀態(tài)以及字符之間的相互制約的關(guān)系。根據(jù)這一結(jié)果編制出了相應(yīng)的計(jì)算機(jī)軟件，該

3、軟件可以在構(gòu)造該類型的分子有限自動機(jī)時(shí)，輔助進(jìn)行字符編碼和狀態(tài)轉(zhuǎn)換分子編碼。在該軟件的輔助下構(gòu)造出狀態(tài)和字符更多的分子有限自動機(jī)，其計(jì)算能力較yaakov等人設(shè)計(jì)的分子有限自動機(jī)要強(qiáng)。
　　 接著提出了一種新的分子下推存儲器的模型。首先利用一類特殊的限制性內(nèi)切酶實(shí)現(xiàn)了延長DNA分子鏈的功能。該類限制性內(nèi)切酶的特點(diǎn)是具有2個(gè)回文結(jié)構(gòu)的識別位點(diǎn)，并且切割位點(diǎn)在2個(gè)識別位點(diǎn)之間。接著利用該特性構(gòu)建了簡單的分子存儲器，研究了其存儲和讀取

4、機(jī)理，并通過改進(jìn)編碼使這種存儲器具有一定的編程能力，從而實(shí)現(xiàn)了按一定規(guī)律存儲字符信息的下推存儲器。通過分析表明，這種分子存儲器的可編程能力和存儲效率除了與所使用的限制性內(nèi)切酶的特性有關(guān)外，還受分子存儲器編碼的影響，并得出了分子存儲器存儲效率最高或者編程能力最強(qiáng)的編碼方式。研究表明該種下推存儲器模型也可以視為一種特殊的有限自動機(jī)模型(非全狀態(tài)轉(zhuǎn)換)，通過引入合適的調(diào)節(jié)分子，可以將其擴(kuò)展為全狀態(tài)轉(zhuǎn)換的可編程有限自動機(jī)。這種有限自動機(jī)模型優(yōu)點(diǎn)

5、在于：初始DNA分子的合成較為簡單；通過分子鏈的延長而非縮短來實(shí)現(xiàn)狀態(tài)轉(zhuǎn)換，這種狀態(tài)轉(zhuǎn)換機(jī)理可使計(jì)算步驟更多；最重要的是它能同時(shí)進(jìn)行狀態(tài)轉(zhuǎn)換與數(shù)據(jù)存儲，從而可以保存狀態(tài)轉(zhuǎn)換的歷史信息。
　　 進(jìn)而提出了一種分子下推自動機(jī)的模型。計(jì)算理論表明，具有一個(gè)下推存儲器的有限自動機(jī)的計(jì)算能力較單純的有限自動機(jī)強(qiáng)。通過將前述分子下推存儲器引入到的分子有限自動機(jī)的運(yùn)算中，獲得了計(jì)算能力更強(qiáng)的分子下推自動機(jī)。
　　 最后討論了分子自動機(jī)

6、可能的應(yīng)用。分子有限自動機(jī)的計(jì)算能力暫時(shí)還不能與電子計(jì)算相比，但是分子自動機(jī)是納米計(jì)算機(jī)的一種，有其自身的優(yōu)點(diǎn)，有望運(yùn)用于一些特殊的場合。文中介紹了一些簡單的理論計(jì)算的例子，同時(shí)對其可能的應(yīng)用領(lǐng)域進(jìn)行了說明。由于有限自動機(jī)可以用于信息加密和解密，因此分子有限自動機(jī)也可以實(shí)現(xiàn)類似的功能；而利用分子有限自動機(jī)進(jìn)行疾病診斷則是一個(gè)較有前景的應(yīng)用方向?？删幊谭肿哟鎯ζ骺梢杂糜诖鎯π畔?，同時(shí)也可以用于構(gòu)造一些分子池，文中以構(gòu)造圖頂點(diǎn)著色問題的分子