参数布尔网络在系统生物学中的应用与分析方法研究

可在www.sciencedirect.com在线获取理论计算机科学电子笔记335（2018）67-90www.elsevier.com/locate/entcs参数布尔网络JurajKolc'aka，bDavidSafra'nekb，1StefanHaaraLocPaulev'ecaInria和LSVE'coleNormaleSup'erieuredeCachan和CNRS卡尚b马萨里克大学系统生物学实验室捷克共和国cLRI UMR CNRS8623Univ. 法国巴黎萨克莱奥赛大学巴黎南科学研究摘要在系统生物学中，细胞调控过程的模型，如基因调控网络或信号通路，对于理解活细胞的行为至关重要。然而，可用的生物学数据通常不足以用于完整的模型规范。 在本文中，我们专注于部分指定的模型，其中以参数的形式提取丢失的信息。 我们引入了一种新的分析方法的参数逻辑调节网络解决两个来源的组合爆炸的模型。首先，我们引入了一个新的紧凑表示的容许参数使用布尔格。然后，我们定义了参数布尔网络的展开。所得到的结构提供了并发转换的偏序约简，并分解了具体模型之间的公共转换。对国家的最先进的方法进行比较参数模型分析。关键词：布尔网络，参数识别，异步系统，并发性，系统生物学1介绍计算系统生物学研究的主要问题之一是理解细胞内分子间的相互作用，通常表现为网络。主要对两类过程进行建模，即基因表达调控（基因调控网络）和细胞信号传导[13]。基因调控网络的主要兴趣是基因-蛋白质和基因-基因相互作用，后者通常由它们编码的蛋白质促进细胞信号模型通常由一个或多个信号通路组成简单地说，蛋白质链通过连续的磷酸化提供信息，直到某些细胞过程（如基因表达）被中断。1这项工作得到了捷克科学基金会第2000号拨款的部分支持GA15-11089S。https://doi.org/10.1016/j.entcs.2018.03.0091571-0661/© 2018作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。68J. Kol cá k等/ElectronicNotesinTheoreticalComputerScience335（2018）67虽然所描述的两个过程在性质上都是定量的，但它在生物学背景下，反应的精确动力学参数是未知的。因此，通常通过离散模型（逻辑调控网络）对遗传调控网络和信号传导途径进行建模[1，6，15，18，19]。在基因调控网络和信号传导途径的背景下，通常情况下，物种之间的一对一的竞争是已知的体外实验。然而，这些因素组合的结果在很大程度上是未知的。换句话说，可以知道两个物种对 第三物种的活动/种群。然而，很少有人知道是否两种激活剂都必须存在才能激活靶点，或者只有一种激活剂就足够了。一般来说，一个任意的逻辑函数可以控制关节的连续性。为了从技术上解决这个问题，将一个物种的个体目标值及其调节剂活性的可能组合视为未知参数。参数调节网络（PRN）的分析受到双重COM的阻碍双星爆炸不仅网络的状态空间的大小是指数的，而且参数化的数量在最坏的情况下是物种数量的双指数这些因素的组合通常导致PRN的分析技术不能扩展到更大的网络。我们的贡献。本文提出了一种新的参数逻辑调控网络分析框架，在两个层次上解决组合爆炸问题。首先，我们提出了一种新的编码的参数化使用的内部结构的参数化。编码被应用于减轻由参数化引起的组合爆炸。提供了允许有效使用编码的伴随方法。其次，我们扩展Petri网展开，以适应参数设置。 展开与编码方法相结合 用于参数化以允许PRN的状态空间的紧凑表示这要归功于它们利用并发性的能力。最后，提供了一个原型实现来计算所引入的展开。实验进行比较，我们的方法对国家的最先进的方法在参数调节网络分析的结果相关工作。参数不确定性条件下的逻辑调节网络分析是一个尚未深入研究的领域.最近，由于系统生物学领域的重要性和巨大前景，它越来越受欢迎。计算树逻辑（CTL）[2]已被Bernot等人用于枚举Thomas网络的所有可能的时间属性（参数化）。基于LTL模型检验的方法[2]也被引入到Thomas网络[14，10]中。在[14]中，[3]中首次引入的称为有色模型检查的方法用于利用许多参数化共享其行为的某些部分。参数化由二进制向量中的颜色（位）表示，并且模型检查扩展到二进制向量操作以跟踪令人满意的行为。[10]中的方法探索了以执行树的形式象征性地表示的状态空间这种方法最接近我们的工作，因为[10]中使用的状态空间的符号表示是非循环的，类似于展开。此外，委员会认为，J. Kol cá k等/ElectronicNotesinTheoreticalComputerScience335（2018）6769一BC在[10]中还使用逻辑公式执行参数化的编码。然而，与我们的固定大小编码相反，[10]中使用的公式在探索过程中继续扩展，因为需要更详细的参数化编码。还使用约束逻辑编程进行参数识别[5，9]，再次使用Thomas网络。[5]中的方法将所有可用的生物学知识编码为对网络行为的逻辑约束，而在[9]中，约束逻辑编程用于预处理初始的一组约束，以过滤出与约束相关联的约束。模型检查随后用于较小的（过滤的）集合。Ostrowski等人[17]还介绍了一种限制布尔网络可能行为的初始集合的方法。逻辑约束来自时间序列数据和答案集编程（ASP）应用于计算一组最适合的测量瞬态动态（参数化）。纸结构。在第2节中，我们介绍了参数调节网络，包括它们的语义和参数化。第3节通过用于将先验知识纳入模型的信息上的标签进一步扩展了在第4节中，我们通过引入一种新的参数化编码来解决参数化的潜在双指数数这种编码随后应用于第5节中的参数调节网络的展开。第6节提供了使用参数展开的实验结果以及与依赖于执行树的方法的比较[10]。2参数调控网络在本节中，我们将介绍参数监管网络（PRN）。 非正式地，人们可以将PRN视为具有未知动态的标准调节网络，即过渡关系。因此，我们可以使用一个有向图来捕捉PRN的拓扑，即所谓的Inquirience Graph，G=（V，I），其中V是n个顶点（分量）的集合，I<$V×V是有向边（Inquirience）的集合。我们将某个v ∈ V的所有内邻（调节器）的集合表示为n−（v）={u∈V|（u，v）∈I}和所有外邻居（目标）的集合为n+（v）={u∈V|（v，u）∈I}。我们运行的示例的影响图可以在图1中看到。图1.一个简单的三节点调节网络的影响图。我们将进一步在我们的运行示例中使用这个图形。70J. Kol cá k等/ElectronicNotesinTheoreticalComputerScience335（2018）67一一0Pa∅1Pa{a}BB0Pb∅1Pb{b}一BC00Pc∅Pc{b}Pc{a}Pc{a，b}011011表1图1所示的连续性图中运行示例的节点的真值表。 真值表对于所有三个节点：a、b和c从左到右列出一般来说，每个分量v∈V被认为是一个具有有限离散域（多值）的变量。在本文的范围内，我们将自己限制为布尔设置。扩展到多值变量被认为是进一步的工作。在每个变量v∈V都是布尔的情况下，我们将PRN表示为参数布尔网络（PBN）。将交互图的组件视为变量允许自然定义PBN的状态。G=（V，I）的状态X表示V（X<$V）的任何子集 我们说，任何分量v ∈ V在状态X中是活动的（值为1），如果v∈X，并且相应地，v是不活动的（值为0）， 如果v∈/X。 We表示所有可能状态的集合为X = 2 V。相互作用的性质取决于给定状态下组件的活动水平。然而，在生物学中，调节剂对其靶点的确切作用往往是未知的。因此，我们通过参数来抽象这些值。参数表示分配给给定组合的目标值在特定状态下确定的活动和非活动调节器。自然地，对于任何这样的调节器组合存在参数。我们将这样的组合表示为监管背景（RC）。正式定义如下。定义2.1分量v∈V的调节上下文ω是v的调节器的任意子集。形式上，ωn−（v）。就像PBN的态一样，我们说所有的分量u∈ω都是活动的，所有的分量u∈n−（v）\ω都是不活动的。v的所有组合可能的调节上下文的集合将进一步表示为Ωv = 2n-（v）。以这种方式，RC对应于每个分量的真值表的行。我们运行示例的真值表以及RC和参数如表1所示。每个参数（RC）都可以指定一个目标值0或1。 我们将所有RC的这种分配表示为参数化。定义2.2参数化P<$Ω（Ω =v∈V（{v}×Ωv））将监管背景与每个组件相关联。我们称在参数化P下分量v的RCω的目标值为1 i <$（v，ω）∈P。我们写ω∈P而不是（v，ω）∈P，只要目标v从上下文中已知。J. Kol cá k等/ElectronicNotesinTheoreticalComputerScience335（2018）6771我们把一个不连续图G=（V，I）的所有可能参数化的集合记为PG= 2Ω.因此，PBNB是配备有可能的参数化的关联图G2.3参数布尔网络（PBN）B是一对（G，P），其中G是一个不连续图，P ∈PG，其中P /= P∈G是G的可能参数化的非空集合。如果P=PG，那么我们说B是完全参数的。 另一方面如果|P|= 1，则B是一个简单的布尔网络。最后，我们可以定义PBN的动力学。正如我们已经提到的，配备单个参数化的PBN的动力学与标准布尔网络相同。然而，有几种方法可以从同步的角度定义布尔网络的动态。在生物学背景下，个体反应通常在时间上彼此独立，不存在明确的同步性。在本文的范围内，我们考虑了布尔网络的通常异步语义，其中每次最多更新一个组件。异步动态通常是不确定的，然而，它可以通过所谓的状态转移图（STG）S=（X，δ）很容易地捕获，其中δX × X是由RC的目标值给出的状态转移关系。直观地说，PBNB=（G，P）的STG可以被认为是布尔网络（G，{P}）的STG的自然合成（转换上的并集），对于每个P∈ P。 更正式地说，由于不确定性，我们只考虑在一个元素中不同的状态之间的转换。设X1，X2∈ X是在一个元素v∈V（分别为X1\X2={v}，X2\X1={v}）中离散的两个状态. 转移（X1，X2）属于δ，只有当至少存在一个参数化可以重现它。更正式地说，对于v被分配活动值0（X1\X2={v}）的情 况 ， 我 们 需要<$P∈P ： （ n− （ v ） <$X1 ） ∈/P 。 F或 v 被 赋 值 为 活 动 值 1（X2\X1={v}）的情况下，我们需要<$P∈P：（n−（v）<$X1）∈P。3关联图在上一节中，我们介绍了PBN，并提到参数不确定性的原因来自缺乏生物相互作用的信息然而，这些信息往往是部分可用的。部分生物学知识可以归纳为两类约束条件：单调性和可观测性。单调性有两种形式，即正单调性和对偶负单调性。 边（u，v）∈I在参数化Pi ∈ I下是正单调的<$ω∈Ωv ： u∈ω<$ （ ω∈P<$ω\{u}∈/P ） .类 似 地 ， 一 条 边 （ u ， v ） ∈I 在Pi<$$>ω∈Ωv：u∈ω<$（ω∈/P<$ω\{u}∈P）下是minus-单调的. 换句换句话说，如果源的活动的增加不能72J. Kol cá k等/ElectronicNotesinTheoreticalComputerScience335（2018）678一BO+O+C哦-哦-图2. 通过引入标号函数γ={（（a，a），{−，o}），（（b，b），{−，o}），（（a，c），{+，o}），（（b，c），{+，o}）}，得到一个标号不连续图（LIG）.标记严格地确定了控制a和b的自我调节的布尔函数。事实上，从运行示例的初始2 = 256个参数化中，只有两个参数化是可能的。还注意到，运行示例的每个交互的标记γ我们将这种标记功能称为全标记，将具有全标记的LIG称为如果源的活动的增加不能引起目标活动的增加，则另一方面，在参数化P下，边（u，v）∈I是可观察的，如果ω∈ Ω v：|{ω\{u}，ω{u}}P|= 1。 换句话说，边是可观察的，如果存在调节器的组合，使得源的活性的变化引起靶的活性的变化自然地，单调性和可观测性可用于限制可能的参数化。因此，我们给该关联图 配 上 一 个 标 号 函 数 γ ： I→2{+ ， - ， o} ， 它 指 定 了 每 条 边 所 满 足 的 条 件 。ALabelledInu-因此，图（LIG）是元组G=（V，I，γ）。 可能的参数化G是{P∈ P（V，I）|i∈I：P满足γ（i）}所施加的条件。一个图2中给出了一个标签函数和LIG的示例，使用运行示例作为原始的嵌入图。4参数化编码在前面的部分中，我们介绍了布尔网络的参数化概念和自然约束，以实现关于模型的部分知识。然而，在实践中，由于组合爆炸，当应用于引入的PBN时，已知方法是不可扩展的。事实上，PBN的组合爆炸发生在两个实例中。首先，状态空间在元件数量上是指数的（注意X= 2V）。状态空间爆炸也适用于标准的布尔网络和等效模型（这将在第5节中更详细地讨论）。第二，可能的参数化的数量也与RC成指数关系（PG= 2Ω）。在本节中，我们致力于组合子爆炸的第二个原因，参数化的数量。在这里，我们介绍了一种新的方法来编码一些特殊的参数集相关的应用程序。需要对参数化进行编码，特别是对于生成PBN的过程（可能的行为）。虽然进程可能是无限的，但任何可达状态至少可以被一个有限进程达到。因此，我们只要求J. Kol cá k等/ElectronicNotesinTheoreticalComputerScience335（2018）6773有限的进程是可达性完整的。正式定义如下。定义4.1设（G，P）是具有STG（X，δ）的PBN一个长度为k ∈ N的过程是一个状态序列π =（X1，...，Xk）∈ Xk，其中i∈{1，.，k−1}：（Xi，Xi+1）∈δ.令π =（X1，...， Xk）是一个过程，X ∈X是一个状态，使得（Xk，X）∈ δ.则πJ=π·X是一个长度为k+1的过程，我们说πJ是π的扩张。PBN代表了几种不同的模型可能性引入个别参数化。尽管单个参数化应该是排他性的，但PBN的动态（由其STG给出）并不区分它们。因此，在PBN中有可能存在混合不同参数化的过程。这些过程可能不对应于任何单独参数化的过程。为了避免探索这种不连贯的过程，我们分配给每个过程（被视为一个序列的过渡，或作为一个部分有序的多组过渡）一组容许参数化。设（G，PG）是PBN，（X1，X2）∈δ是相应STG的跃迁，使得对于某个v∈V，X1\X2={v}.我们把这种过渡称为v的抑制。每一个允许v在状态X1下被抑制的参数化都必须将X1<$n−（v）的目标值赋值为0。此外，将X1<$n−（v）的目标值固定为0对于参数化允许过渡（X1，X2）是足够的我们将类似的推理应用于激活（X2\X1={v}，对于某些v∈V）。激活要求相关的RCX1<$n−（v）具有目标值1。因此，我们可以定义一个过渡d=（X，XJ）∈δ的相关监管背景为ωd=n−（v）<$X，其中{v}=XΔXJ（Δ是指对称差异）。任何变换都只更改一个分量的值。因此，任何转变要么是某种成分的激活，要么是某种成分的抑制。因此，一个任意的转移集D<$δ被唯一地给定为抑制集DI和激活集DA的并集（D=DA<$DI）。我们现在形式化的概念下的参数上下文（PC）的概念下的任何一组转换的可行参数化。定义4.2设（G，P）是具有STG（X，δ）的PBN。 我们定义了一个函数p：2δ→ 2 P，它为每一个变迁集分配了一个参数化集，所有这些变迁都包含在这个参数化集中。 对于任意y，gi venanyD∈δ，设p（D）={P∈P|<$d∈DA：（ωd∈P）<$<$d∈DI：（ωd∈/P）}其中DA和DI分别是约束和抑制的集合，使得DA<$DI= D。我们称p（D）为D的参数上下文，对于任何D<$δ。可以注意到p（D）=d∈Dp（{d}）。我们将定义扩展到自然方式的过程 令π =（X1，...， Xk）成为一个过程。 π的PC是指p（π）= p（{（Xi，Xi+1）|i∈{1，.，k− 1}}）。一种计算上述PC的简单方法是枚举所有指数级的参数化。然而，正是由于PG= 2Ω，通过将集合包含序引入参数化，我们得到了布尔格（PG，Ω）。我们现在提供使用点阵进行PC编码背后的直觉。让我们考虑一个完全参数PBN（G，PG）。如上所述，74J. Kol cá k等/ElectronicNotesinTheoreticalComputerScience335（2018）67(A)（B）图3.在未标记的运行示例中，表示用于组件c的调节的参数上下文的晶格的哈斯图。（A）跃迁（{c}，λ）的PC，即， p（{（{c}，n）}）. （B）包括转换（{b，c}，{b}）之后的受限PC（p（{（{c}，n），（{b，c}，{b}）}））。任意单个转变d的PC仅包含将ωd的目标值设置为相同值的参数化如果d是某个v∈V的抑制，则我们知道w∈P∈p（{d}） ：ωd∈/P. 记住集合包含顺序，p（{d}）中的最大参数化是Ω\ {（v，ωd）}。事实上，p（{d}）是具有唯一主（极大）元Ω\ {（v，ω d）}的格（PG，ωd）的素理想（格L的理想I是素的，如果它是真的，且对任意a，b∈L，使得a∈b∈I或a ∈ I或b ∈ I成立）. 类似地，如果d是某个v ∈ V的激活，则PCp（{d}）={P ∈ PG|ωd∈ P}是（PG，n）的一个素滤子，它具有唯一的主（极小）元{（v，ωd）}（在与理想相同的条件下，滤子是素的，但不是下确界（n），而是上确界（n））。由于p（D<$DJ）= p（D）<$p（DJ）（定义4.2），我们可以注意到，任何集合DI<$δ的PC使得<$d∈DI：d是一个抑制是（PG，<$）的理想。相应地，任何激活集合DAAAδ的PC是滤波器。众所周知，任意理想和任意滤子的交要么是空的，要么是凸子格。此外，任何凸子格都可以由理想和过滤器的交集唯一表示[12]。这允许我们仅用最大元素（理想）和最小元素（滤波器）来表示（PG，λ）的任何凸子格。因为任何一组转换都可以分为一组抑制和一组很明显，任何PC都可以由最小和最大元素编码。在图3中可视化了表示为凸子晶格的PC的示例。我们所提供的结果适用于全参数PBN（G，PG）。然而，在LIG G的情况下，不保证晶格（P G，P G）存在。 这是因为在P G中可能存在两个参数化，使得它们的下确界（上确界）不属于P G。 为了说明，考虑具有一个可观察交互的运行示例，例如，标号γ={（（a，c），{o}）}。 相互作用（a，c）在参数化{（c，n）}和{（c，a）}下是可观测的，并且其中b{（c，n）}，{（c，a）}∈PG.在交（有限）式<$={（c，c）} <${（c，a）}下，任何相互作用都是不明显的，即（a，c）不明显意味着<$∈/PG.为了解决这个问题，我们提出了PBNB =（G，PG）的过近似，其构造为BJ=（G，[PG]），其中我们使用[P]来表示最小的凸子，{（c，{a}），（c，{b}）}{（c，{a}），（c，{b}），（c，{a，b}）}{（c，{b}），（c，{a，b}）}∅{（c，{a，b}）}{（c，{a}）}{（c，{b}）}{（c，{a}），（c，{a，b}）}{（c，{a}），（c，{a，b}）}{（c，{a}）}{（c，{a，b}）}∅J. Kol cá k等/ElectronicNotesinTheoreticalComputerScience335（2018）6775格，P ∈[P]。 在类似的情况下，我们引入了一个过逼近PCPJ：2δ→2PG 因此，如果P（D）= π，则pj（D）=[p（D）]或PJ（D）=π。标记函数γ引入了各个RC的目标值之间的依赖性，因此计算pJ（D）<$pJ（DJ）可能不足以获得与p相反的正确的pJ（D<$DJ）。但是，我们可以通过以下方法解决这个问题。我们的方法依赖于对某个过程π =（X1，.，Xk）来计算任意扩张π·X的PC，其中X ∈X是相容态。因为我们知道p（π·X）<$p（π），并且在猜想pJ（π·X）<$pJ（π）中，扩张的PC只能小于π的PC。从而实现了从PJ（π）untl[p（π·X）]中连续提取元素的方法. 这些元素通过连续应用限制来解决。限制是监管上下文ω∈Ωv（对于某个v∈V）和值i∈ {0， 1}的组合。一个受限PC则是一个PCP，满足：如果i=1，则满足：P∈P：ω∈P，如果i=0，则满足ω∈/P。在其他情况下，限制确保受限PC中的所有参数化对于给定RC具有相同的目标值。该方法认识到限制的两个原因。首先，扩展本身要求允许转移（Xk，X）。其次，边缘标签引入了各个RC的目标值之间的依赖性。该方法检测这些依赖性并相应地限制PC。有关该方法的更详细说明，请参见附录A.1。该方法最重要的特性之一是保持可达性。由于该方法保证了 PJ（π·X）= [p（π·X）]，即如果p（π·X） =π，则PJ（π ·X）=π，因此，如果PJ（π）/=π，则保证也有p（π）/=π，反之亦然。这个性质在第5节中变得很重要，在那里我们构造了一个可达状态空间的紧凑表示。由于可达性被保留，通过过近似pJ达到的任何状态都保证也是p可达的，反之亦然。这允许我们计算过近似pJ内的可达状态。然而，只有当方法的输入pJ（π）是正确的时，才能保证保持可达性。案件存在其中初始的[PG]PG。 因此，需要预先计算，以确定[PG]. 附录A.2中详细说明了预先计算本身。5参数展开先前，我们引入了参数化的编码以减轻由RC的所有可能组合引起的组合爆炸。在本节中，我们将讨论PBN和标准布尔网络的状态空间的组合爆炸。生物网络通常在本质上是相当稀疏的因此，部分降阶方法对于处理标准网络的状态空间爆炸问题是有意义的Petri网展开是利用变迁并发性的结构的一个很好的例子。因此，本节致力于将展开应用于PBN和一般的参数设置76J. Kol cá k等/ElectronicNotesinTheoreticalComputerScience335（2018）67现在我们将介绍使用由pJ给出的PC的PBN的展开。直观地说，展开是PBN的所有过程在给定初始状态开始的非循环（树状）表示。虽然可以为任何PBN构造一个等价的Petri网，但我们并不要求这个Petri网能够显式地展开PBN。我们将PBN的（参数）展开定义为事件结构。因此，我们的构造类似于Petri网展开[8，7]。唯一的区别是事件的来源，在我们的例子中是PBN与Petri网。因此，PBN展开和Petri网展开在结构上是相同的。当确定哪些分支可以被截断而不损失可达性时，需要对PBN展开的完整有限前缀一般来说，事件结构是一个三元组E=（E，≤，#），其中E是事件的集合，≤E×E是E上的偏序关系，称为因果关系，#E×E是反对称的，不相关的关系，称为联系关系，满足：(i) e∈E：{eJ∈E|eJ≤e}是有限的。(ii) e，eJ，eJJ∈E：（e#eJ<$eJ≤eJJ）<$e#eJJ.为了我们的目的，我们通过一组条件B（我们采用Petri网展开符号）扩展事件结构，以在我们的设置中提供因果关系和冲突关系背后更好的直觉。 首先让我们定义一个给定PBN的所有可能事件E和条件B的集合。 由于事件和条件的定义是相互依赖的，我们定义了集合Ei和Bi的层次结构。 首先，设B0={（v，v，j）|v∈V<$j∈ {0，1}}。 然后我们定义Ei={（β，v）|v∈ V<$β<$j∈{0，.，i−1}BjBi={（e，v，j）}|v ∈ V<$j ∈ {0，1}<$e ∈ Ei}，对所有i ∈ N。的期望的E= i∈NEi和B=i∈N0Bi因此成为无限并集。每个条件b∈B都是b=（e，v，i）的形式，其中e∈E<${n}是b的前趋（父）事件，如果它存在，或n;否则，v∈V是由条件b表示的PBN的分量，i∈ {0，1}是v在b中的值。直观地说，条件表示一个进程通过跟随事件e到达组件v具有值i的状态的可能性。 类似地，每个事件e∈E具有e=（β，v）的形式，其中β∈B是e的前驱（预设）的集合，v∈V是其值通过触发e而改变的组件。直观地说，事件e表示在β中的调节器的影响下分量v改变值的可能性。事件与STG（δ）的跃迁非常 事实上，如果事件e =（β，v）是良构的（满足n−（v）<${v}={u|（eJ，u，i）∈β}，|n−（v）{v}|为|β|我们可以定义一个相关的RC ωe={u ∈ n−（v）|<$（eJ，u，i）∈ β：i = 1}就像过渡一样。我们也可以区分事件之间的激活和抑制。 我们说事件e=（β，v）是一个激活v，如果<$（EJ，v，0）∈β，类似地，e是v的抑制，如果<$（EJ，v，1）∈β。任何形式良好的事件都是唯一的激活或抑制。这使我们能够将PC函数p和pJ扩展到自然形式的良构事件。 形式上，让EE是一组格式良好的事件。 则p（E）={P∈P|其中EA是一个活动集，EI是一组抑制，使得E=EA<$EI。我们现在可以定义因果关系和矛盾关系。设e，EJ∈E是任意的.J. Kol cá k等/ElectronicNotesinTheoreticalComputerScience335（2018）6777∈≤≤J JJ我们说事件e=（β，v）因果依赖于事件EJ=（βJ，u）（EJe）、如果e=EJ或存在b=（EJJ，w，i）β使得EJEJJ.换句话说，如果存在由条件和事件的父项和子项定义的从e到eJ的有向路径，则e因果依赖于eJ如果<$（e≤eJ）和<$（eJ≤e），我们说e和e因果独立。类似地，如果存在事件（β，v），（βJ，u）∈E使得（β，v）/=（βJ，u），（β，v）≤e，（βJ，u）≤EJ且β∈βJ/=β j，则e与e（e # e）是连续的。 在其他文字中，如果两个事件（或其因果关系的前辈）通过两个不同的事件使用相同的条件，则它们是冲突的。我们也可以通过简单地设置<$（β，v）∈E：<$b∈β：b（β，v）和<$（e，v，i）∈B：e（e，v，i）并计算自反闭包和传递闭包，自然地将因果关系和冲突关系推广到调整了约束关系，将其域扩展到E→B。 另外，设x，y∈E∈B，使得x和y因果独立且不冲突。我们说x和y是共点的。可以注意到，（B，E，≤，#）可能不是扩展的事件结构，因为它不能保证满足因果关系和冲突关系的约束因此，我们使用B<$B和E<$E的子集构造开折，其中关系≤和#满足所需的性质。设（G，PG）是一个PBN，STG（X，δ），X0∈ X为初始状态.然后，在状态X0下构造（G，[PG]）的开折U=（B，E，≤，#）如下。(i) 从emp tyB=和E=开始。(ii) 对于每个v∈V，给B加上一个条件（i，v，i），使得i= 1，如果v∈X0，否则i= 0(iii) 对于每个v∈V，求所有共点条件（陪集）的集合C ∈B，使得{u|（e，u，i）∈C}=n−（v）<${v}且|C|为|n−（v）<${v}|. 对于每一个人，创建一个e ve nte=（C，v）。如果e∈/E，则使用下式中的出租m计算pJ（e）：附录A.1. 如果pJ（e）n把e加到集合E上，并且对于每个（eJ，u，i）∈ C，新的条件b=（e，u，j）toB，其中如果u v，则j=i，对于u=v，j=（1−i）。如果至少有一个事件添加到E中，重复步骤（iii）。虽然B和E是B和E的子集，但从展开的构造中可以明显看出，它们在一般情况下是无限的。我们在第4节中提到，任何可达状态都是有限进程可达的。由于展开是网络的所有过程的表示，并且状态的数量是有限的，因此存在展开的有限个预设，所有可达状态都可以从这些预设中恢复。我们把这样的前缀称为完全有限前缀（CFP），并在下面展示一个可能的构造。首先，我们定义了一个在传统上被称为配置的展开过程定义5.1一个集合C∈E是一个构形，如果它是无约束的（$e，eJ∈C：e#eJ）和因果闭的：e∈C，eJ∈E：eJ≤e∈eJ∈C。通过[e]，我们表示称为e的局部配置的特殊配置，[e]={eJ∈ E |eJ≤ e}。任何配置C对应于PBN的至少一个过程，通过完成与C中事件等价的转移的偏序来给出。我们可以78J. Kol cá k等/ElectronicNotesinTheoreticalComputerScience335（2018）67J因此，为每个有限配置分配一个终端（最终）状态XC=X0Δ{v1} Δ···Δ {vk}其中C ={e1=（β1，v1），.，ek=（βk，vk）}且k∈ N0.设C是一个构形，F∈E满足C∈F=F。我们说，如果C∈F是一个构形，则F是C现在让我们考虑C的所有可能的扩展。C的任何扩展都对应于原始PBN中从状态XC开始的进程，并且每个这样的进程都由扩展表示。因此，我们可以看到C的所有扩张定义了PBN在状态XC和初始参数化pJ（C）中的展开。此外，在P ∈pJ（C）中任何可能的扩张在p（C）下也是可能的。现在让我们考虑两个构形C，CJ<$E使得XC=XC′且PJ（C）<$PJ（CJ）和C的一个扩张F<$E。由于F是C的扩张，它肯定属于PBN在状态XC中的开折，其中pJ（C），即a0级了c0b0的e0级e1e4的1B1e5的1b0的C1e2e6e3a0级B1C1a0级的1C1B1b0的e7e8a0级B1e13了c0a0级e9e11b0的e10e12的1b0的了c0的1a0级了c0b0的B1图4.通过展开运行示例获得的完整有限前缀，该运行示例配备了图2所示的完整标记功能。完整的有限前缀被可视化为Petri网。由它们所代表的分量和分量的值（vifor（e，v，i））标记的条件是用圆圈表示。 由y_numbering（e_i表示第i个顶点）标记的顶点由直角表示。切割事件还用虚线边界标记。注意，a和b种的同时激活/抑制的顺序被抽象化了。J. Kol cá k等/ElectronicNotesinTheoreticalComputerScience335（2018）6779≺它也属于XC中有PJ（CJ）的开折。PBN的展开由初始状态和可行参数集唯一给出。因此，在XC中具有PJ（CJ）的开折必然同构于在XC′中具有PJ（CJ）的开折。特别地，Cj的扩张Fj<$E必同构于F.这适用于C的任何扩展，这意味着由C的扩展捕获的任何信息已经被CJ的扩展覆盖，并且从可达性的角度来看是冗余的这一结果对于局部配置尤其有趣。设e，EJ∈E使得X[e]=X[e′]且PJ（[e]）<$PJ（[EJ]）.由于没有必要探索我们将他们从《古兰经》中剔除。我们通过截断事件的概念将其一旦一个事件e被标记为cut-o，则没有其他事件eJ∈E使得e eJ被添加到CFP。Esparza等人。[8]证明了Petri网展开需要一个特定的配置顺序，称为适当顺序，以保证没有可达性因cut-o而丢失。 因为我们的展开概念等价于Petri网的展开我们在订单上也有同样的要求。通过这一点，我们将进一步理解[8]中定义的完全充分序，并根据我们对展开的定义进行了调整（定义见附录B）。以下是一个正式的定义定义5.2一个事件e∈E被认为是截止事件，如果存在一个不同的事件eJ∈E使得X[e]=X[e′]，[eJ]<$[e]和pJ（[e]）<$pJ（[eJ]）。然而，总的足够的顺序，不相关的包含顺序超过PC。换句话说，C<$CJ不保证p（CJ）<$p（C），反之亦然。这样的情况可能会发生，其中两个事件e，eJ∈E的局部配置导致相同的状态X[e]=X[e′]，并且p（[e]）p（[eJ]）也成立。理想情况下，在这种情况下，不应该探索e的扩展，因为它们都是多余的，eJ的一些扩展。 然而，由于[e] [eJ]，e将不会被设计为cut-o-n（因为eJ还不存在），并且e的一些扩展可能在eJ之前已经被探索过了。在我们的算法中，当eJ被添加到CFP时，e被标记为cut-o_n，并且我们删除了它的（不必要的探索）扩展。使用扩展的完全足够阶计算的标准完全有限Petri网前缀有许多不超过Petri网标记图（状态空间）大小的非割零事件[8]。这种说法在我们的设置中不然而，由于CFP中的过渡的结果部分排序，人们可以很容易地认为CFP中的进程数量小于STG中的迹线数量图4显示了运行示例的完全标记版本的计算CFP。6实验在这一节中，我们提出了一些关于生物模型的初步结果，并与[10]中采用的符号表示进行了比较。结果已经取得80J. Kol cá k等/ElectronicNotesinTheoreticalComputerScience335（2018）67政变ftio-SP8o-O+o-O+O+O+O+o-Fgf8o-o-Pax6o-o-o-Emx2TNFaEGFo-O+O+O+IKBPI3KSOSo-o-o-O+O+O+O+NFkBGSK3map3k1RAF1O+O+O+O+O+p38AP1CREBERK一个名为Pawn的参数文件夹的Python原型实现。2比较是关于代表所有可能轨迹的结构的大小进行的。因此，我们比较了展开的大小-符号执行树，使用工具SPuTNIk[10]获得。因此，在参数生物调控网络的范围实验针对两种不同的生物模型进行。首先，我们使用一个布尔模型的基因调控网络的哺乳动物皮质区的发展[11]。该模型如图5（A）所示。研究了两个不同初始状态的可达状态空间首先，所有物种都被认为是不活跃的。第二，所有物种都被认为是无活性的，唯一的例外是Fgf8。(A)（B）图5. （A）控制皮质区发育的遗传调控网络。 标记的状态在其中一个实验中，蓝色的已被设置为初始值1。（B）EGF-TNFα的信号传导途径的模型。仅有的两个以初始值1开始的状态用蓝色标记第 二 种 模 型 是 信 号 传 导 途 径 EGF-TNFα ， 如 [16 ， 17] 中 所 研 究 （ 图 5（B））。在这种情况下，除了两种输入物质tnfa和egf是活性的（X={tnfa，egf}）之外，每个物质的初始状态都是非活性的。结果总结见表2。Pawn的执行时间不到一秒（100秒）。4 s）和8左右。噬菌体λ（两种变体）和EGF-TNFα分别为5秒另一方面，SPuTNIk在有和没有Min/Max的情况下对于噬菌体λ分别需要101min和1010min，并且对于EGF-TNFα需要 1030 min。虽然没有对参数展开的大小的理论估计， 从结果中可以看出，利用并发性允许对于实际中参数状态空间的相当小的表示。尺寸的差异主要来自于展开的能力，2Pawn可在线获取：https://github.com/GeorgeKolcak/PawnJ. Kol cá k等/ElectronicNotesinTheoreticalComputerScience335（2018）6781模型展开的事件展开事件（带有cut-o按钮）符号执行大小皮质（Fgf 8 =1）1,0543,5308,312皮质（Fgf 8 =0）5541,9398,312EGF-TNFα1,0572,658534,498表2不同模型的展开和符号表示之间获得的结构的大小的比较。利用并发性。因此，如果有n个不同的并发转换正在触发，展开不会区分它们被触发的顺序，只会探索一种可能性。另一方面，符号执行探索所有n！可能的发射序列，每次只获得相同的结果这在包含大量并发转换的稀疏网络中尤其在皮层发育模型中实验的两个初始条件的情况下，相同的状态空间是可达的。然而，在这两种情况下，不同大小的展开表明，我们的技术是敏感的具体的初始状态确定的建设展开。7结论提出了一种基于Petri网展开的逻辑调节网络参数辨识平台。 我们的贡献涉及几个问题。 首先，我们介绍了一种新的方法来编码参数化允许有效分析参数布尔网络。我们在实践中采用的编码计算可行的参数化系统的所有可能的行为。并提出了相应的方法，以有效地计算编码中行为扩展的可行这组参数可以有效地由单调性和可观测性准则约束。今后的工作还可考虑考虑到其他限制因素，如