随机自动机的视图和随机过程的描述

理论计算机科学电子笔记272（2011）3-17www.elsevier.com/locate/entcs基于Agent-视图自动机Heinz Koeppl2 Tatjana Petrov3洛桑联邦理工学院（EPFL）瑞士洛桑摘要在本文中，我们提出了一种基于随机自动机的形式主义来描述由规则集指定的信号转导网络的随机动力学。 我们的形式主义给出了一个模块化的描述，潜在的随机过程，在这个意义上说，它是一个组成的更小的单位，代理意见。 代理的视图是一个自动机，它识别该代理的所有局部修改更改（内部状态修改，绑定和取消绑定），而且那些相互作用的代理，这是在同一规则内测试。我们展示了如何将整个规则集的底层马尔可夫过程的生成矩阵表示为属于个体视图自动机的速率矩阵的克罗内克和。 在没有出生的情况下，自动机是有限的，因为一个智能体可以出现在规则集中的不同上下文的数量是有限的。我们通过一个与细胞信号事件相关的例子来说明这个框架关键词：细胞信号传导，连续时间马尔可夫链，随机自动机合成1引言信号蛋白的多位点翻译后修饰[21，17]和构象变化[4，18]的内部依赖性例如，考虑蛋白质相互作用网络驱动蓝藻的昼夜振荡。中心六聚体KaiC蛋白经历低磷酸化和高磷酸化状态的循环[14，13]，其中每个蛋白质亚基的两个残基的磷酸化序列受到严格控制[15]。此外，据信KaiC六聚体在发生构象改变时，1Heinz Koeppl感谢瑞士国家科学基金会的支持。200020- 117975/1。Tatjana Petrov感谢来自SystemsX.ch的支持，这是瑞士系统生物学倡议。2电子邮件：heinz. epfl.ch3电子邮件：tatjana. epfl.ch1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2011.04.0024H. Koeppl，T.Petrov/Electronic Notes in Theoretical Computer Science 272（2011）3Ⓧ过度磷酸化。参见图1，该循环过程由两种调节蛋白KaiA和KaiB控制。这种修饰事件是单分子事件，因此可以很好地封装到蛋白质的内部逻辑中。双分子事件，如调制剂结合，可以被认为是输入到这个状态自动机。单个蛋白质自动机的构造也Fig. 1. 多聚体蛋白的内在逻辑。 简化的方案捕获了基本的循环跃迁六聚体生物钟蛋白KaiC所经历的。过度磷酸化（黑色填充的亚基）诱导从变构紧张（）到松弛（Q）状态调节蛋白的结合可以被认为是该状态自动机的输入有望直接揭示相互作用蛋白质系综的有效自由度近年来，在确定这类系综的有效态空间维数和相应的广义态方面取得了很大进展该线程从[2，5]开始，其中构建了基于物种的状态空间的线性投影，允许在较低维状态空间上对动态进行自洽描述。在[8]中，将这种方法推广到任何基于规则的规范的区分语义的自动约简在[10]中给出了这种简化的随机版本。所有这些方法都有一个共同点，即它们首先描述具体的大状态空间，然后通过投影或聚合方法进行简化在我们的例子中，描述已经以象征性的、隐含的形式给出了。 我们采取自下而上的方法，观察每个代理的有效自由度，并相应地构建其局部状态空间。从以主体为中心的角度来看，自由度是主体所涉及的所有不同的上下文–因此，除了上述以代理为中心的模块化封装了代理考虑图2所示的例子，它传达了基本思想。它涉及一种可以同时和独立地结合两种其他蛋白质的sca蛋白质。考虑到图中的规则2.我们可以确定智能体A遇到了什么样的情境 它的观点产生了状态集合{A（b），A（ba. B）} ×{A（xu），A（xp）}。我们使用随机自动机表示其视图，然后将不同代理的视图自动机耦合到自动机网络[16]。这种网络有时可以转换为叠加广义随机Petri网（GSPN）[12] -一个集合 共享转换但没有位置的Petri-Cubes。 示例图2的情况在图3中示出，其中随机自动机被示出用于以下情况：每个代理的单拷贝数和任意标记的Petri网表示。 我们认识到，由于约束力和KaiaKaiaKaiaKaiaKaiaKaiCKaiCKaiCKaiCKaiCKaiaKaiaKaiaKaiaKaiaKaiCKaiCKaiCKaiCKaiC凯卜凯卜H. Koeppl，T.Petrov/Electronic Notes in Theoretical Computer Science 272（2011）35视图自动机B视图自动机AR1：A（b），B（a）−~7−A（b1），B（a1）R2：C（b），B（c）~−7−C（b1），B（c1）R3：A（xu）~−7−A（xp）R3：C（yu）−~7−C（yp）图二. Sca蛋白B独立地募集蛋白A和C（左）。为了便于说明，我们假设后两者是自发磷酸化和去磷酸化的。Kappa语法[7]来表达这种交互（右）。图3中的视图自动机可以被构造为两个较小自动机的自动机乘积，这两个较小自动机是从它们各自的规则R1和R3获得的。在这个例子中，视图自动机状态等价于由[10]获得的片段中表示的状态将一个基于规则的规范映射到一个随机分配网络，图三.代理A的随机视图自动机网络和代理B的部分显示（左）;每个代理绘制一个拷贝数。只有跨不同自动机的具有相同标号的变迁被同步化。相应的Petri网表示，其中视图网共享变迁但不共享库所。Tomata允许人们使用为这种网络开发的合成方法[3]。此外，我们可以利用组合结构来获得网络的连续时间马尔可夫链的生成矩阵的表达式，该表达式涉及各个自动机的生成矩阵的第一次使用随机自动机网络来描述随机化学动力学可以在[22]中找到这项工作认为，基于物种的状态空间，并与每个物种的计数器自动机工作的其余部分安排如下。在第2节中，网站图和他们的编码为一组布尔变量的赋值。编码的灵感来自Kappa [7]中站点图的定义。第3节通过定义规则和基于规则的系统来继续形式主义每个基于规则的系统，伴随着初始条件被分配（连续时间）的随机语义的解释标记转移系统（以下简称ILTS）。此外，定义了代理视图和人口视图投影。主要结果在第4节中陈述，其中我们提出了基于规则的系统的ILTS何时以及如何可以表示为较小ILTS的组合abAxBC b振英6H. Koeppl，T.Petrov/Electronic Notes in Theoretical Computer Science 272（2011）3每一个对应于规则的子集。 导出了分解准则 通过分析每个规则中出现的变量集。在此基础上，第五节利用以智能体为中心的合成方法显式构造了随机自动机网络的马尔可夫链生成器。使用图2的简单缩放示例概述了该过程。结论见第6节。2一个简单的基于代理的框架我们在基于规则的语言Kappa上建立了一个形式主义[7]。我们用来描述蛋白质网络结构和编码反应混合物的主要数据结构是位点图。标准图是由一组节点和一组在节点对上形成的边定义的对结构，而站点图具有稍微丰富的结构：每个节点由（i）它的名称，（ii）一组具有内部状态的站点，以及（iii）该节点的一组绑定站点定义;然后建立边，不是在节点名称之间，而是在一对绑定站点之间，每个绑定站点属于不同的节点。定义2.1（站点图）考虑一组代理名称A和一组站点名称S。站点图是一个对G=（V，E），其中节点集是代理名称、其内部站点集和其绑定站点集的三元组，即V{（A，int，l）|A ∈ A;<$int，<$l <$2S}和边是位置对：E<${（（A，s），（AJ，sJ））|（A，int，l），（AJ，intJ，Jl）∈ V，s ∈l，sJ∈ lJ}.具有节点（A，Rint，Rint1），代理A的站点集合，即RintRint1，有时被称为代理A的接口，并且被表示为Rint（A）。当我们用位点图对蛋白质相互作用网络建模时，一组代理A表示一组蛋白质名称，一组位点S表示蛋白质的不同相关氨基酸残基。在蛋白质网络模型中总结蛋白质名称及其可能的结合的位点图，我们称之为接触图（CM）。例2.2（图2重访）联系地图是一个站点图（V，E），其中代理名称A ={A，B，C}和站点名称S ={a，b，c，x，y}; n个节点的集合是V= {（A，{x}，{b}），（B，x，{a，c}），（C，{y}，{b}）}，并且边E={（（A，b），（B，a）），（（B，c），（C，b））}.此外，给定联系图和代理- 副本被分配名称A1，...，A n（A）. 在连续映射中，任意（Ai，s）和（AJ，SJ）之间生成键，使得键存在于（A，s）和（AJ，SJ）之间形式上，具有代理名称A和S的CM（V，E）上的完整CM是一个站点H. Koeppl，T.Petrov/Electronic Notes in Theoretical Computer Science 272（2011）37图（VJ，EJ），具有代理名称AJ和站点名称S，使得AJ={A i|A∈A，i = 1，..，n（A）}，以及若（A，int，l）∈ V，则（A i，int，l）∈ VJ，其中i = 1，.，n（A），且边集EJ使得如果（（A，s），（AJ，SJ））∈ E，则（（Ai，s），（AJj，s））∈EJ，i=1， . . . ，n（A），j=1， . ，n（AJ）.例2.3（图2次重新访问）为n（A）=1,n（B）=2,n（C）=1,我们得到完整的接触图（VJ，EJ），其中AJ={A1，B1，B2，C1}，并且VJ为{（A1，{x}，{b}），（B1， n，{a，c}），（B2， n，{a，c}），（C1，{y}，{b}）}， and EJ为{（（A1，b），（B1，a）），（（A1，b），（B2，a）），（（B1，c），（C1，b））（（B2，c），（C1，b））}。如果我们对蛋白质相互作用网络建模，我们需要表示某个时间点的反应混合物。一个完整的接触图是一个总结，哪些网站出现在哪个代理，但它并没有告诉我们什么是内部状态的价值;此外，在网站图中指定的债券是潜在的形成，但他们可能 或者可以不存在于反应混合物中。 换句话说，给定一个位点图，有几种混合物对应于该位点图，这取决于内部位点的内部状态，并取决于混合物中存在哪些键。为了简单起见，我们假设内部状态可以取正好两个值，并且我们将一组布尔变量分配给完整的接触映射，使得这些变量的一个赋值编码反应混合物。每个代理的站点花费一个变量Var（V，E）={（A，s）|（A，nin t，nl）∈ V且s∈nintnnnl} nE.每个站点变量都由字母a表示，其下标中包含相应的座席我们使用键描述的字母b我们用V arA表示涉及主体A∈ A的变量集。从集合V ar（V′，E′）到布尔值的变量的任何赋值将代理的内部状态设置为值给定由CM（V，E）导出的完全CM（VJ，EJVal（V′，E ′）={x |x：V ar（V′，E ′）→ {0，1}}.实施例2.4（Ex. 2revisited）.设n（A）= 1，n（B）= 2，n（C）= 1。 我们有这个Var={a（A1，x），a（A1，b），a（B1，a），a（B1，c），a（B2，a），a（B2，c），a（C1，b），a（C1，y），b（（A1，b），（B1，a）），b（（A1，b），（B2，a）），b（（B1，c），（C1，b）），b（（B2，c），（C1，b））}.状态x1=（0， 1， 1， 1， 0， 0， 1， 1; 1， 0， 1， 0）表示图1所示的混合物5b）。8H. Koeppl，T.Petrov/Electronic Notes in Theoretical Computer Science 272（2011）3JΣX的1BaB CBC1y1a）、一BC2X一11B aBCB y C110000000b）、一0B2 C0见图4。一、完整的联系方式。2和试剂多重性n（A）= 1，n（B）= 2，n（C）= 1; b）一个反应混合物对应于状态x1=（0，1，1，1，0，0，1，1; 1，0，1，0）∈ Val。 内部状态被设置为1（即x（b（C1，y））=1），通过突出表示该内部状态的绿色圆圈来标记。然而，并非所有的估值都将描述一个有效的反应混合物。首先，不能有两个债券源于一个网站的身份识别代理人任何节点（Ai，int，l）∈ VJ，且其结合位点s∈l，最多可以有一个键从位点（Ai，s）建立。其次，键的存在性，假设描述一个有效反应混合物的估值，我们称之为定义2.5（良好定义的估值）估值x∈V al是良好定义的，如果•Ai∈A′，s∈S|{（Ai，s）suc hthat A′∈A，s′∈SX（b（（Ai，s），（A′j，s′）=1}|≤1，且• x（b（（A，s），（A′，s′）= 1当且仅当x（a（A，s））= 1且x（a（A′，s））= 1.实施例2.6（Ex. 估值x2=（0， 1， 1， 1， 0， 0， 1， 1， 1， 0， 1， 1）没有很好的定义，因为b（（B2，c），（C1，b））= 1，但a（B2，c）= 0。此外，x3=（0，1， 1， 1， 0， 1， 1， 1， 1， 0， 1， 1）的估值也没有很好的定义，因为有两个债券源于网站（C1，b）。人们可能会问，为什么我们对每个键进行两次编码，因为键（（Ai，s），（AIJ，SJ））的存在可以从a（Ai，s）=a（A′，s′）=1得出结论。让我们回到前任。2，假设我们有两个代理A的副本，和两个副本的代理B，即n（A）=n（B）= 2，并有所有绑定，即x（a（A1，b））=x（a（A2，b））=x（a（B1，a））=x（a（B2，a））= 1.然而，我们可能在A1，B1和A2，B2之间，或者在A1，B2和A2，B1之间有键。我们使用键变量b（（A1，b），（B1，a）），... . ，以避免这种歧义。3基于规则的模型我们观察到的代理集合的转换内核由一组规则定义。在对应于接触的变量集上定义规则地图（V，E），即V ar（V，E），它包括左手边（lhs在进一步的文本）和右手边（rhs在进一步的文本），这是命题公式在从集合V ar（V，E）中的变量。我们将以如下方式来思考一个规则：规则的左手边α定义了事件发生的前提条件。右边的αd定义了估值的更新，它是以下原子操作的有限组合：（i）H. Koeppl，T.Petrov/Electronic Notes in Theoretical Computer Science 272（2011）39（Ⅲ）11111111α<$<$a（A，s）和αd<$a（A，s），（ii）一对变量从自由态到结合态或相反的变化（结合/非结合），即α<$<$a（A，s）<$<$a（A′，s′）<$<$b（（A，s），（A′，s′））和αd<$a（A，s）<$a（A′，s′）<$b（（A，s），（A′，s′））。我们仅限于没有出生，也没有删除代理的情况。我们还假设规则中最多出现一次相同的代理名称。请注意，这两个约束都是相对于Kappa语言的限制- Kappa在一个规则中支持相同代理名称的更多占用。出现在规则R中的变量的集合，我们用V arR表示。定义3.1（规则）考虑变量上的命题公式PV ar（V，E）（也记为P（V，E）），由文法p0生成|1|a∈V ar（V，E）|p|我们用V ar p表示在命题p中出现的变量的集合，并且用p ={x|X| = p}。规则是一个三元组 （α，α d; k）∈P × P ×R0，使得Var α= Var αd.我们注意到，规则是在接触图上定义的，而代理没有提到多重性。我们观察由CM（V，E）导出的全CM（VJ，Ej）上的变量集Var（V′，E′）变量V ar（V，E）上的每个规则生成变量V ar（V，E）上的一组规则。变量V ar（V′，E′），其中代理的标识符是指定的：而不是一个单一的规则R，我们观察到一个家庭的规则{ R id A = i } A ∈A ; i∈{ 1，.，n（A）}，其中每个代理A被分配唯一标识符id A∈ {1，.，n（A）}。这样的规则集我们称之为可识别规则，记为Rid。实施例3.2（Ex. 2revisited）. 图中描述的规则在这个框架中重写的5个是（R1）<$a（A，b），<$a（B，a），<$b（A，b），（B，a）→a（A，b），a（B，a），b（A，b），（B，a）（R2）<$a（C，b），<$a（B，c），<$b（C，b），（B，c）→a（C，b），a（B，c），b（C，b），（B，c）（R3）<$a（A，x）→a（A，x）（R4）<$a（C，y）→a（C，y），其中我们以α→αd的形式写出规则r=（α，αd;k）（我们不写不需要说明的比率）。在n（A）= 1、n（B）= 2和n（C）= 1上设置代理多重性，规则（R1）具有以下两个实例：（R1idA=1，idB=1）<$a（A，b），<$a（B，a），<$b（A，b），（B，a）→a（A，b），a（B，a），b（A，b），（B，a）（R1idA=1，idB= 2）<$a（A1，b），<$a（B2，a），<$b（A1，b），（B2，a）→a（A1，b），a（B2，a），b（A1，b），（B2，a）.定义3.3（基于规则的系统）在代理A的集合和站点S的集合上的基于规则的系统B =（V，E，n，R，p0）由以下定义：（i）在接触图（V，E）和初始代理多重性n上的全接触图（V j，E j）：A→ N 0，（iii）规则集合R={R1，.，Rm}定义在切触映射（V，E）上，（iv）由命题p0∈ P（V，E）表示的初始混合. 如果一组规则中的每一条规则都是定义良好的，那么这组规则就是10H. Koeppl，T.Petrov/Electronic Notes in Theoretical Computer Science 272（2011）3→→→S|0Σ我们将通过具有可数状态空间的转换系统来定义基于规则的系统的语义。每个状态被分配一个或几个反应混合物，由变量V ar（V′，E′）的命题公式表示;跃迁由定义它的规则的名称标记定义3.4（标记迁移系统）标记迁移系统是一个元组M=（S，L，δ，S0），其中• S是一组状态，• L是一组标签，• δ：S×L→S是将状态和标签映射到另一个状态的转换函数，• S0S是初始状态的集合，长度为k的M的迹是序列s0l1，t1S1 → →sk−1lk，tkSK ∈S×（L×R×S）k，则δ（sj−1，lj）=sj，j=0，1， . ， k和s0∈S0.定义3.5（解释标记转移系统-由L：S→2Val.这样的系统我们称之为解释LTS，我们用ML表示。我们说ILTS ML是良定的，如果对所有s，SJ∈S，我们有L（s）<$L（SJ） =<$，即。分配给不同状态的值集通常是不相交的。迹线的柱面r=s0l1，l1S1 →........ →sk−1lk，lkSK ∈S×（L×IR×S）k表示由给定的k个转变序列开始的所有迹线的集合，以及每个转换发生在箭头所示的时间间隔的初始分布是这样的，如果s ∈ S0，则π0（s）= |1（我们使用符号）|·|表示集合的基数），否则π0（s）= 0。的概率迹线r的圆柱由以下表达式给出：π（r）=π0（s0）·Kj=1a（sj−1，lj，sj）a（sj−1）·e−a（sj−1）·inf（Ii）−e−a（sj−1）·sup（Ii）<$，其中a（sj-1，lj，sj）是在I j时间间隔内经由标签l j从状态sj-1转换到状态sj的活动，其将取决于ILTS模型所定义的规则集而被指定。 状态sj−1的总活动y是a（sj−1）={a（sj−1，lj，sj）|lj∈L，sj∈S}.给定一个基于规则的系统B，我们通过赋予它ILTSML来解释它的语义。然后我们说ML对基于规则的系统建模，写作ML|= B.粗略地说，我们将ILTS的每个状态与解释联系起来，通过识别每一种试剂或在一定的抽象级别上，所分配的赋值描述了反应混合物。此外，转换由启用转换的规则标记。过渡的起源是其解释满足规则左手边的状态，活动是→H. Koeppl，T.Petrov/Electronic Notes in Theoretical Computer Science 272（2011）311（2）4与该规则的速率成比例定义3.6（对基于规则的系统进行建模的完整ILTS）系统B=（V，E，n，R，p0）定义在代理类型A的集合和站点S的集合上。我们构造了ILTSML，它具有与集合Val（V′，E′）中的赋值一样多的状态，并且每个状态都用具有恰好一个赋值的集合来解释这样的ILTS是定义良好的，因为任何两个满意集之间的交集都是空洞的初始状态是其估值满足（p0）的状态。标签集就是已识别规则的集合。状态s之间的跃迁用R标记，使得L（s）={x}和SJ，使得L（SJ）={XJ}当且仅当x和XJ使得x∈α和XJ∈αd，并且它们评估所有变量将规则R中未提及的元素的活度设为相同的值;此外，活度由a（s，JRJ，sJ）=k（R）给出。如果这对所有规则R∈（α，α d; k）∈Rid都成立，那么我们说转移系统M =（S，L，δ，S0）在解释L中对规则集Rid建模，记为ML|= Rid.这样的ILTS具有与定义连续时间马尔可夫链上的随机化学动力学的标准方式相一致的动力学[11]，[1]，[9]。例3.7（图在这个例子中，变量有36种不同的形式良好的赋值此外，这些配置中的任何一个都可以以四种不同的方式进行编码，这取决于A1和C1的内部状态的值，即变量a（A1，s）和a（A1，s）的值。a（C1，s）. 这使得总数为（1 + 4 + 4）·4 = 36。定义3.8（代理视图）给定一个基于规则的系统B=（V，E，n，R，p0），定义在代理类型A的集合和站点S的集合上，设RA是规则R的子集，使得对所有R∈ RA，V arR<$V arA成立规则RA的子集，我们称之为AgentA的Agent视图。- 是的完整的ILTSover我们承认，由于规则集在置换代理的标识符下是封闭的，我们可以定义一个基于种群的ILTS，它对基于规则的系统进行建模。定义3.9（基于人口的ILTS，对基于规则的系统进行建模）基于规则的系统B=（V，E，n，R，p0），定义在代理类型A的集合和站点S的集合上。我们构造了ILTSML，它具有与由等价关系Val（V′，E′）×Val（V ′，E′）划分的集合Val（V′，E′）中的赋值一样多的状态，该等价关系标识直到标识符上的置换的所有状态注意p0是在变量VarV ，E的集合上定义的，而分配给状态的值是在变量V arV'，E'上定义的。我们认为，它沿着如何出现在规则中的命题是实例化时，代理多重性;12H. Koeppl，T.Petrov/Electronic Notes in Theoretical Computer Science 272（2011）3R {}⎛⎞⎝⎞⎠∼Jx=a（A1，x）b（（A1，b），（B1，a））b（（B2，c），（C1，b））a（C1，y）n，anndxJ=⎝aB2个r1aB1ABABaBR−1aB 2b）、图五. (a)代理A的一组规则= R1，R2的视图的表示;（b）基于人口的ILTS模型的规则R1在Ex。二、相同类型的代理人：x<$xJ如果存在一个置换σ：{1，...，n（A）}A∈A→ {1，.，n（A）}A∈A使得对所有i，x（a（Ai，s））= XJ（a（σ（Ai），s））.我们设置SVal/。每个状态都被分配了一组属于这个等价类的赋值。让我们用[x，α]表示的不同实例的数量，在V ar α中变量的标识符，使得x| = α id5。标签集是没有标识符的规则集，即L=R。两个状态x1 <$，x2 <$∈V al/k由对应于规则R<$（α，αd;k）的标签R连接，当且仅当类x1 <$满足规则R的左侧条件，并且分配给标签R∈R的速率等于k（R）·[x1，α]。例3.10（图2（重新讨论）让美国观察的估值01 1 1⎛a（A1，x）b（（A1，b），（B2，a））b（（B1，c），（C1，b））a（C1，y）6. 它认为xxJ，be可以用we0 1 1 1来表示，有一个置换σ<$A1B1B2C1<$，使得x（a）=x（a），对于所有A1B2B1C1-C4（Ai，s）（σ（Ai），s）A∈ A，且i = 1，...，n（A）。 等价类，其代表是x，X可以被描述为由试剂B和C如果这个状态被命名为s，那么我们给它分配解释集L（s）={x，xJ}。在基于人口的ILTS中有20个状态，它在示例中对系统进行建模债券：一个没有债券，两个不同的估值， 具有一个键的混合物（或者在A型试剂之间形成复合物[5]假设有一条规则是αa（A，x），年龄n是A1和A2;那么基数y[x，α]可以是0、1或2，这取决于有多少个A是自由的。6我们不提及每个代理人aB1AB2R1R1−aB 11AB11aBaB 22R1a）、R1−aBAB11aB 2H. Koeppl，T.Petrov/Electronic Notes in Theoretical Computer Science 272（2011）313我和B之间，或B型和C型试剂之间），以及编码具有两个键的混合物的两个不同赋值（一个具有A、B和C的三聚体，一个B是游离的，或者形成两个二聚体而没有B是游离的）。这种观察导致了代理集成的“基于人口”的语义，这是标准的描述。4模型分解一个完整的ILTS模型的状态空间的规则为基础的系统增长成比例的变量的数量在其完整的接触地图，这增长的组合在代理的数量和他们的接口的复杂性我们建议将其定义为较小ILTS的组合。我们从一个ILTS开始，它分别为每个规则建模，然后我们在它们上面定义一个复合算子。换句话说，我们将ILTS分解为较小ILTS集合的标准乘积定义4.1（两个ILTS的叉积）给定两个ILTS：M1，L1 =（S1，L1，δ1，S01），具有一组变量V ar1，赋值V al1和对状态L1和M2的解释，L2 =（S2，L2，δ2，S02），其中V ar2和V al2和L2，使得L1<$L2=0，且dVar1<$Var2=0。我们定义乘积ML=（S，L，δ，S0），记作ML=M1，L1×M2，L2如下：• S=S1×S2，• L=L1L2，• δ（（s1，s2），l）=（δ1（s1，l），δ2（s2，l）），对任意l∈L，• （s1，s2）∈S0i ∈s1∈S01和s2∈S02（即S0=S01×S02）。此外，我们设置V ar=V ar1<$V ar2，并通过每个状态的赋值集的交集来L（（s1，s2））= L1（s1）<$L2（s2）.我们还可以看到ILTSM1 ，L1（分别为M1 ，L1）作为ILTS ML到变量集合V ar1（resp.V ar2），我们可以写为M1，L1 = ML|第1版。由叉积组成的两个ILTS的唯一约束是它们定义在相互不相交的变量集和相互不相交的标签集上。提案4.2（分解ILTS）给定 一 基于规则 系统 B=（V，E，n，R，p0）定义在代理类型A的集合和站点S的集合上。 设ML是模拟Rid的完全ILTS。如果我们可以将规则集划分为类R1，.. .，Rm，使得R = R1≠. 并且每两个类都有互不相交的变量集，则ML可以分解为以下形式：MML=MiLi，i=1其中对于所有i = 1，. m，ILTS M i，LimodelsRid.14H. Koeppl，T.Petrov/Electronic Notes in Theoretical Computer Science 272（2011）3R12R3R1RR3X一1X一1R3−振英R4R4−Cy11一B1R1aB 11ABAB1R−1一B一1B222R1R1−aBM L |VarA B11R1aB 2BC1BCR2BC11B C1BC2R−2B1C2R2R2−BCM|1LV arR2B C1BC2ML|R3ML|V arR4图第六章 分解位置：ML=ML|VarR1×ML|VarR2×ML|VarR3×ML|4.第四章例4.3（图2重访）出现在每个变量中的变量集规则是V aridA=1，idB=11={a（A1，b），a（B1，a），b（（A1，b），（B1，a））}，VarRidA=1，idB=2 为{a（A1，b），a（B2，a），b（（A1，b），（B2，a））}，VarRidB=1，idC=1为 {a（B1，c），a（C1，b），b（（B1，c），（C1，b））}，V aridB=1，idC=12={a（B1，c），a（C1，b），b（（B1，c），（C1，b））}，VarRidA=1={a（A1，x）}，VaridC=14={aC1，y}。 并不是所有的都是相互分离的，但是我们可以将它们组合在一起，将变量集分成以下不相交的类：VarR1=VarRidA=1，idB=1VarRidA=1，idB=2，VarR2=VarRidB =1，idC=1，VarRidB =2，idC=1，VarR3=VarRidA =1，1 2 1 3Var R4 = V ar id C =1。4我们建立了四个ILTS模型，每个模型都有这些变量：ML1| =IDA=1，IDB =1IDA =1，IDB =2{R1，R1}，类似地，ML2，ML3，ML4。 ILTSML，模型规则Rid是以下组成：ML= ML1×ML2×ML3×ML4。ML是定义良好的ILTS，其投影为ML1 = ML|VarR1，ML2= ML|VarR2，ML3 = ML|VarR3，且ML4 = ML|VarR4.5生成器的构造如果我们根据连续时间马尔可夫链为基于规则的系统建模的ILTS配备随机语义，则可以将建模单个规则的每个ILTS视为随机自动机，并且将其组合视为随机自动机网络。我们通过回顾图2中讨论的例子来介绍生成器的构造。分析规则集并考虑命题H. Koeppl，T.Petrov/Electronic Notes in Theoretical Computer Science 272（2011）3154.2，我们得出结论，变量集是不相交的，我们在图中显示了四个ILTS投影6对于n（A）=n（C）= 1，且n（B）=16H. Koeppl，T.Petrov/Electronic Notes in Theoretical Computer Science 272（2011）3我L∈LΣΣΣΣL1−−−−1−−111LL1111IDA=1，IDB=110 0 00 0 0- idA=1，idB=1 10 0 00 0 0i=1l∈Lii=1l∈Li2. 我们组成的随机自动机网络的生成矩阵Q的基本矩阵，从个人的自动机。 考虑由ILTS {M1，...， M m}。每个ILTSMi的特征在于：从集合L标记的转变的集合。例如，对于图6中的网络，我们 有 L1 = {Rid A=1，id B =1，Rid A=1，id B =2，R−id A=1，id B =1，R−id A=1，id B =2}。为每个定义了一个初等速率矩阵Ei，其元素Ei（j，k）表示在自动机Mi中通过转移l从状态j到状态k的速率。最后，为了保证生成器的行和为零，我们设计了一个矩阵Di=diag（Eie），单位向量为e。根据[16，3]，生成器可以是L l表示为M mQ=Ei− Di其中我们使用符号来表示Kronecker和[19]。该组合只包括克罗内克和，这是已知的，以对应于独立的连续时间马尔可夫链的经典组合。我们限制的情况下，独立的ILTS（有小自动机之间没有同步转换），所以涉及克罗内克积运算符的部分不出现在表达式中。例5.1（图2（重新讨论）去回来到图6和exem-1简化投影ML的结构|VarR1，我们有L={RidA=1，idB =1，RidA=1，idB =2，R−idA=1，idB =1，R−idA=1，idB =2}，状态空间S={s1，s2，s3}。然后，基本矩阵变为EM1=100k10m，EM1=0 0k1，和EM10 0 0=k−0 0， EM10 0 0=零 0 0 、−idA=1，idB=2 1其中，对于l∈/Li，E i = I。10 0 0−idA=1，idB=2 1k1−0 0让我们讨论另一个例子，我们回顾一下第4节中提出的结构。考虑一个激酶K可以结合底物S并独立磷酸化其两个修饰位点s2和s3。在卡帕语法中，C+R：K（k），S（s）−~K（k1），S（s1）11 171 1C1C+R：K（k1），S（s1，su）−~2K（k1），S（s1，sp）（一）21 1 27 1 1 2C2C+R：K（k1），S（s1，su）−~3K（k1），S（s1，sp）.31 1 37 1 1 3C3RRRRH. Koeppl，T.Petrov/Electronic Notes in Theoretical Computer Science 272（2011）317从考虑出现在每个规则R1，R2和R3中的变量集开始，由于它们都具有非空的相互交叉，我们不能应用ILTS的分解，该分解模拟了所有规则，在Prop.4.2. 因此，每一个主体的主体视图暴露并决定了每一个主体的完整界面，这相当于说视图是完全特定的物种。这个系统的有效自由度，撇开质量守恒关系，因此等于不同的可达物种的数量6结论本文提出了一种自然的方法来描述高度结构化的分子代理的随机相互作用。每个代理都与一个随机自动机相关联，它描述了该代理的自由度和视图。它允许有效状态空间的自底向上构造。这种模块化表示是有代价的：乘积公式过度近似可达状态空间-但不是它的维度。自然地，这种方法变得更有吸引力，每个自动机的代理人的内在逻辑就越丰富。我们展示了如何将整个规则集的底层马尔可夫过程的生成矩阵表示为属于各个视图自动机的速率矩阵的克罗内克和。分解准则是通过分析出现在每个规则中的变量集而得出的。人们可以理解分解原理背后的直觉，即利用某些事件的统计独立性。参考（1）的规则集，我们在下面讨论未来的研究方向，其承诺进一步分解。即利用较弱的条件独立性概念构造降维状态空间。（1）中的两个修饰位点s2和s3联合概率Pr（s2，s3）不能被因式分解。然而，在状态S1的条件下，事件变得独立。使用乘积规则条件概率我们有恒等式Pr（s2，s3|s1）= Pr（s2|s3，s1）Pr（s3|s1）。独立性意味着状态s2以s3和s1为条件和只以s1为条件是一样的。因此，我们有Pr（s2，s3|s1）= Pr（s2|s1）Pr（s3|s1）。让我们考虑一个粗粒度的碎片，它不枚举站点状态s2和s3，而只枚举站点状态s1。然后重建问题是，给定Pr（s1），我们是否可以重建联合Pr（s2，s3，s1）。 考虑到手头的依赖结构，我们有Pr（s2，s3，s1）= Pr（s2|s1）Pr（s3|s1）Pr（s1），我们只剩下定义两个条件分布。这种修改事件的数量遵循泊松定律。因此，修改状态s2和s3可以从已知的s1中恢复。显然，在衬底S中(1) 具有多个独立的磷酸化位点，则所呈现的分解将比利用条件的分解指数地大，而不是完全独立。18H. Koeppl，T.Petrov/Electronic Notes in Theoretical Computer Science 272（2011）3引用[1] Baier，C.，B. Haverkort，H.赫尔曼斯和J. - P. Katoen，连续时间马尔可夫链，IEEE软件工程学报29（2003），p.2003年。[2] Borisov，N. M.，N. I. Markevich，J. B. Hoek和B. N. Kholodenko，Signaling through receptors and scabodies：Independent interactions reduce combinatorial complex，Biophys J89（2005），pp.951-966[3] Buchholz，P.和p.Kemper，Kronecker基于矩阵表示的大型马尔可夫模型，在：随机系统的验