膜演算：P系统和Brane演算的连接及通信模型构建

理论计算机科学电子笔记171（2007）187-196www.elsevier.com/locate/entcs膜演算Giancarlo Mauri2米兰比科卡大学信息、系统和通信系Via Bicocca degli Arcimboldi 8，20126米兰，意大利摘要P系统和Brane演算是两个受活细胞结构和功能启发的计算模型。虽然他们有不同的目标，但最近对连接这两个研究领域的结果越来越感兴趣在这里，我们考虑一种重要的通信基于移动膜的自然出芽（例如，高尔基体），已经为P系统定义，我们展示了如何构建一个类似的Phago/Exo/Pino Brane演算中的通信。关键词：膜计算，膜演算，系统生物学，芽P系统1介绍P系统[6]和Brane演算[4]都被引入作为受活细胞的结构和功能启发的计算模型（家族），从关键观察开始，即在活细胞中发生的各种过程虽然它们有共同的基础，但它们有不同的目标：P系统研究领域的主要目标为了更好地阐明不同的目标，我们引用[5]：“虽然膜计算（即，P系统）是自然计算的一个分支，它试图从结构中1电子邮件地址：vitale@disco.unimib.it2电子邮件地址：mauri@disco.unimib.it1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2007.05.016188A. 维塔莱湾，澳-地Mauri/Electronic Notes in Theoretical Computer Science 171和细胞的功能，特别是利用自动机，语言和复杂性理论工具，Brane演算更加关注生物现实的真实性，将系统生物学作为主要目标，特别是使用进程代数的框架。在P系统中，细胞组织由嵌套膜的维恩图形式化的膜结构模拟，而在由隔室限定的溶液中游动的化学物质多重集的概念完美地模拟了化学物质的无序结构。在P系统的基本变体中，对象根据局部地与隔间相关联的进化规则进化，该规则将多组符号转换为多组符号。通过允许进化规则在直接嵌套的膜之间移动物体来实现隔室之间的相互作用这样的规则通常以最大程度的并行方式非确定地应用：要使用的规则和要进化的对象是随机选择的，并且在每一步中，所有可以进化的对象都必须这样做。虽然在膜结石中我们也有膜结构，但膜并不像P系统那样是简单的分隔物，而是主要活性的协调者和活性位点在Brane演算中，计算发生在超膜，而不是在超膜内部因此，我们不再使用多组对象，而是使用驻留在膜上的过程。[4]中提出的两种基本膜结石的操作直接受到生物过程如内吞作用、胞吐作用和有丝分裂的启发。与P系统的另一个不同之处是，通常Brane演算使用交错语义（顺序单指令执行）进行进化。直到最近，P系统才被应用于模拟生物系统和过程（特别是在细胞水平）。这两种形式主义的共同背景和最近对P系统的兴趣转向系统生物学提出了自然的问题，桥接两个研究领域。已经取得了各种正式成果。文[3]研究了文[4]中提出的两种基本Brane演算在[5]中检查了P系统的一个变体，该变体受到[4]中定义的基本Brane演算的相互作用的启发受P系统的最大并行语义的启发，文献[2]给出最后，在[7]中，研究了P系统的两个变体，它们的相互作用受到[4本文不调查正式的属性，如计算能力或复杂性，并应被视为一个（简单的）测试的表达能力和可用性的生物建模目的的膜演算具体地说，我们考虑了一种特殊的通信，这种通信基于细胞中移动囊泡/膜的自然出芽，这种通信已经在具有移动膜出芽的P系统中定义[1]，我们展示了如何以简单而优雅的方式在基本的Phago/Exo/Pino Brane演算中建模类似的A. 维塔莱湾，澳-地Mauri/Electronic Notes in Theoretical Computer Science 171189本文的其余部分组织如下。在第2节中，我们介绍了本文其余部分所需的所有形式概念。在第3节中，我们展示了如何用Phago/Exo/Pino动作来建模移动膜通信。在第4节中，我们报告了一些最后的评论，并对未来的工作提出了一些看法。2预赛我们使用的形式语言理论的概念是基本的，可以在这一领域的每一本专著中找到（例如，[8]）。生物膜在活细胞中的关键功能是定义一个复合体及其与周围环境（包括其他隔室）的相互作用。在P系统和Brane演算中，我们都有一个膜结构，其中膜的概念被用作过程和资源之间的逻辑分离器。膜结构可以被看作是一个树状结构，一个维恩图或一个正确匹配的括号串，应该清楚的是，我们可以有嵌套的膜结构;每对匹配的括号识别一个膜。树的高度决定了结构的深度一个系统最外层的膜称为皮膜，不含其他膜的皮膜称为基本膜。由膜定义的空间称为区域或隔室。生物膜包含各种物质，我们使用多集的概念来形式化它们。 集合X上的多重集合W是映射W：X→N，并且可以用字符串表示（例如，a3bc2=abacac=baccaa=. ）.多集数据结构使我们可以直接形式化的多重性和无序结构的化学品。2.1Gemmating P系统一般来说，P系统是基于膜结构3的计算模型，其以并行和分布式方式局部处理多组符号。每一个膜都标识了一个隔间（或区域），其中包含一组进化规则和来自给定字母表的多组符号。给定一个隔间，所包含的符号根据所包含的一组规则演变通常以非确定性的、最大程度并行的方式使用规则;在计算的每个步骤，我们非确定性地选择规则和对象（符号），直到不能做出进一步的选择，然后同时将所选择的规则应用于所选择的符号。如果计算停止，则计算是成功的，定义输出的一种简单方法是考虑预定义隔室中的对象数量 存在基本模型的许多变体，并且可以在网址www.example.com上找到最新的参考书目http://psystems.disco.unimib.it/。具有可移动膜的萌发的P系统（brie-gemmating P系统）是第一个在膜之间引入非直接通信的变体。基于生物学过程，他们定义了一种[3]通常是层级结构，但也存在网络结构。190A. 维塔莱湾，澳-地Mauri/Electronic Notes in Theoretical Computer Science 171细胞膜仅对水、离子和一些小分子等物质具有渗透性，这些物质通过渗透作用自由地穿过膜其他物质需要特定的分子泵或通道才能穿过膜。最后，更大的物质如蛋白质或蛋白质复合物只能通过囊泡在细胞内外进行交流。 拟通报的实质内容被包围在一个新产生的囊泡中，通过一个发芽过程离开源膜。囊泡自由游动，直到它与靶膜融合，释放出其中的转运物质。高尔基体是使用这种通讯的细胞区室的一个例子：一堆基本膜，按顺序修改一组蛋白质并将其发送到下一个高尔基体区域。该过程的发送部分是通过囊泡实现的。这为了与生物现实非常相似，仅考虑简单的膜结构，并且所使用的操作具有生化灵感;皮肤膜仅包含基本膜（即，深度= 2），形式上有三种类型的操作：突变r m：a→u，复制r r：a→u1||u2和分裂rs：a→u1：u2，其中a∈V，u ∈V+，u1，u2∈V+.在这里，我们只是说复制和分裂增加字符串的数量，而突变可以删除符号。对于规则的完整形式定义，我们参考[1，第3页]。通常，每个区域i= 0，1，.，n的一个膜结构μ具有一个在V上的有限支集的多重集。此外，μ的每个区域i都关联了一组经典演化规则Ci和一组前动力学规则Di。元优先级在两个集合之间定义：Ci中所有适用的规则必须在Di中的任何规则之前执行。C i是一组突变、复制和分裂规则，其中得到的字符串通常定义为（V ×{here，out}），如果i = 1，. ，n，或超过（V × {here，out}）<$（V×{in1，.，in n}），如果i= 0。Di是一组突变、复制和分裂规则，其中u和u1、u2之间的至少一个是（（{@j}·V）× {here}）或（（V·{@j}）× {here}）上的字符串，其中@j是V中不存在的特殊符号，j是膜指数，例如j/=i。具体地说，前动力学规则只能在字符串w的两端引入符号@j，这意味着字符串w将通过可移动的囊泡运输到膜j。符号@j，一旦附加到字符串w上，有两个功能：它定义了必须运输的物质以及它应该去哪里通信是通过以下两个规则实现的两步过程：（一）（二）显然，w代表我们想要运输的物质，而i，j分别定义了源膜和目标膜。移动囊泡由一个[0.. . [iw@j]i.. . ]0−→[0.. . [i]i（i，jw）i，j.. . ]0[0.. . （i，jw）i，j[j]j.. . ]0−→[0.. . [jw]j.. . ]0发芽融合A. 维塔莱湾，澳-地Mauri/Electronic Notes in Theoretical Computer Science 171191匹配几个圆括号。为了我们的目的，所介绍的概念是表面上的，但关于宝石配对P系统的进一步细节，你应该参考原始论文[1]。2.2膜结石膜结石是一个家庭的过程结石提出的各种细胞动力学建模与生物膜的行为。与P系统的主要区别是，这里的活性实体与膜紧密耦合，这赋予了膜支持生物化学的（正确的）生物膜是由脂质双层形成的，脂质双层实际上表现为一种生物流体，它可以让结构成分和嵌入的物质（如蛋白质）自由地移动到脂质层所限定的区域将膜本身浸入水溶液中，在水溶液中膜可以自由地渗透。这样的双流体结构直接启发了Brane演算的基本结构：两个带有复制算子的交换幺半群，每个幺半群代表一种双流体。我们有(i) 代表脂质双层的幺半群：（膜，|、0）的哪里|是膜的 组 成 ， 0 是 单 位 （ 空 工 艺 ） ;(ii) 和表示水溶液的幺半群：（系统，系统，系统）式中，n是系统两个monoid都使用复制操作符！对相同类型的“多个”组件的概念（无限数量的组件的并行组合）进行建模。系统由嵌套的膜组成，每个膜代表定义其行为的动作（过程）的组合。形式上，基本语法由表1描述。系统P，Q：：= P <$Q <$！P <$σ<$P <$ nestedmembranes膜σ，τ：：= 0 <$σ| τ！σσ a.σ膜过程动作 a，b：：=.见表3表1Brane演算用σ<$P<$我们表示一个类属系统，它的行为由过程σ表征，并且包含系统P。我们用a.σ表示一个受保护的进程：该进程在执行动作a之后表现为σ。我们使用以下缩写：a为a。0，P为0 P，σ为σ。系统和过程都有一个定义在它们之上的结构一致关系（表2）。下一页表4中的一般反应对任何膜计算都是有效的。192A. 维塔莱湾，澳-地Mauri/Electronic Notes in Theoretical Computer Science 171nP<$Q <$Q<$Pσ|τ ≡ τ |σP<$（Q <$R）<$（P <$Q）<$Rσ|（τ|ρ）（σ|τ）|ρPPσ|0 ≡σ！你好！0 ≡0！（PQ）！P！Q！（σ|τ）！σ|！τ！！P！P！！哦！σ！噗！P！σ≡ σ|！σ0⟨⬦⟩ ≡⬦表2系统与膜lus，但每个演算都必须定义自己的特定反应，提供相对的反应规则。2.2.1Phago/Exo/Pino Brane演算Phago/Exo/Pino Brane演算（brie braney PEP）由内吞和胞吐的生物过程启发的三种作用定义。内吞作用的过程分为两种：吞噬作用（phago），它是指一个细胞只吞噬一个外膜的过程;以及胞饮作用（pino），它只吞噬外膜而不吞噬膜。胞吐作用以胞吐作用为代表，存在于内吞作用的相反过程中：单个内膜与外膜不可逆地混合，同时将其内容物推出内膜。动作a，b：：=噬菌体n⊥噬菌体;噬菌体外消旋体βpino（ρ） βbudn βbudn（ρ）表3PEP，加上bud，动作除了这三个基本动作，我们将使用复合动作芽来模拟萌芽（发芽）过程：它是细胞分裂的特化，包括分裂恰好一个内膜。芽动作可以用pino、phago和exo动作的序列编码（参见等式3和4）。对于涉及两个膜的每个动作，我们使用共同动作来识别第二个膜。这样的协同动作是通过在动作名称后附加符号“”来此外，我们可以索引我们的行动，以准确地耦合一个与正确的合作行动。表3和表5提供了PEP加芽动作的语法和反应规则。¦A. 维塔莱湾，澳-地Mauri/Electronic Notes in Theoretical Computer Science 171193n芽P Q<$P<$RQ<$RPQ<$σ<$P<$σ<$Q<$J J J JPPP QQQPQ我们用A表示4的传递闭包和自反闭包。表4通用反应规则噬菌体⊥噬菌体，噬菌体|σ0<$P噬菌体n（ρ）.τ |τ0Q⊥τ|τ0 ⟨ρ⟨σ|σ0 Pexo外， 外|τ0τ外显σ|0|σ0|τ |τ0Q皮诺皮诺（ρ）.σ|联系我们|σ0ρ P⊥∗芽芽n（ρ）.τ |τ0芽，σ|σ0PQρ⟨σ|σ0P τ |τ0Q表5PEP加复合芽作用的反应规则噬菌体行动和噬菌体将同步实现一个⊥膜进入另一个，而外膜和外膜 将同步以获得相反的过程 芽N和芽N的动作将同步分裂一个嵌套的膜。pino和pino的动作n有一个参数ρ代表膜反应生成新膜的过程为了清楚起见，我们明确了芽动作的编码芽，芽噬菌体，噬菌体.Σ⊥ ⊥⊥（三）芽n（ρ）.τpino phago n（ρ）. exonJ . 外J.τ以及它的完整反应⊥芽n（ρ）.τ |τ0芽，σ|σ0<$P <$$>Q <$=.圣皮诺皮诺 噬菌体n（ρ）。exonJ. 外J.τ |τ0噬菌体σ|σ0P Q- 是的黄曲霉属（四）外J.τ|τ0⊥噬菌体n（ρ）。exonj|σ0PQexonJ外J.τ |τ0<$exonJ<$ρ<$σ|σ0P Qρ⟨ σ|σ0Pτ |τ0Q194A. 维塔莱湾，澳-地Mauri/Electronic Notes in Theoretical Computer Science 171[4]粗略地说，这意味着反应不是基元跃迁，而是由一系列基元反应组成的。A. 维塔莱湾，澳-地Mauri/Electronic Notes in Theoretical Computer Science 171195n1n253PEP中通过移动囊泡进行通信的模拟如前所述，我们将使用PEP膜演算，加上复合动作芽，通过移动囊泡来模拟通信。我们在与Gemmating P系统相同的情况下工作：含有待传输物质的移动囊泡从膜源中弹出，并最终与膜靶融合，释放其内容物。该通信的期望属性是：• 安全性：“信息”应该仅可被靶膜接近。• 通信过程不应干扰正常的系统演进。我们用以下系统源！芽囊（泡）|ω源X目标！噬菌体，外噬菌体|ω T目标函数囊泡噬菌体2. EXO（五）其中X代表我们想要交流的物质（系统）。在宝石交配P系统中，我们只考虑一个简单的，虽然现实的，膜结构：一个两级层次结构，其中皮肤包含各种膜都在同一水平。让GωG源目标显然，ωG代表皮肤膜过程。如果Xωx不包含可达的芽n1作用，则系统G不演化。让G=ωG源目标..Σ Σ=ωG⊥！芽n1（泡）|ω源←−X+budn1−→芽N1|ω x◦ 目标芽N1ωG.∗Σ源微囊泡靶点.←−−Target∗ ←−mobilevescicle−→−−−−−−−→⊥ ⊥噬菌体N2=ωG源◦ 噬菌体2. exo X！噬菌体n2（exo）的方式|ωT目标（六）ωG.∗源.∗⊥⊥◦ ！噬菌体n2（exo⊥⊥）的方式|ωT目标.exo外消旋体exo非结构一致性ωG源◦ ！噬菌体n2（exo）的方式|ω T目标<$X<$0 <$. ←−−Source−（X+budn1）−−→←−Target+XΣ−−−−−−→⊥ ⊥ ⊥⇒ω克！芽n1（泡）|ω源！噬菌体n2（外）|ω T目标富含作用芽n1的物质X通过引起恰好含有X：作用芽n1的可移动囊泡的萌发而启动通讯5 我们用T表示系统T是一般修改的。196A. 维塔莱湾，澳-地Mauri/Electronic Notes in Theoretical Computer Science 1712都被这个过程消耗掉了这是PEP演算对应于Gemmating P系统的规则（1）。然后，移动囊泡通过噬菌体n2和胞外作用与膜靶融合：这对应于规则（2）。除作用芽n1外，我们观察到X从膜上移动源到膜目标。行动芽n1定义了一种特别的附加行为，作为Gemmating P系统中的特殊符号@对于这种类比，我们定义了以下特殊作用：@m1BudM1（7）与Gemmating P系统的唯一区别是，这里的信息（即，关于靶膜的指数）包含在可移动囊泡中，而不是直接包含在标记物@m1中。在（6）中，我们假设X已经有了启动通信过程所需的适当动作@m1，现在我们简要地讨论如何将通信标记添加到物质。在Gemmating P系统中，它是一个前动力学规则，通过将特殊符号@附加到编码物质本身的字符串来标记物质以进行传输在这里，我们提出了一个更一般的方法。在PEP中，我们可以以不同的方式将适当的action@i添加到物质（系统）中：(i) 当物质产生时，(ii) 在物质进入源头之后我们应该选择第一种情况，如果我们有一个产生X物质实例的源子系统，并且如果所有这些物质最终都应该通过一个移动囊泡与一个特定的膜进行通信：每种物质类型一个通信通道。否则，如果源可以将X物质传递到不同的膜，我们必须延迟标记过程，将其保留到特定的并行过程：每种物质类型都有许多通信通道。3.1新的复合操作：发送和接收最后，我们提供了两个新的复合动作，以简化通过移动囊泡的通信的使用。（八）（九）现在，我们可以以更清晰、更紧凑的方式模拟物质X在两层膜之间的传输.←−X−→传输发送1A组@1|ω X轴◦ ···接收2B中国（10）.←−X−→发送！ 芽（噬菌体）exo）M1⊥n2M1n2收到！噬菌体（exo）⊥ ⊥n2n2A. 维塔莱湾，澳-地Mauri/Electronic Notes in Theoretical Computer Science 1711972发送1条A条···接收2条BωX198A. 维塔莱湾，澳-地Mauri/Electronic Notes in Theoretical Computer Science 1714结论我们已经做了一个简单的建模测试，表明它是可能的模型，一个重要的一种生物通信的PEP膜演算很少的e-的ort。我们在一个简单和最小的情况下工作，作为一个用于Gemmating P系统，以强调两种建模方法的不同表达能力。PEP演算，让我们通过移动膜的通信模型，具有更少的e的排序比所需的Gemmating P系统。我们计划通过研究一个扩展来进一步研究这种在膜结石中的通信，该扩展应该让系统的任何两个膜通过移动膜进行通信，而不受两级层次结构的限制我们也有兴趣评估这种延伸的生物学意义。确认这项工作得到了意大利大学部（MIUR）在项目PRIN-04“系统生物学：模型、语言和分析（SYBILLA）"下的部分支持引用[1] Besozzi，D.，C.赞德隆湾Mauri和N. Sabadini，P具有可动膜萌发的系统，在：A. Restivo，S. Ronchi-Della-Rocca和L. Roversi，编辑，理论计算机科学。* 2001年10月4日至6日在意大利都灵举行的2001年国际交通运输中心第7次意大利会议。诉讼，计算机科学讲义2202（2001），pp. 136-153。[2] Busi，N.， 关于配偶/芽/滴膜演算的计算能力：交织与最大并行度，在：预处理 第六届国际膜计算研讨会（WMC6），维也纳，2005年6月18日至21日，2005年，第10页。235-252[3] Busi，N.和R. Gorrieri，关于膜演算的计算能力，CMSB 2005（2005），pp. 106[4] 卡尔代利湖， 膜结石：生物膜的相互作用。，in：V.Danos和V.沙赫特，编辑们，CMSB，Lecture Notes in Computer Science3082（2004），pp. 257-278.[5] 卡尔代利湖和G. Pagliun，基于mate/drip操作的（n）膜演算的普适性结果，在：ESF细胞计算探索性研讨会（复杂性方面）会议记录，塞维利亚（西班牙），2005年1月31日至2月2日，pp. 七十五比九十四[6] Pingyun，G.，用膜计算，技术报告208，图尔库计算机科学中心-TUCS（1998），（www.tucs.fi）。[7] Pingyun，G.，另一个普适性结果为P系统与对象上的膜，在：第三届头脑风暴周膜计算，塞维利亚（西班牙），1月31日至2月4日，2005年，页。263-274。[8] 罗森伯格湾和A.《形式语言手册》，施普林格出版社，柏林，海德堡，1997年。