通訊膜計算系統(tǒng)研究綜述

宋勃升1,2， 徐 飛1

(1.華中科技大學(xué) 人工智能與自動化學(xué)院圖像信息處理和智能控制教育部重點實驗室, 湖北 武漢 430074;2.湖南大學(xué) 信息科學(xué)與工程學(xué)院, 湖南 長沙 410082)

0 引 言

膜計算是自然計算的分支, 由歐洲科學(xué)院院士P?un G[1]在芬蘭圖爾庫計算機科學(xué)中心訪學(xué)時提出.膜計算的提出為生物分子計算和非傳統(tǒng)計算提供了豐富的計算框架，是接近“具有計算功能的細(xì)胞”概念的計算模型. 膜計算由于在計算機科學(xué)、系統(tǒng)生物學(xué)、語言學(xué)等領(lǐng)域具有廣泛的應(yīng)用價值，該領(lǐng)域受到國內(nèi)外許多學(xué)者們的關(guān)注，根據(jù)不同的生物背景，學(xué)者們提出了許多膜計算模型[2-6]. 膜計算中所研究的模型統(tǒng)稱為膜系統(tǒng)(或P系統(tǒng))，是一個離散的、分布式并行計算模型.

經(jīng)過20年的發(fā)展，膜計算研究取得了豐富的研究成果.根據(jù)膜系統(tǒng)結(jié)構(gòu)不同，膜計算系統(tǒng)可以分為樹狀結(jié)構(gòu)膜系統(tǒng)(細(xì)胞型膜系統(tǒng))和任意圖結(jié)構(gòu)膜系統(tǒng)(組織型膜系統(tǒng)或脈沖神經(jīng)膜系統(tǒng))[1,7-8]. 受生物活細(xì)胞具有多種不同生物特性的啟發(fā)，學(xué)者們構(gòu)建了許多新型膜系統(tǒng)，譬如帶催化劑的膜系統(tǒng)[9]，帶促進(jìn)劑/抑制劑的膜系統(tǒng)[10]，剪切膜系統(tǒng)等[11].借鑒計算機科學(xué)中的基礎(chǔ)概念，學(xué)者們設(shè)計了各種不同運行模式的膜系統(tǒng)，譬如串行模式[12]、極小并行模式[13]和扁平極大并行模式[14]. 通過與經(jīng)典計算理論中的圖靈機進(jìn)行比較，證明了多數(shù)膜系統(tǒng)是圖靈完備的，即這些系統(tǒng)的計算能力與圖靈機等價[15-18]. 在膜系統(tǒng)中細(xì)胞分裂、細(xì)胞分離和細(xì)胞生成等規(guī)則，系統(tǒng)可以產(chǎn)生指數(shù)多個細(xì)胞，通過空間換時間的方式，膜系統(tǒng)可以有效地求解NP問題[19-21]，甚至是PSPACE問題[22-25].有關(guān)膜計算的應(yīng)用研究進(jìn)展，讀者可以參考膜計算手冊[26]，更多的應(yīng)用研究也可以參看文獻(xiàn)[27-30].

1 通訊膜系統(tǒng)計算能力

本節(jié)首先介紹細(xì)胞型和組織型通訊膜系統(tǒng)的概念，然后對這2類膜系統(tǒng)的一些變形以及計算能力進(jìn)行概述，模型中涉及的有關(guān)形式語言知識讀者可以參考文獻(xiàn)[31].

1.1 細(xì)胞型通訊膜系統(tǒng)

細(xì)胞型通訊膜系統(tǒng)是由P?un A等[32]首次提出的，該模型所使用的規(guī)則是同向/異向規(guī)則，并且系統(tǒng)以極大并行方式工作，具體計算模型如下.

定義1一個度為q≥1的細(xì)胞型通訊膜系統(tǒng)是一個元組Π=(Γ,,μ,1,…,q,1,…,q,iout),其中：

?Γ是一個有限字母表，?Γ；

?μ是一個含有q個節(jié)點的根樹；

同向規(guī)則：(u,out)或(u,in)，u∈Γ+；

異向規(guī)則：(u,out;v,in)，u,v∈Γ+；

?iout∈{0,1,…,q}.

規(guī)則(u,out)，(u,in)(或(u,out;v,in))的長度定義為|u|(或|u|+|v|).

如果在某一時刻膜i包含多重集u，那么同向規(guī)則(u,out)∈i在該時刻可以使用.當(dāng)使用該條規(guī)則時，多重集u被送到膜i的父代膜中.如果在某一時刻父代膜i包含多重集u，那么同向規(guī)則(u,in)∈i在該時刻可以使用.當(dāng)使用該條規(guī)則時，多重集u從膜i的父代膜被送到膜i中.

如果在某一時刻膜i包含多重集u，膜i的父代膜包含多重集v，那么反向規(guī)則(u,out;v,in)∈i在該時刻可以使用.當(dāng)使用該條規(guī)則時，多重集u被送出膜i，同時，多重集v從膜i的父代膜中被送進(jìn)膜i中.

已經(jīng)證明細(xì)胞型通訊膜系統(tǒng)具有圖靈通用性[32].

到目前為止，學(xué)者們提出了許多細(xì)胞型通訊膜系統(tǒng)的變形，帶細(xì)胞分裂的細(xì)胞型通訊膜系統(tǒng)[23]；帶通道狀態(tài)的細(xì)胞型通訊膜系統(tǒng)[33]，證明了在通訊規(guī)則長度、通道狀態(tài)數(shù)、細(xì)胞數(shù)目等多種組合情況下都具有圖靈通用性；進(jìn)化-通訊細(xì)胞型膜系統(tǒng)[34]，該膜系統(tǒng)的規(guī)則同時包含進(jìn)化規(guī)則和通訊規(guī)則，并且已經(jīng)證明該膜系統(tǒng)具有圖靈通用性.

1.2 組織型通訊膜系統(tǒng)

組織型膜系統(tǒng)由Martín-Vide等[7]提出，該模型中的規(guī)則為進(jìn)化規(guī)則，每個新生成的物質(zhì)都有一個指引，表示新生成的物質(zhì)將被送到哪個區(qū)域；簡化的組織型膜系統(tǒng)由Verlan[35]提出，該模型中的規(guī)則為通訊規(guī)則，系統(tǒng)中不會產(chǎn)生新的物質(zhì)，物質(zhì)在系統(tǒng)中僅僅是位置的改變.

定義2一個度為q≥1的組織型通訊膜系統(tǒng)是一個元組Π=(Γ,,1,…,q,,iout),其中：

?Γ是一個有限字母；

異向規(guī)則：(i,u/v,j)，0≤i≠j≤q，u,v∈Γ+；

?iout∈{0,1,…,q}.

已經(jīng)證明組織型通訊膜系統(tǒng)具有圖靈通用性[35].

學(xué)者們提出了許多組織型通訊膜系統(tǒng)的變形，譬如帶促進(jìn)劑的組織通訊膜系統(tǒng)[36]、細(xì)胞上帶蛋白的組織通訊膜系統(tǒng)[16]、帶通道狀態(tài)的組織通訊膜系統(tǒng)[37]、帶進(jìn)化通訊的組織膜系統(tǒng)等[38].已經(jīng)證明，以上這些變形的組織通訊膜系統(tǒng)具有圖靈通用性.

2 通訊膜系統(tǒng)計算復(fù)雜性

2.1 帶膜分裂或膜分離通訊膜系統(tǒng)

為了研究通訊膜系統(tǒng)的計算復(fù)雜性，先給出帶細(xì)胞分裂的細(xì)胞型和組織型通訊膜系統(tǒng),以及帶細(xì)胞分離的細(xì)胞型和組織型通訊膜系統(tǒng)的概念，然后給出相應(yīng)的識別膜系統(tǒng).

定義3一個度為q≥1的帶細(xì)胞分裂細(xì)胞型通訊膜系統(tǒng)是一個元組

(2) 熵權(quán)法計算權(quán)重：設(shè)存在m個評價對象和n評價指標(biāo)，將定性評價指標(biāo)轉(zhuǎn)化為定量數(shù)據(jù)，構(gòu)建原始數(shù)據(jù)矩陣Z=[zij]mn，對矩陣Z進(jìn)行標(biāo)準(zhǔn)化處理，得到標(biāo)準(zhǔn)化矩陣K=[kij]mn，對于收益型指標(biāo)和成本型指標(biāo)標(biāo)準(zhǔn)化方法分別為：式中zmax、zmin為不同評價對象同一類指標(biāo)極值。

Π=(Γ,,μ,1,…,q,1,…,q,iout),

其中：

(1)Π=(Γ,,μ,1,…,q,1,…,q,iout)是一個細(xì)胞型通訊膜系統(tǒng)；

定義4一個度為q≥1的帶細(xì)胞分離細(xì)胞型通訊膜系統(tǒng)是一個元組

Π=(Γ,Γ0,Γ1,,μ,1,…,q,1,…,q,iout),

其中：

(1)Π=(Γ,,μ,1,…,q,1,…,q,iout)是一個細(xì)胞型通訊膜系統(tǒng)；

(2){Γ0,Γ1}是Γ的一個分割，即Γ=Γ0∪Γ1，Γ0,Γ1≠?，Γ0∩Γ1=?；

定義5一個度為q≥1的帶細(xì)胞分裂組織型通訊膜系統(tǒng)是一個元組

Π=(Γ,,1,…,q,,iout),

其中:

(1)Π=(Γ,,1,…,q,,iout)是一個組織型通訊膜系統(tǒng)；

定義6一個度為q≥1的帶細(xì)胞分離組織型通訊膜系統(tǒng)是一個元組

Π=(Γ,Γ0,Γ1,,μ,1,…,q,,iout),

其中：

(1)Π=(Γ,,1,…,q,,iout)是一個細(xì)胞型通訊膜系統(tǒng)；

(2){Γ0,Γ1}是Γ的一個分割，即Γ=Γ0∪Γ1，Γ0,Γ1≠?，Γ0∩Γ1=?；

根據(jù)以上定義，可以看出一個度為q≥1的任意膜系統(tǒng)均可以表示為(Γ,Γ0,Γ1,,μ,1,…,q,,iout),其中，如果Γ0=Γ1=?，則該膜系統(tǒng)不含分離規(guī)則，并且當(dāng)μ沒有明確給出時，則該膜系統(tǒng)為組織膜系統(tǒng).

定義7 一個度為q≥1的識別通訊膜系統(tǒng)是一個元組

Π=(Γ,Γ0,Γ1,,Σ,μ,1,…,q,,iin,iout),

其中：

(1)字母表Γ中包含2個不同的元素yes，no，至少一個包含在初始多重集中，但它們在初始時刻不能出現(xiàn)在環(huán)境中；

(2)存在一個嚴(yán)格包含在Γ中的額外字母表Σ(輸入字母表)，滿足?ΓΣ；

(4)iin∈{1,…,q}是輸入?yún)^(qū)域的標(biāo)簽，輸出區(qū)域iout是環(huán)境；

(5)所有的計算都停止；

根據(jù)文獻(xiàn)[39]，定義用同向/異向規(guī)則的識別膜系統(tǒng)在統(tǒng)一模式下求解判定性問題.

定義8 一個判定性問題X=(IX,θX)在多項式時間內(nèi)可以被一族識別膜系統(tǒng)Π={Π(n)|n∈}以統(tǒng)一的模式解決如果滿足以下條件：

(1)系統(tǒng)Π是圖靈機在多項式時間內(nèi)統(tǒng)一的；即對于系統(tǒng)Π(n)(n∈)，存在一個在多項式時間內(nèi)工作的確定性圖靈機；

(2)IX上存在一個多項式時間的計算函數(shù)對(cod,s)，使得：

- 對于任意一個例子u∈IX，s(u)是一個自然數(shù)，cod(u)是系統(tǒng)Πs(u)上的一個輸入多重集；

- 對每個自然數(shù)n∈，s-1(n)是一個有限集合；

- 系統(tǒng)族Π是關(guān)于(X,cod,s)多項式有界的，即存在一個多項式函數(shù)p(n)，對每一個u∈IX，系統(tǒng)Π(s(u)+cod(u))的所有計算都將在p(|u|)步內(nèi)停止；

- 系統(tǒng)族Π是關(guān)于(X,cod,s)充分的，即對每一個例子u∈IX，如果系統(tǒng)Π(s(u)+cod(u))存在一個接受的計算，那么θX(u)=1；

- 系統(tǒng)族Π是關(guān)于(X,cod,s)完備的，即對每一個例子u∈IX，并且滿足θX(u)=1，那么系統(tǒng)Π(s(u)+cod(u))的每一個計算都是一個接受的計算.

2.2 通訊膜系統(tǒng)計算復(fù)雜性

本小節(jié)介紹(類細(xì)胞或類組織)通訊膜系統(tǒng)的計算復(fù)雜性問題.

根據(jù)文獻(xiàn)[40]，一族識別組織膜系統(tǒng)解決一個判定性問題能夠被一族轉(zhuǎn)移膜系統(tǒng)有效的模擬.另外，一族識別轉(zhuǎn)移膜系統(tǒng)只能求解P類問題[41].因此，可以得到以下結(jié)論.

定理1P=PMC=PMC.

利用依賴圖，已經(jīng)證明帶細(xì)胞分裂的類細(xì)胞或類組織通訊膜系統(tǒng)在通訊規(guī)則長度最大為1時只能求解P類問題[42-43].

定理2P=PMC∩PMC.

哈密爾頓回路問題是著名的NP完全問題，已經(jīng)證明一族帶細(xì)胞分裂的識別組織膜系統(tǒng)在通訊規(guī)則長度最大為2時可以解決哈密爾頓回路問題[44]. 另外，文獻(xiàn)[45]證明哈密爾頓回路問題可以被一族帶細(xì)胞分裂的識別膜系統(tǒng)在通訊規(guī)則長度最大為2時求解.

定理3 NP∪co-NP?PMC∩PMC.

利用模擬的方法，已經(jīng)證明一族帶細(xì)胞分離的類細(xì)胞或類組織通訊膜系統(tǒng)在通訊規(guī)則長度最大為2時只能求解P類問題[46-47].

定理4P=PMC∩PMC.

文獻(xiàn)[48]證明一族帶細(xì)胞分裂的類組織通訊膜系統(tǒng)在通訊規(guī)則長度最大為3時可以求解可滿足性問題；另外，已經(jīng)證明一族帶膜分離的類細(xì)胞通訊膜系統(tǒng)在通訊規(guī)則長度最大為3時也可以求解可滿足性問題[46].

定理5NP∪co-NP?PMC∩PMC.

利用算法的方法，已經(jīng)證明一族帶細(xì)胞分離的類細(xì)胞或類組織通訊膜系統(tǒng)在環(huán)境為空時只能求解P類問題[49-50].

利用模擬的方法，已經(jīng)證明每一個帶細(xì)胞分裂的識別類組織通訊膜系統(tǒng)在通訊規(guī)則長度最大為k≥1時求解判定性問題X都可以被一族帶細(xì)胞分裂的識別類細(xì)胞通訊膜系統(tǒng)在環(huán)境為空和通訊規(guī)則長度最大為k≥1時有效的模擬(同樣求解判定性問題X)[51-52].

定理7對每一個k≥1有:

文獻(xiàn)[38]提出了進(jìn)化通訊組織膜系統(tǒng)，同時將細(xì)胞分裂規(guī)則引入到該膜系統(tǒng)中. 另外，文獻(xiàn)[53]提出了帶細(xì)胞分離的進(jìn)化通訊組織膜系統(tǒng)，并研究了該模型的計算復(fù)雜性問題.

由于標(biāo)準(zhǔn)的通訊規(guī)則(i,u/v,j)可以被看成進(jìn)化通訊規(guī)則[u]i[v]j→[v]i[u]j的特殊情況，因此，可以得出以下結(jié)論.

定理8對∈{,}，有：?.

定理9對∈{,}和每個k≥1有：

(k)?(k,k)?(2k).

定理10對∈{,}和每個k1,k2≥1，有：

(k1,k2)?(k1+k2).

定理11PMC=PMC=P.

定理12SAT∈PMC.

定理13對每一個自然數(shù)n≥1，有：

PMC=PMC=P.

定理14 SAT∈PMC.

3 結(jié)論與展望

經(jīng)過20年的發(fā)展，膜計算在理論和應(yīng)用2個方面均取得了重要的進(jìn)展. 本文僅僅對類細(xì)胞型和類組織型通訊膜系統(tǒng)在理論研究方面所取得的成果進(jìn)行概述[54]. 盡管通訊膜系統(tǒng)已經(jīng)取得不少的研究成果，但是大多數(shù)研究都集中在類組織型通訊膜系統(tǒng)，因此，類細(xì)胞型通訊膜系統(tǒng)將是未來的研究重點，作者認(rèn)為未來的研究可以考慮如下幾點：

(1)在膜計算理論研究中，學(xué)者們提出了許多的系統(tǒng)運行模式，譬如極小并行模式、串行模式和扁平極大并行模式等，研究類細(xì)胞型通訊膜系統(tǒng)在不同運行模式下的計算能力是一個值得考慮的方向.

(2)進(jìn)化通訊膜系統(tǒng)是最近新提出的計算模型，其研究主要集中在進(jìn)化通訊類組織型膜系統(tǒng). 研究進(jìn)化通訊類細(xì)胞型膜系統(tǒng)的計算復(fù)雜性將是一個有趣的方向.

(3)另外一個研究方向是將物質(zhì)在細(xì)胞間通訊過程中可以發(fā)生進(jìn)化的思想引入到一些新的模型中，譬如細(xì)胞上帶蛋白的組織膜系統(tǒng)[16]，帶促進(jìn)劑的組織膜系統(tǒng)等[36]，研究這些新模型的計算能力及計算復(fù)雜性問題.