论文部分内容阅读
自然计算是观察自然界中各种生物现象所抽象出来的一个研究领域。近年来,受生物细胞结构和功能的启发,提出了一种新型的分布式生物计算模型—膜计算。在膜计算领域中研究的所有计算模型都统称为膜系统。 在标准膜计算系统中,假设存在一个全局时钟对系统中所有的区域进行计时,并且每条规则的执行时间都是一个单位时间。然而,在活细胞中,化学反应或者复杂的生物操作(细胞分裂、细胞分离等)都需要一定的时间来执行完成;在很多情况下,不同的生物过程需要花不同的时间来完成,这些反应依赖于环境,催化剂等因素。因此,标准膜计算系统中每条规则执行时间都是一个单位时间的假设是不合理的。基于这个生物实际,本文建立了能够克服规则执行时间长短的鲁棒系统,提出了各种时间膜计算系统,研究了这些系统在时间无关模式下求解计算困难问题的能力以及产生数的能力。主要工作包括: 研究了带时间的活性膜膜系统的计算能力,证明了在使用标准分裂规则(分裂生成的新膜标签与它们的父代膜标签相同)且分裂基本膜的情况下,活性膜膜系统可以解决可满足性(简称SAT)问题的时间无关半统一解(一个膜系统只能解决某个具体的例子)。如果系统允许分裂非基本膜,那么该膜系统可以解决SAT问题的时间无关统一解(一个膜系统可以解决一族参数大小相同的例子)。另外,给出了PSPACE完全问题(QSAT)的时间无关半统一解。最后,证明了时间无关活性膜膜系统在不同规则类型组合下都具有计算通用性。 提出了膜上带蛋白的时间膜系统。研究了膜上带蛋白的时间膜系统的计算能力,给出了基于膜上带蛋白膜系统的SAT问题时间无关统一解。证明了在时间无关模式下,该模型可以求解QSAT问题的统一解。本文还证明了时间无关膜上带蛋白膜系统是计算通用的。 提出了膜生成的时间膜系统,研究了膜产生的时间膜系统的计算能力,证明了在时间无关模式下,如果考虑每个膜上都带有一个电荷(或者正电荷或者负电荷或者中性),那么膜产生膜系统可以求解SAT问题的半统一解。另外,通过模拟带出现检测的矩阵文法,证明时间无关无极性膜产生膜系统(每个蛋白质最多只有两种状态)是计算通用的。 考虑将时间概念引入到类组织膜系统中,提出了时间组织膜系统。我们研究带细胞分裂的时间组织膜系统,证明了在时间无关模式下,该模型可以求解子集和问题。本文还证明了时间无关组织膜系统在通讯规则长度不超过3时是计算通用的。 将膜分裂引入到通讯(同向/反向)膜系统中,提出了带膜分裂的通讯膜系统。在标准膜系统模式下研究了带膜分裂的通讯膜系统的计算复杂性问题。通讯规则的长度定义为在该规则中所含物质数目的总和。本文证明了基于膜分裂的通讯膜系统可以解决P类问题如果所有通讯规则的长度不超过1;其次,如果所有通讯规则的长度不超过3,并且只能分裂基本膜的情况下,该膜系统可以在线性时间内求解NP问题(子集和);最后,证明了当所有通讯规则长度不超过3且分裂规则可以是非基本膜时,该膜系统可以有效的求解PSPACE问题(QSAT)。因此,在带膜分裂的通讯膜系统框架下,我们提供了一个界:从通讯规则的长度不超过1到通讯规则长度不超过3对应于从非效率到效率(假设P=NP)。 基于P-Lingua的MeCoSim是一款为用户提供设计、模拟、分析和论证不同类型膜系统的软件。本文设计的一个P-Lingua程序有效的模拟了基于膜分裂和膜分离的通讯膜系统,并分析了该程序用这两类膜系统在求解计算困难问题方面(以SAT问题为例)所耗时长短的原因。