時間膜計算系統(tǒng)的計算性能研究.pdf

1、自然計算是觀察自然界中各種生物現(xiàn)象所抽象出來的一個研究領(lǐng)域。近年來，受生物細胞結(jié)構(gòu)和功能的啟發(fā)，提出了一種新型的分布式生物計算模型—膜計算。在膜計算領(lǐng)域中研究的所有計算模型都統(tǒng)稱為膜系統(tǒng)。
　　在標(biāo)準膜計算系統(tǒng)中，假設(shè)存在一個全局時鐘對系統(tǒng)中所有的區(qū)域進行計時，并且每條規(guī)則的執(zhí)行時間都是一個單位時間。然而，在活細胞中，化學(xué)反應(yīng)或者復(fù)雜的生物操作（細胞分裂、細胞分離等）都需要一定的時間來執(zhí)行完成；在很多情況下，不同的生物過程需要花不

2、同的時間來完成，這些反應(yīng)依賴于環(huán)境，催化劑等因素。因此，標(biāo)準膜計算系統(tǒng)中每條規(guī)則執(zhí)行時間都是一個單位時間的假設(shè)是不合理的?；谶@個生物實際，本文建立了能夠克服規(guī)則執(zhí)行時間長短的魯棒系統(tǒng)，提出了各種時間膜計算系統(tǒng)，研究了這些系統(tǒng)在時間無關(guān)模式下求解計算困難問題的能力以及產(chǎn)生數(shù)的能力。主要工作包括：
　　研究了帶時間的活性膜膜系統(tǒng)的計算能力，證明了在使用標(biāo)準分裂規(guī)則（分裂生成的新膜標(biāo)簽與它們的父代膜標(biāo)簽相同）且分裂基本膜的情況下，活性

3、膜膜系統(tǒng)可以解決可滿足性（簡稱SAT）問題的時間無關(guān)半統(tǒng)一解（一個膜系統(tǒng)只能解決某個具體的例子）。如果系統(tǒng)允許分裂非基本膜，那么該膜系統(tǒng)可以解決SAT問題的時間無關(guān)統(tǒng)一解（一個膜系統(tǒng)可以解決一族參數(shù)大小相同的例子）。另外，給出了PSPACE完全問題（QSAT）的時間無關(guān)半統(tǒng)一解。最后，證明了時間無關(guān)活性膜膜系統(tǒng)在不同規(guī)則類型組合下都具有計算通用性。
　　提出了膜上帶蛋白的時間膜系統(tǒng)。研究了膜上帶蛋白的時間膜系統(tǒng)的計算能力，給出了基

4、于膜上帶蛋白膜系統(tǒng)的SAT問題時間無關(guān)統(tǒng)一解。證明了在時間無關(guān)模式下，該模型可以求解QSAT問題的統(tǒng)一解。本文還證明了時間無關(guān)膜上帶蛋白膜系統(tǒng)是計算通用的。
　　提出了膜生成的時間膜系統(tǒng)，研究了膜產(chǎn)生的時間膜系統(tǒng)的計算能力，證明了在時間無關(guān)模式下，如果考慮每個膜上都帶有一個電荷（或者正電荷或者負電荷或者中性），那么膜產(chǎn)生膜系統(tǒng)可以求解SAT問題的半統(tǒng)一解。另外，通過模擬帶出現(xiàn)檢測的矩陣文法，證明時間無關(guān)無極性膜產(chǎn)生膜系統(tǒng)（每個蛋白

5、質(zhì)最多只有兩種狀態(tài)）是計算通用的。
　　考慮將時間概念引入到類組織膜系統(tǒng)中，提出了時間組織膜系統(tǒng)。我們研究帶細胞分裂的時間組織膜系統(tǒng)，證明了在時間無關(guān)模式下，該模型可以求解子集和問題。本文還證明了時間無關(guān)組織膜系統(tǒng)在通訊規(guī)則長度不超過3時是計算通用的。
　　將膜分裂引入到通訊（同向/反向）膜系統(tǒng)中，提出了帶膜分裂的通訊膜系統(tǒng)。在標(biāo)準膜系統(tǒng)模式下研究了帶膜分裂的通訊膜系統(tǒng)的計算復(fù)雜性問題。通訊規(guī)則的長度定義為在該規(guī)則中所含物質(zhì)

6、數(shù)目的總和。本文證明了基于膜分裂的通訊膜系統(tǒng)可以解決P類問題如果所有通訊規(guī)則的長度不超過1；其次，如果所有通訊規(guī)則的長度不超過3，并且只能分裂基本膜的情況下，該膜系統(tǒng)可以在線性時間內(nèi)求解NP問題（子集和）；最后，證明了當(dāng)所有通訊規(guī)則長度不超過3且分裂規(guī)則可以是非基本膜時，該膜系統(tǒng)可以有效的求解PSPACE問題（QSAT）。因此，在帶膜分裂的通訊膜系統(tǒng)框架下，我們提供了一個界：從通訊規(guī)則的長度不超過1到通訊規(guī)則長度不超過3對應(yīng)于從非效率到