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

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

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

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

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

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

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