带通道状态通讯膜系统的研究综述

宋勃升， 李艳艳， 曾湘祥

(湖南大学 信息科学与工程学院, 湖南 长沙 410082)

在生物启发式计算或者自然计算的领域内，存在一个快速发展的分支：膜计算，由欧洲科学院院士Păun[1]于1998 年在芬兰图尔库计算机科学中心访学时首次提出，它是从活细胞的组织和器官的结构以及功能中抽象出来的. 膜系统(又称为P系统)是膜计算研究中计算模型的统称，它们是分布式和并行计算设备. 根据活细胞内部的真实膜结构，许多类型的膜系统已经被提出[2-5]，主要有两类P系统：细胞型P系统[1,4](一个细胞中的膜是以一个层次结构排列)和组织型P系统[4,6]，或者神经型P系统[7](如一个组织或一个神经网络置于任意图节点中的膜结构). 根据生物活细胞具有不同的生物特征，研究者们又提出了许多新型的膜系统，例如，带催化剂的膜系统[8]、带促进剂/抑制剂的膜系统[9]和剪切膜系统[10]等.

膜计算的研究课题主要聚焦在理论分析和现实生活问题的应用上. 一方面，随着各种P系统的引入，许多不同种类P系统的计算能力以及计算复杂性已经被深入地研究[11-15]. 结合计算机科学中的基本概念，在理论推导中，学者们设计了各种不同的规则执行方式，例如，串行模式[16]、极小并行模式[17]、极大并行模式[18]和扁平极大并行模式[19]. 在理论分析方面，主要通过与图灵机比较来证明多数膜系统是具有图灵完备性的，即这些P系统的计算能力与通用图灵机等价[20-24]. 同时，受细胞膜的分离、分裂以及生成等生物活动的启发，膜系统中存在细胞分离[1](1)Sosík P, Cienciala L. Computational power of cell separation in tissue P systems[J]. Information Sciences, 2014, 279: 805-815.、 细胞分裂[25]以及细胞生成[26]等规则，通过这些规则的使用，细胞可以生成指数多个细胞，通过以空间换取时间的方式有效地求解NP完全问题[27-29]以及PSPACE完全问题[30-34]. 另一方面，研究膜计算的实际应用也非常有趣[35-37]，例如，P系统可以应用到生物系统和合成生物学[38]中，可以改进人工智能算法[39-43]，还可以用于电路系统的设计以及生态系统的建模[44-45]. 关于P系统的详细信息，读者可以查阅文献[46]. 更详尽的细节以及最新的参考资料可以在网址http://ppage.psystems.eu 上找到.

通讯P系统是一类受活细胞中物质跨膜移动的生物现象启发而得来的膜系统，最早提出来是在文献[47]中. 这类P 系统是一类通过使用同向/异向转运规则代替进化规则的计算模型，其中,同向转运规则的形式是(u,in) 或者(u,out)，异向转运规则的形式是(u,out;v,in). 该类P系统的计算理论研究广泛，比如计算能力[48-50]，计算有效性[51]和生成语言的能力[52].

膜计算中有一类通讯P系统被提出并且得到了深入的研究，这里称为带有通道状态的通讯P系统，其中，通道上的状态用来控制细胞间的通讯以及细胞与环境间的通讯. 对于通讯，如果从不同的角度来看，那么会有两种情况：其一，细胞间会有与状态相关的链接，并且细胞会使用这些状态来控制细胞间的通讯；其二， 通讯的完成通过同向/异向规则的使用. 本文主要围绕着带有通道状态的通讯P 系统.首先，对带有通道状态的细胞型通讯P系统，带有通道状态的组织型通讯P系统以及带有通道状态的识别通讯P系统的基本概念进行了简单的介绍；其次，对这两类通讯P系统的计算能力和计算复杂性分别进行了概述；最后，给出了对这类通讯P 系统的总结以及对未来的展望.

1 带有通道状态通讯膜系统的基本概念

本节主要介绍带有通道状态的细胞型和组织型通讯P系统的概念，模型中涉及有关形式语言的知识，读者可以参考文献[53].

1.1 带有通道状态的通讯膜系统

带有通道状态的细胞型通讯膜系统是由Song等[54]首次提出的，该模型使用的是带有通道状态的同向/异向转运规则，且规则以极大并行的方式执行，具体概念如下.

定义1一个度为q≥1的带有通道状态的细胞型通讯膜系统是一个元组

Π=(Γ,K,ε,μ,1,…,q,s1,…,sq,1,…,q,iout),

其中：

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

•K是一个状态字母表(与Γ的交集为空)；

•μ是一个含有q个节点的根树，用1,…,q来标记；

•si(1≤i≤q)是通道状态；

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

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

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

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

笔者注意到一个非常重要的限制是两个相邻区域之间最多一个通道，每个步骤的状态都来自于K. 这个不会限制相邻区域间的通讯，因为一个通道的两个方向上都允许物质的移动.

如果膜i和它的父区域p(i)之间的通道状态为s，且膜i中包含多重集合u，那么此时在格局中应用一条同向规则(s,(u,out),s′). 当这样一条同向转运规则被应用时，多重集合u被发送到区域p(i)，且区域i和区域p(i)之间的通道状态从s变为s′.

如果膜i和它的父区域p(i)之间的通道状态为s，且区域p(i)中包含多重集合u，那么此时在一个格局中应用一条同向转运规则(s,(u,out),s′). 当这样一条规则被应用时，多重集合u将从区域p(i) 进入膜i中，且区域i与区域p(i)之间的通道状态由s变为s′.

如果膜i和它的父区域p(i)之间的通道状态为s，且膜i中包含多重集合u，同时膜i的父区域中包含多重集合v，那么此时在一个格局中应用一条反向转运规则(s,(u,out;v,in),s′). 当使用这样一条规则时，多重集合u从膜i发送到区域p(i)，同时，多重集合v从区域p(i)发送到膜i，且区域i与区域p(i)之间的通道状态由s变为s′.

已经证明了该类型P系统具有图灵通用性. 除此之外，学者们还提出了具有细胞分裂的带有通道状态的细胞型P 系统[55]，同样已经证明具有图灵通用性，且此类型膜系统还可以解决哈密顿回路问题.

带有通道状态的组织型通讯P系统是由Freund等[56]首次提出的，该模型使用的是带有通道状态的同向/异向转运规则，且规则以极大并行的方式执行，具体概念如下.

定义2一个度为q≥1的带通道状态的组织型通讯膜系统是一个元组

Π=(Γ,T,K,ε,1,…,q,ch,(s(i,j))(i,j)∈ch,(R(i,j))(i,j)∈ch,,iout),

其中：

•Γ是一个有限字母；

•T⊆Γ是一个结束物质的字母表；

•K是一个状态的字母表；

•ε⊆Γ是初始时刻位于环境中的物质集合，所有可用的物质都有任意多的数量；

•ch⊆{(i,j)|i,j∈{0,…,q},i≠j}是细胞间通道或细胞与环境间通道的集合，在ch中最多出现(i,j)，(j,i)其中之一(0标记环境)；

•R(i,j)是具有如下形式的有限规则集合(与通道(i,j)∈ch有关)：

- 同向规则：(s,u/λ,s′)，s,s′∈K，u∈Γ+；

- 异向规则：(s,u/v,s′)，s,s′∈K，u,v∈Γ+，|u|>0，|v|>0；

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

笔者注意到一个重要的限制是两个已给细胞之间最多存在一条通道，通道以有序对(i,j)的形式给出，并且通道上有来自于K的状态. 这个不会限制两个细胞间或者细胞和环境之间的通讯，因为通道上的两个方向都允许物质的移动. 规则(s,u/λ,s′)、(s,λ/u,s′) 或者(s,u/v,s′)的长度分别为|u|和|u|+|v|.

如果区域i和区域j之间通道的状态为s，且区域i包含对象的多重集合u，(或者区域j包含对象的多重集合u)，那么此时在一个格局中使用同向规则(s,u/λ,s′)∈Ri,j(或(s,λ/u,s′)∈Ri,j). 当使用这样的规则时，多重集合u被发送到区域j(或者区域i)，且区域i和区域j之间的通道状态由s变为s′.

如果区域i和区域j之间通道的状态为s，且区域i包含对象的多重集合u，同时区域j包含对象的多重集合v，那么此时在一个格局中使用异向规则(s,u/v,s′)∈Ri,j. 当使用这样的规则时，多重集合u将从区域i发送到区域j，多重集合v将从区域j发送到区域i，且区域i和区域j之间的通道状态由s变为s′.

已经证明该系统具有图灵通用性. 除此之外，学者们还提出了带有细胞分裂的带通道状态的组织型通讯P 系统，单向[57-59]带有细胞分裂带通道状态的组织型通讯P系统[60]，它们不仅具有图灵通用性，而且可以解决NP完全问题.

下面将介绍带有细胞分裂和通道状态的通讯P系统以及相应的识别P系统的基本概念.

1.2 带细胞分裂和通道状态的通讯膜系统

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

Π=(Γ,K,ε,μ,1,…,q,s1,…,sq,1,…,q,iout),

其中：

•Γ是一个物质(或符号)的字母表，又称为一个有限非空集合；

•K是一个通道状态的字母表，表示一个有限非空集合且Γ∩K=∅；

•ε是Γ的一个子集，代表初始位于Π环境中的物质集合；

•μ是一个由1,…,q标记的有q个节点的根树，表示这个系统的框架；

•si，1≤i≤q是K上的通道状态，它们代表每个区域的初始状态；

•Ri，1≤i≤q是每个区域i中规则的有限集，有下述的形式：

- 通讯规则：

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

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

- 分裂规则：[a]i→[b]i[c]i，a,b,c∈Γ，i∈{2,…,q}，i≠iout.

•iout∈{0,1,…,q}是输出区域.

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

Π=(Γ,T,K,ε,1,…,q,ch,(s(i,j))(i,j)∈ch,(R(i,j))(i,j)∈ch,iout),

其中：

•Γ是一个有限字母；

•T⊆Γ是一个终止字母表；

•K是一个状态的字母表；

•ε⊆Γ是初始时刻位于环境中的物质集合，所有可用的物质都有任意多的数量；

•ch⊆{(i,j)|i,j∈{0,…,q},i≠j}是细胞间通道或细胞与环境间通道的集合;

•R(i,j)是具有如下形式的有限规则集合(与通道(i,j)∈ch有关)：

- 通讯规则：

- 同向规则：(s,u/λ,s′)，s,s′∈K，u∈Γ+；

- 异向规则：(s,u/v,s′)，s,s′∈K，u,v∈Γ+，|u|>0，|v|>0；

- 分裂规则：

- [a]i→[b]i[c]i，a,b,c∈Γ，i∈{1,…,q}，i≠iout；

•iout∈{0,1,…,q}是输出区域.

1.3 带细胞分裂和通道状态的识别通讯膜系统

定义5一个度为q≥1的带有细胞分裂和通道状态的细胞型识别通讯膜系统是一个元组

Π=(Γ,K,ε,μ,∑,1,…,q,s1,…,sq,1,…,q,iin,iout),

其中：

•(Γ,K,ε,μ,∑,1,…,q,s1,…,sq,1,…,q,iout) 是一个度q≥1的带有细胞分裂和通道状态的细胞型通讯膜系统；

•Γ有两个不同的物质yes和no；

•∑是一个严格包含于Γ中的输入字母表，使得ε⊆Γ∑；

•iin∈{1,…,q}是输入细胞，且iout=0；

•所有的计算停止；

在这个系统中，规则的集合中包含细胞分裂规则，即可以产生2n个细胞，由此可见这个系统可以采用空间换时间的方式来解决HPP问题.

定义6一个度为q≥1的带有细胞分裂和通道状态的组织型识别通讯膜系统是一个元组

Π=(Γ,T,K,∑,ε,1,…,q,ch,(s(i,j))(i,j)∈ch,(R(i,j))(i,j)∈ch,iin,iout),

其中：

•(Γ,T,K,∑,ε,1,…,q,ch,(s(i,j))(i,j)∈ch,(R(i,j))(i,j)∈ch,iout) 是一个度q≥1的带有细胞分裂和通道状态的组织型通讯膜系统；

•Γ有两个不同的物质yes和no；

•∑是一个严格包含于Γ中的输入字母表；

•iin∈{1,…,q}是输入细胞，且iout=0；

•所有的计算停止；

在这个系统中，规则的集合中包含细胞分裂规则，即可以产生2n个细胞，由此可见这个系统可以采取空间换时间的方式来解决SAT问题.

对于带有细胞分裂和通道状态的识别通讯膜系统来说，如果物质yes出现在与计算停止状态相关的环境中，且在计算的非停止状态中没有出现物质yes和no，那么就称计算为一个接受计算，否则，就称计算为拒绝计算.

2 带通道状态通讯膜系统的计算能力和计算复杂性

本节首先介绍带有细胞分裂和通道状态的通讯P系统求解判定性问题的概念，然后再分析这些膜系统的计算能力，最后给出这些膜系统的计算复杂性.

接下来，根据文献[61]，笔者定义用同向/异向规则的带有细胞分裂和通道状态的识别通讯膜系统在统一模式下求解判定性问题.

定义7在多项式时间内可以由一族带有细胞分裂和通道状态的识别通讯膜系统∏={Π(n)|n∈}以一种统一的模式解决一个判定性问题X=(IX,θX)，如果满足下述的条件：

•一族∏是通过图灵机在多项式时间内统一的，也就是说存在一个多项式时间内工作的确定性图灵机，且这个确定性图灵机可以构建系统Π(n)(n∈)；

•在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.1 带有通道状态的通讯膜系统的计算能力

本小节首先介绍带有通道状态的类细胞或类组织通讯膜系统的计算能力，然后再分别介绍了带有细胞分裂和通道状态的类细胞或类组织通讯膜系统的计算复杂性问题.

在介绍定理之前，首先给出各种符号的含义. 一般，NFIN表示正整数所有有限集的族，NMAT表示无外观检测矩阵文法产生的正整数集合的族，NRE表示自然数递归可枚举集的族.

根据文献[54-55]，对于带有通道状态的细胞型通讯膜系统，笔者有如下的定理展现其计算能力.

定理1根据文献[54]，对于带有通道状态，使用同向/异向规则的细胞型通讯膜系统来说，其具有如下的计算能力，其中，NOPm(statek,symt1,antit2)表示该类膜系统计算的所有数字集合的族，且该类膜系统有m个膜，k个状态，以及使用规则长度最长为t1的同向规则和规则长度最长为t2的异向规则. 如果在膜系统中只使用了同向规则(或者异向规则)，那么由膜系统计算得来的所有数字集合的族简单地记为NOPm(statek,symt1)(或者NOPm(statek,antit2)).如果参数m,k,t1,t2没有限制，那么它们可以用*来代替.

•NOP*(state*,anti2)⊆NFIN；

•NOP*(state2,sym1)⊆NFIN；

•NOP1(state1,anti4)=NOP1(state*,sym1,anti2) =NMAT；

•NOP2(state*,sym1)=NRE；

•NOP2(state4,anti2)=NRE；

•NOP2(state2,anti3)=NRE；

•NOP2(state1,anti3)=NRE；

•NOP2(state3,sym1,anti2) =NRE.

定理2根据文献[55]，对于带有通道状态，使用协同同向规则，工作在扁平极大并行模式的细胞型通讯膜系统来说，其具有如下的计算能力，其中，NOPm(statek,symt,flat)表示由m个膜，k个状态，只使用规则长度最长为t的同向规则组成且以扁平极大并行方式工作的膜系统计算的所有自然数集合的族. 如果参数m,k,t没有限制，那么它们可以用*来代替.

•NOP2(state*,sym1,flat)=NOP2(state4,sym2,flat)=NOP2(state2,sym3,flat)=NRE；

•NOP1(state1,sym3,flat)=NRE；

•NOP1(state*,sym2,flat)=NRE；

•NOP2(state3,sym2,flat)=NRE.

定理3根据文献[56]，对于带有通道状态的组织型通讯膜系统来说，其具有如下的计算能力. 一般来说，系统Π计算得来的所有向量的集合使用Ps(Π)来表示.PsOtpm(statek,antii)表示系统计算的向量集合Ps(Π)的族，其中这个系统有m个细胞，k个状态，使用形式为(s,x/y,s′)的规则，|x|≤i，|y|≤i. 当参数m,k,i没有限制时，可以使用*来代替.MAT表示矩阵文法生成的语言族且PsCF⊂PsMAT⊂PsRE.

•PsMAT⊆PsOtp1(state*,anti1)；

•PsMAT⊆PsOtp1(state1,anti2)；

•PsOtp1(state*,anti*)⊆PsMAT；

•PsMAT=PsOtp1(statek,antii)=PsOtp1(state*,antij)，k≥1，i≥2，j≥1，每个k,i,j也可以等于*；

•PsRE=PsOtpm(state*,antii)，m≥2，i≥1；

•PsRE=PsOtpm(statek,antii)，m≥2，k≥1，i≥2；

•PsRE=PsOtp*(statek,antii)，k≥3，i≥1.

定理4根据文献[59]，对于带有通道状态，工作在扁平极大并行模式下的组织型通讯膜系统来说，其具有如下的计算能力. 系统Π计算得来的所有向量的集合使用Ps(Π)来表示.PsOtpm(statek,symt1,antit2,flat)表示系统计算的向量集合的族，其中，这个系统有m个细胞，k个状态，使用规则长度最长为t1的同向规则和规则长度最长为t2的异向规则，flat表示通道上的规则以扁平极大并行的方式使用. 当参数m,k,i没有限制时，可以使用*来代替.

•PsOtp*(state*,anti2,flat)⊆PsFIN；

•PsOtp1(state1,sym3,flat)=PsRE；

•PsOtp2(state*,sym1,flat)=PsRE；

•PsOtp*(state4,sym1,flat)=PsRE.

•NOtP2m(state*,sym1)=NRE；

•NOtP2m(state4,sym2)=NRE；

•NOtP*m(state5,sym1)=NRE.

2.2 带有细胞分裂和通道状态的通讯膜系统的计算复杂性

定理6 根据文献[55]，带有细胞分裂和通道状态的细胞型通讯膜系统可以解决哈密顿回路问题，其计算复杂性如下，CCDeP(k)表示一类带有细胞分裂和通道状态，通讯规则长度最长为k的细胞型通讯膜系统，PMCCCDeP(k)表示由CCDeP(k)在多项式时间内解决的所有判定性问题的集合.

•HPP∈PMCCCDeP(1)；

•NP∪co-NP⊆PMCCCDeP(1).

定理7根据文献[59]，带有细胞分裂和通道状态，工作在扁平极大并行模式下的组织型通讯膜系统可以解决SAT问题，其计算复杂性如下，PMCTSDC(k)来表示由带有细胞分裂和通道状态，通讯规则长度最长为k的组织型识别通讯膜系统在多项式时间内以统一的方式解决的所有判定性问题的集合.

3 结论与展望

本文主要介绍了带有通道状态的通讯膜系统，包括带有通道状态的细胞型通讯膜系统和带有通道状态的组织型通讯膜系统. 本文首先分别对这两类膜系统的基本概念做了简要的介绍；其次分别介绍了带有通道状态的通讯膜系统的一些变形：带细胞分裂和通道状态的组织型识别通讯膜系统，带细胞分裂和通道状态的组织型通讯膜系统，带细胞分裂和通道状态的细胞型识别通讯膜系统，以及带细胞分裂和通道状态的组织型通讯膜系统. 对于这些膜系统，它们具有解决判定性问题的能力，本文分析了这些模型的计算能力和计算复杂性. 至今为止，膜计算作为自然计算中的一个分支，仍然是一个冉冉新生的计算模型，对于带通道状态的通讯膜系统来说，存在如下待解决的问题，且这些问题值得思考，具体如下.

(1)以串行方式工作的带通道状态，使用同向/异向规则的细胞型P系统已经在文献[52]中得以研究；以扁平极大并行方式工作，带有通道状态的通讯P 系统的通用性也得到了研究，在这项工作中同时获得了NP完全问题的一个解. 然而值得关注的是在一些其他的操作策略中，如异步模式，无时间模式[62-64]，或者集合推导模式[65]下带有细胞分裂和通道状态的P系统的计算能力或者计算效率.

(2)可以将膜分离(或裂变)作为一种生物现象纳入P系统中，它能够在多项式时间内产生大量的新细胞为计算提供一个指数级的工作空间，因此，有膜分离的各种形式的P系统可以解决NP完全问题[66-67]. 在文献[68]中，HPP问题可以由工作在极大并行模式，有活性膜和分离规则的P系统解决，然而，HPP 问题是否能由带细胞分离和通道状态的通讯P系统来解决值得思考.

(3)由于PSPACE问题，如QSAT问题可以由带有非基本膜分裂，使用通讯规则(同向/异向规则)的P系统高效地解决[30]. 因此，假设带有非基本膜分裂和通道状态的通讯P 系统也可以解决PSPACE问题，而如何解决仍然有待于思考.

(4)对于带通道状态的组织型通讯P系统来说，研究其工作在扁平极大并行模式下，且使用细胞分离规则的系统的计算能力和计算复杂性是一个有待于被解决的问题；

(5)依据各种生物活动特性，研究者们提出了串行模式、极小并行模式、极大并行模式以及扁平极大并行模式. 对于带有通道状态的通讯P系统来说，分别研究其在不同模式下的计算能力和计算复杂性是一个有待于解决的问题.