通讯膜计算系统研究综述

宋勃升1,2， 徐 飞1

(1.华中科技大学 人工智能与自动化学院图像信息处理和智能控制教育部重点实验室, 湖北 武汉 430074;2.湖南大学 信息科学与工程学院, 湖南 长沙 410082)

0 引 言

膜计算是自然计算的分支, 由欧洲科学院院士Păun G[1]在芬兰图尔库计算机科学中心访学时提出.膜计算的提出为生物分子计算和非传统计算提供了丰富的计算框架，是接近“具有计算功能的细胞”概念的计算模型. 膜计算由于在计算机科学、系统生物学、语言学等领域具有广泛的应用价值，该领域受到国内外许多学者们的关注，根据不同的生物背景，学者们提出了许多膜计算模型[2-6]. 膜计算中所研究的模型统称为膜系统(或P系统)，是一个离散的、分布式并行计算模型.

经过20年的发展，膜计算研究取得了丰富的研究成果.根据膜系统结构不同，膜计算系统可以分为树状结构膜系统(细胞型膜系统)和任意图结构膜系统(组织型膜系统或脉冲神经膜系统)[1,7-8]. 受生物活细胞具有多种不同生物特性的启发，学者们构建了许多新型膜系统，譬如带催化剂的膜系统[9]，带促进剂/抑制剂的膜系统[10]，剪切膜系统等[11].借鉴计算机科学中的基础概念，学者们设计了各种不同运行模式的膜系统，譬如串行模式[12]、极小并行模式[13]和扁平极大并行模式[14]. 通过与经典计算理论中的图灵机进行比较，证明了多数膜系统是图灵完备的，即这些系统的计算能力与图灵机等价[15-18]. 在膜系统中细胞分裂、细胞分离和细胞生成等规则，系统可以产生指数多个细胞，通过空间换时间的方式，膜系统可以有效地求解NP问题[19-21]，甚至是PSPACE问题[22-25].有关膜计算的应用研究进展，读者可以参考膜计算手册[26]，更多的应用研究也可以参看文献[27-30].

1 通讯膜系统计算能力

本节首先介绍细胞型和组织型通讯膜系统的概念，然后对这2类膜系统的一些变形以及计算能力进行概述，模型中涉及的有关形式语言知识读者可以参考文献[31].

1.1 细胞型通讯膜系统

细胞型通讯膜系统是由Păun A等[32]首次提出的，该模型所使用的规则是同向/异向规则，并且系统以极大并行方式工作，具体计算模型如下.

定义1一个度为q≥1的细胞型通讯膜系统是一个元组Π=(Γ,,μ,1,…,q,1,…,q,iout),其中：

•Γ是一个有限字母表，⊆Γ；

•μ是一个含有q个节点的根树；

同向规则：(u,out)或(u,in)，u∈Γ+；

异向规则：(u,out;v,in)，u,v∈Γ+；

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

规则(u,out)，(u,in)(或(u,out;v,in))的长度定义为|u|(或|u|+|v|).

如果在某一时刻膜i包含多重集u，那么同向规则(u,out)∈i在该时刻可以使用.当使用该条规则时，多重集u被送到膜i的父代膜中.如果在某一时刻父代膜i包含多重集u，那么同向规则(u,in)∈i在该时刻可以使用.当使用该条规则时，多重集u从膜i的父代膜被送到膜i中.

如果在某一时刻膜i包含多重集u，膜i的父代膜包含多重集v，那么反向规则(u,out;v,in)∈i在该时刻可以使用.当使用该条规则时，多重集u被送出膜i，同时，多重集v从膜i的父代膜中被送进膜i中.

已经证明细胞型通讯膜系统具有图灵通用性[32].

到目前为止，学者们提出了许多细胞型通讯膜系统的变形，带细胞分裂的细胞型通讯膜系统[23]；带通道状态的细胞型通讯膜系统[33]，证明了在通讯规则长度、通道状态数、细胞数目等多种组合情况下都具有图灵通用性；进化-通讯细胞型膜系统[34]，该膜系统的规则同时包含进化规则和通讯规则，并且已经证明该膜系统具有图灵通用性.

1.2 组织型通讯膜系统

组织型膜系统由Martín-Vide等[7]提出，该模型中的规则为进化规则，每个新生成的物质都有一个指引，表示新生成的物质将被送到哪个区域；简化的组织型膜系统由Verlan[35]提出，该模型中的规则为通讯规则，系统中不会产生新的物质，物质在系统中仅仅是位置的改变.

定义2一个度为q≥1的组织型通讯膜系统是一个元组Π=(Γ,,1,…,q,,iout),其中：

•Γ是一个有限字母；

异向规则：(i,u/v,j)，0≤i≠j≤q，u,v∈Γ+；

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

已经证明组织型通讯膜系统具有图灵通用性[35].

学者们提出了许多组织型通讯膜系统的变形，譬如带促进剂的组织通讯膜系统[36]、细胞上带蛋白的组织通讯膜系统[16]、带通道状态的组织通讯膜系统[37]、带进化通讯的组织膜系统等[38].已经证明，以上这些变形的组织通讯膜系统具有图灵通用性.

2 通讯膜系统计算复杂性

2.1 带膜分裂或膜分离通讯膜系统

为了研究通讯膜系统的计算复杂性，先给出带细胞分裂的细胞型和组织型通讯膜系统,以及带细胞分离的细胞型和组织型通讯膜系统的概念，然后给出相应的识别膜系统.

定义3一个度为q≥1的带细胞分裂细胞型通讯膜系统是一个元组

(2) 熵权法计算权重：设存在m个评价对象和n评价指标，将定性评价指标转化为定量数据，构建原始数据矩阵Z=[zij]mn，对矩阵Z进行标准化处理，得到标准化矩阵K=[kij]mn，对于收益型指标和成本型指标标准化方法分别为：式中zmax、zmin为不同评价对象同一类指标极值。

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

其中：

(1)Π=(Γ,,μ,1,…,q,1,…,q,iout)是一个细胞型通讯膜系统；

定义4一个度为q≥1的带细胞分离细胞型通讯膜系统是一个元组

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

其中：

(1)Π=(Γ,,μ,1,…,q,1,…,q,iout)是一个细胞型通讯膜系统；

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

定义5一个度为q≥1的带细胞分裂组织型通讯膜系统是一个元组

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

其中:

(1)Π=(Γ,,1,…,q,,iout)是一个组织型通讯膜系统；

定义6一个度为q≥1的带细胞分离组织型通讯膜系统是一个元组

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

其中：

(1)Π=(Γ,,1,…,q,,iout)是一个细胞型通讯膜系统；

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

根据以上定义，可以看出一个度为q≥1的任意膜系统均可以表示为(Γ,Γ0,Γ1,,μ,1,…,q,,iout),其中，如果Γ0=Γ1=∅，则该膜系统不含分离规则，并且当μ没有明确给出时，则该膜系统为组织膜系统.

定义7 一个度为q≥1的识别通讯膜系统是一个元组

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

其中：

(1)字母表Γ中包含2个不同的元素yes，no，至少一个包含在初始多重集中，但它们在初始时刻不能出现在环境中；

(2)存在一个严格包含在Γ中的额外字母表Σ(输入字母表)，满足⊆ΓΣ；

(4)iin∈{1,…,q}是输入区域的标签，输出区域iout是环境；

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

根据文献[39]，定义用同向/异向规则的识别膜系统在统一模式下求解判定性问题.

定义8 一个判定性问题X=(IX,θX)在多项式时间内可以被一族识别膜系统Π={Π(n)|n∈}以统一的模式解决如果满足以下条件：

(1)系统Π是图灵机在多项式时间内统一的；即对于系统Π(n)(n∈)，存在一个在多项式时间内工作的确定性图灵机；

(2)IX上存在一个多项式时间的计算函数对(cod,s)，使得：

- 对于任意一个例子u∈IX，s(u)是一个自然数，cod(u)是系统Πs(u)上的一个输入多重集；

- 对每个自然数n∈，s-1(n)是一个有限集合；

- 系统族Π是关于(X,cod,s)多项式有界的，即存在一个多项式函数p(n)，对每一个u∈IX，系统Π(s(u)+cod(u))的所有计算都将在p(|u|)步内停止；

- 系统族Π是关于(X,cod,s)充分的，即对每一个例子u∈IX，如果系统Π(s(u)+cod(u))存在一个接受的计算，那么θX(u)=1；

- 系统族Π是关于(X,cod,s)完备的，即对每一个例子u∈IX，并且满足θX(u)=1，那么系统Π(s(u)+cod(u))的每一个计算都是一个接受的计算.

2.2 通讯膜系统计算复杂性

本小节介绍(类细胞或类组织)通讯膜系统的计算复杂性问题.

根据文献[40]，一族识别组织膜系统解决一个判定性问题能够被一族转移膜系统有效的模拟.另外，一族识别转移膜系统只能求解P类问题[41].因此，可以得到以下结论.

定理1P=PMC=PMC.

利用依赖图，已经证明带细胞分裂的类细胞或类组织通讯膜系统在通讯规则长度最大为1时只能求解P类问题[42-43].

定理2P=PMC∩PMC.

哈密尔顿回路问题是著名的NP完全问题，已经证明一族带细胞分裂的识别组织膜系统在通讯规则长度最大为2时可以解决哈密尔顿回路问题[44]. 另外，文献[45]证明哈密尔顿回路问题可以被一族带细胞分裂的识别膜系统在通讯规则长度最大为2时求解.

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

利用模拟的方法，已经证明一族带细胞分离的类细胞或类组织通讯膜系统在通讯规则长度最大为2时只能求解P类问题[46-47].

定理4P=PMC∩PMC.

文献[48]证明一族带细胞分裂的类组织通讯膜系统在通讯规则长度最大为3时可以求解可满足性问题；另外，已经证明一族带膜分离的类细胞通讯膜系统在通讯规则长度最大为3时也可以求解可满足性问题[46].

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

利用算法的方法，已经证明一族带细胞分离的类细胞或类组织通讯膜系统在环境为空时只能求解P类问题[49-50].

利用模拟的方法，已经证明每一个带细胞分裂的识别类组织通讯膜系统在通讯规则长度最大为k≥1时求解判定性问题X都可以被一族带细胞分裂的识别类细胞通讯膜系统在环境为空和通讯规则长度最大为k≥1时有效的模拟(同样求解判定性问题X)[51-52].

定理7对每一个k≥1有:

文献[38]提出了进化通讯组织膜系统，同时将细胞分裂规则引入到该膜系统中. 另外，文献[53]提出了带细胞分离的进化通讯组织膜系统，并研究了该模型的计算复杂性问题.

由于标准的通讯规则(i,u/v,j)可以被看成进化通讯规则[u]i[v]j→[v]i[u]j的特殊情况，因此，可以得出以下结论.

定理8对∈{,}，有：⊆.

定理9对∈{,}和每个k≥1有：

(k)⊆(k,k)⊆(2k).

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

(k1,k2)⊆(k1+k2).

定理11PMC=PMC=P.

定理12SAT∈PMC.

定理13对每一个自然数n≥1，有：

PMC=PMC=P.

定理14 SAT∈PMC.

3 结论与展望

经过20年的发展，膜计算在理论和应用2个方面均取得了重要的进展. 本文仅仅对类细胞型和类组织型通讯膜系统在理论研究方面所取得的成果进行概述[54]. 尽管通讯膜系统已经取得不少的研究成果，但是大多数研究都集中在类组织型通讯膜系统，因此，类细胞型通讯膜系统将是未来的研究重点，作者认为未来的研究可以考虑如下几点：

(1)在膜计算理论研究中，学者们提出了许多的系统运行模式，譬如极小并行模式、串行模式和扁平极大并行模式等，研究类细胞型通讯膜系统在不同运行模式下的计算能力是一个值得考虑的方向.

(2)进化通讯膜系统是最近新提出的计算模型，其研究主要集中在进化通讯类组织型膜系统. 研究进化通讯类细胞型膜系统的计算复杂性将是一个有趣的方向.

(3)另外一个研究方向是将物质在细胞间通讯过程中可以发生进化的思想引入到一些新的模型中，譬如细胞上带蛋白的组织膜系统[16]，带促进剂的组织膜系统等[36]，研究这些新模型的计算能力及计算复杂性问题.