P系统的π@编码及其在系统生物学中的应用

理论计算机科学电子笔记171（2007）171-186www.elsevier.com/locate/entcsπ@中催化P系统的编码克里斯蒂安·维萨里1博洛尼亚大学信息科学学院意大利博洛尼亚摘要P系统是从细胞的生物结构中抽象出来的理论计算设备，它可以通过GheorgheP系统和新的科学方法来产生数据。 在concurre eats y s tem s中，进程演算最近已经被应用并扩展了类似的目的，以模拟（和形式化）细胞的行为。虽然这两种方法之间可以找到许多共同点，但尚未进行正式和详尽的比较。π@是一种新的演算，强烈基于π演算，非常适合轻松编码生物启发的过程演算。本文提出了P系统的一种变体的π@编码，从而更好地理解P系统和生物启发过程演算之间的相似性。关键词：系统生物学，膜计算，催化P系统，过程代数，优先级1引言膜计算（[6]）是自然计算的一个分支，其目的是从自动机和形式语言理论的角度来形式化和研究生物启发的设备- P系统。虽然最初它们并不打算为细胞提供模型，但最近的研究报告了这一方向的许多进展，从而满足了计算机科学研究领域-并发理论-生物学的最新应用的要求。在这些应用中的第一个（[10]）生物实体（分子，酶等）在π演算中被建模为进程和路径，作为进程间通信的序列。虽然π-演算非常适合于模拟生物元素的移动性和相互作用，但它缺乏对隔室概念的明确表达。随后的方法（如[9，8，2]）添加了这个概念，试图保留并发性和移动性功能：隔室成为BioAmbients中的环境，BetaBinders中的尽管这些语言在细胞生物学的各个方面都有所不同，1电子邮件地址：versari@cs.unibo.it1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2007.05.015172C. Versari/Electronic Notes in Theoretical Computer Science 171（2007）171由于这种隔室的想法，共同的方面：在同一隔室内的相互作用的本地化，复杂操作的原子性，不同隔室之间的大规模对象运动。即使P系统来自一个非常不同的计算机科学分支，它们也呈现出许多与这些进程演算相似的方面- 并发/分布、非确定性、交互、移动性、分隔--这些使得比较非常有趣。执行这种比较的一种方法是用同一种语言对它们进行π @是一种保守的，基于强π演算的语言，具有两个关键特性：多元同步（通道的结构化名称）以表示分隔，以及优先级以实现复杂的质量移动操作的 原 子 性 。 这 些 特 征 允 许 对 生 物 启 发 的 结 石 （ 如 Bioambients 和 BraneCalculi）进行简单的π@编码（[11]），目的是显示它们的共同特征。为了同样的目的，我们现在提出了一种简单的P系统的编码，通过利用π@的关键特征来克服膜系统和进程代数之间的显著差异（首先是最大并行性），从而提出π@作为一种新的核心演算，适合于编码和比较各种生物启发的形式主义。本文的结构如下：第2节回顾了催化P系统的基本定义，第3节介绍了π@，并举例说明;第4节逐步给出了催化P系统π第5节提出了一些最终意见2神经膜系统引用自[7]：“The膜的概念背后的直觉是来自生物学的三维囊泡，但概念本身被推广/理想化，以将膜解释为两个区域的分隔器（欧几里得空间），内部无限和外部无限，也提供了两个区域之间选择性通信的可能性。来自生物学的各种建议以及定义基于膜的多集处理设备的架构和功能的可能性范围实际上是无穷无尽的大量的P系统模型迫使选择最相似的过程结石和最初更容易编码：催化P系统已被选择为简单的进化规则和静态结构的膜树。下面，回顾初步定义，然后给出催化P系统的正式定义。定义2.1给定一个集合S，S上的有限多重集是一个函数m：S→IN，C. Versari/Electronic Notes in Theoretical Computer Science 171（2007）171173设dom（m）={s∈S|m（s）/= 0}是有限的。m中元素s的重数由自然数m（s）给出。S上的所有有限多重集的集合，记为Mfin（S），被m包围。一个多集m使得dom（m）=m称为空集。空的多重集用表示。给定多重集m和MJ，如果对所有s∈S，m（s）≤MJ（s），则m<$mj成立，m表示它们的多集并：m<$mJ（s）=m（s）+mJ（s）。运算符\表示多集差异：（m\mJ）（s）=如果m（s）≥mJ（s）则m（s）−mJ（s）else 0。数j与m的标积j·m为（j·m）（s）=j·（m（s））。基数一个multiset是包含在multiset中的元素的出现次数Σ|= s ∈ Sm（s）.|=s∈S m(s).然后给出了弦、卡氏积和关系的一些基本定义定义2.2S上的弦是S中元素的有限（可能为空）序列。字符串的长度是S中包含的元素出现的次数。我 们 用S表示S 上的弦的集合，u，v，w，.。 范围超过S。给定一个字符串u = x1. xn，对应于u的多重集定义如下：对于所有s∈S，mu（s）=|{我|xi= s<$1 ≤i≤n}|.由于符号的滥用，我们也用u来表示mu。膜结构的定义如下。定义2.3给定字母表V={[，]}，集合MS是由以下规则归纳定义的最小集合：• [ ] ∈MS• 如果μ1，μ2，.，μn∈MS，n≥1，则[μ1.μn]∈MS我们定义MS上的以下关系：x =y当且仅当两个字符串可以写成x=[1. [2. . 2. [3. . ] 3. . ]1和y=[1. [3. . 3. [2. . ] 2. . ]1（即，如果相邻的两对括号可以与它们的内容一起交换）。膜结构的集合MS被定义为等价类的集合w.r.t. 的关系。我们称一个膜为每对出现在双膜结构中的括号。膜结构μ可以表示为维恩图，其中任何封闭空间（由膜和内部的膜限定）称为μ的区域。定义2.4催化P系统（度为d，d≥1）是一个构造V =（V，C，μ，w0，.，w0，R1，.，Rd，i0）1个d哪里(i) V是一个有限的字母表，其元素被称为对象;(ii) C++V是一组催化剂;174C. Versari/Electronic Notes in Theoretical Computer Science 171（2007）171我(iii) μ是由d个膜组成的膜结构（通常标记为i并且由对应的括号[i和]i表示，其中1≤i≤d）;(iv) w0，1≤i≤d，是V上与区域1，2，.，d;它们表示存在于μ的区域中的对象的多个集合（区域中的符号的多重性由该符号在对应于该区域的字符串中的出现次数给出）;(v) Ri，1 ≤i≤d，是与区域1，2，.这些演化规则的形式为a→v或ca→cv，其中c是催化剂，a是来自V\C的对象，v是来自（（V\C）× {here，out，in}）n的字符串;(vi) i0是一个介于1和d之间的数字，它指定了输出膜。3π@语言π@演算-发音像法语的“pailette”-本质上是π演算，增加了两个多元同步在π演算中，通道和名称通常是同义词。多元同步（[1]）在通道中引入了一种结构：它们由一个或多个名称的向量表示然后通过采用由两部分组成的通道一个常见的例子是电子邮件地址的表示：user@domain是一个由两个名称组成的通道Polyadic语法在π@中以完全相同的方式表示：通道中的名称由字符“@”分隔。因此，隔室组件中通道名称chan上的基准面d的通信通常以π@书写为chan@companyjiang.P.. chan @ comp（x）.Q→P.. Q {d/x}其中第一个进程发送d，然后成为进程P，而第二个进程接收d，并执行Q中指定的动作。在π@语义中，两个进程之间的交互只有在输入/输出操作中涉及的通道由相同数量的名称组成时才可能发生，具有相同的多重性和相同的顺序。因此，我们x@y.P... y @ x（）.Q~（xy）x.P . x@ x（）.Q~因为通道x@y不同于y@x，并且x不同于x@x。C. Versari/Electronic Notes in Theoretical Computer Science 171（2007）171175优先优先级的行为符合预期：高优先级进程拥有中央处理单元，并在任何低优先级进程之前执行其作业。在π@中，高优先级同步或通信在任何其他低优先级动作之前执行。通常，高优先级操作通过在通道名称上加下划线一次或多次来表示。例如表述..StandP. 走得很慢。运行时间包含三个具有不同优先级的进程。为了表示三个以上的优先级，使用了另一种表示法，其中进程的优先级由通道名称后面的数字表示。上面的表达式可以重写为..展位：2个展位，展位号：2000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000walk：1000m.Q. 运行：0z其中较低优先级的动作用较高的数字标记（最高优先级由0表示）。只有当通道具有相同的优先级时，才可能发生进程之间的交互在该示例xy.Pxy.P.. x（z）.Q~.. x（z）.Q→P.. Q {y/z}因为表达式x和x实际上表示两个不同的信道，所以只允许第二交互。最后，正如预期的那样，低优先级操作仅在没有更高优先级操作可能发生时发生：...lw . l（x）.P.. 好的。 h（z）.Q~..0的情况。P{w/x}。好的。 h（z）.Q...我在看。l（x）.P. 好的。 h（z）.Q→...lw . l（x）.P.. 0的情况。 Q{y/z} →..0的情况。P{w/x}。0的情况。 Q{y/z}低优先级信道l上的交互可能仅在信道h上的高优先级通信之后发生。在下一节中，我们简要回顾了π-演算的语法和归约语义，然后在3.2中给出了导致π@3.1π-微积分定义3.1Let176C. Versari/Electronic Notes in Theoretical Computer Science 171（2007）171N是一组有限字母表上的名字，x，y，z，. ∈ N;C. Versari/Electronic Notes in Theoretical Computer Science 171（2007）171177...N ={x|x∈ N}π-演算的语法定义为.P：：=0。Σ π.P..P. Q..！P..（νx）Pπ：：=τ..i ∈I.x（y）一 .....xy定义3.2同余关系ε被定义为最小同余s。实现阿尔法转换，交换monoidal法律关于这两个（。、0）的和（+，0）以及以下公理：（νx）P.. Q（νx）（P.. Q）ifx∈/fn（Q）;（νx）P<$Pifx∈/fn（P）.！P ！P其中函数fn定义为fn（τ）fn （ x（ y ））fn（ xy ）fn（0）fn（π.P）. Pdef=def={x}def={x，y}def=def=fn（π）<$fn（P）Escherdef吴晓波（i∈Iπi.Pi）.=defifn（πi.Pi）fn（P.Q）=fn（P）<$fn（Q）deffn（！P）fn（（νx）P）=fn（P）def=fn（P）\{x}178C. Versari/Electronic Notes in Theoretical Computer Science 171（2007）171定义3.3π-演算的语义是根据以下规则描述的归约系统给出的：τ.P→PP→PJ（ν x）P→（νx）PJ..（μ（y）.P + M）。（μ<$z<$.Q + N）→P{z/y}。 QP→PJ.J.P<$Q P→PJPJ<$QJJP. Q → P. QQ →Q见[4]为一个exaustive介绍π演算。C. Versari/Electronic Notes in Theoretical Computer Science 171（2007）171179...3.2π@语法和语义π@非常接近pi-演算：从语法的角度来看，唯一的区别是通道的结构，由多个名称后跟优先级组成。的行动。 我们用μ来表示一个向量的名称x1，. .. 通常，μ：k表示沿通道μ：k的输出操作，而α：k表示优先级为k的通用输入、输出或静默操作τ。定义3.4LetN是一组有限字母表上的名字，x，y，z，. ∈ N;N+=i>0Ni，μ∈ N+;N+={μ|n∈ N+};. +的α∈ NN+Σ{τ};π@的语法定义为.P：：=0。Σ π.P..P. Q..！P..（νx）P.一 ....i∈I。π：：=τ：k.μ：k（x） 。μ：kx如前所述，本文中经常使用一些缩写：μ（x）=μ：2（x）μx=μ：2 xμ（x）=μ：1（x）μx=μ：1 xμ（x）=μ：0（x）μx=μ：0 x结构同余的定义与π-演算的定义完全相同，其中函数fn自然地扩展到π@语法。reduction的语义非常相似，但是根据辅助函数Ik（P）来定义，表示进程P可以立即执行的优先级为k的动作集合。例如如果....P=a.Q。B. C.R. d+e.S. a .T则I0（P）={c，e}，I1（P）={b，d}，I2（P）={a，a，τ}，其中τ行动来自第一个和最后一个过程的相互作用。180C. Versari/Electronic Notes in Theoretical Computer Science 171（2007）171我我I k定义3.5设Ik（P）为我... Pα={α| intn= k};我.Σ（ν y）P=Ik （P）\.α |y ∈ {x1，.，xn}ΣK.Σ（α = x1 @. @ xnα = x1 @. @ xn）;K.我 ！PK..Σ= I（P. P）;k k kkIP. Q=I（P）<$I（Q）<${τ |I（P）I（Q）}，K.k与我 （Q）=α |α∈I（Q）π@语义根据以下归约系统给出τ∈/Ii（M）τ：k.P+M→kPP→kPJ（ν x）P→k（νx）PJ.我τ∈/.i kI（M . N）的范围.（μ：k（y）.P + M）。 （μ：k<$z<$.Q + N）→kP {z/y}. Q吉岛J J JcP →kP。τ∈/i

下载后可阅读完整内容，剩余1页未读，立即下载