几种外部干预算法的比较

崔振东 刘文斌

摘   要：网络干预始终是基因调控网络研究的终极目标。本文关注于8种不改变调控规则的干预算法，对这些算法的设计角度进行了分析，发现MFPT、BOA、SSD、CSSD、UC这五种算法未对存在认知风险的状态加以约束，而conSSD算法、conCSSD算法、PC算法对此加以了限制;其次，这8种算法虽从不同的角度进行干预策略的设计，但所得干预策略的应用均能改善网络的长期动态行为。

关键词：外部干预算法;干预策略;稳态分布;MFPT;BOA;SSD;CSSD;UC

中图分类号：O157.4                                      文献标识码：A                            DOI：10.3969/j.issn.1006-1959.2018.21.004

文章编号：1006-1959（2018）21-0010-03

Comparison of Several External Intervention Algorithms

CUI Zhen-dong，LIU Wen-bin

（School of Physics and Electronic Information Engineering of Wenzhou University， Wenzhou325035， Zhejiang，China）

Abstract：Network intervention is always the ultimate goal of gene regulation network research.This paper focuses on eight intervention algorithms that do not change the regulation rules， and analyzes the design of these algorithms. It is found that at present，the five algorithms of MFPT，BOA，SSD，CSSD，UC do not restrict the state of existence of cognitive risk， while the conSSD algorithm， conCSSD algorithm， PC algorithm do;Secondly， although the eight algorithms design the intervention strategy from different angles， the application of the intervention strategy can improve the long-term dynamic behavior of the network.

Key words：External intervention algorithm;Intervention strategy;Steady-state distribution; MFPT;BOA;SSD;CSSD;UC

基因調控网络的长期动态行为在某种层面上反映了细胞的状态（如癌变），这往往是由关键基因的表达值决定的，该关键基因也称为目标基因。整个状态空间S可根据该基因在布尔机制下的表达值分为：期望状态集D、不期望状态集U，在D中仍存在一些模棱两可的状态Da，它们虽与不期望状态无直接关系，但却存在认知风险。特定的干预可使网络动态行为沿期望方向发展，并规避该风险，进而改变细胞状态。然而生物学中普遍存在一种情况：一个基因或蛋白质的激活（抑制）可能比其他基因或蛋白质更容易导致一个特定的细胞功能状态或显型的产生[1]。选出最佳干预基因并制定相应的干预策略便构成了干预的两大元素，且二者均是基于推理网络获取的，其在原始网络上的作用效果将直接反映是否推理出网络的核心骨架，钱晓宁将此作为了评估推理网络有效性的一个衡量准则[2]。

干预分为结构干预和外部干预，结构干预是一种从本质上改变状态转移路径的干预方法。它通过改变网络调控规则来达到改善稳态分布的效果[3-5]。外部干预则通过是否翻转当前状态的控制基因位来改善稳态分布，其网络结构并未发生变化[1]。本文关注于外部干预的几种典型算法MFPT（mean-first-passage-time）、BOA（basin-of-attraction）、SSD（steady-state-distribution）、CSSD（conservation-SSD）、conSSD（constrained-SSD）、conCSSD（constrained-CSSD）、UC（unconstrained-optimal-intervention）、PC（phenotypically-constrained-optimal-intervention）。从干预策略的设计角度对算法进行了分析1 外部干预算法

干预算法主要用来获取干预基因所对应的干预策略，这又可分为三种：马尔科夫策略MM、平稳策略MS、平稳确定策略MD。若uk∈MM，则uk发生的概率与时间和当前状态有关;若uk∈MS，则uk发生的概率与当前状态有关，且对于当前状态x采用策略a的概率为u（a∣x）∈[0，1]，a=1表示对当前状态的控制基因位翻转，翻转后状态记为，反之不翻转;若uk∈MD，则uk发生的概率与当前状态有关，且u（a∣x）=0或1。

1.1非约束性算法

1.1.1 MFPT算法  MFPT算法设计是基于网络的状态转移的。根据目标基因的值可将状态转移矩阵表示为以下情况P=。该算法的核心思想是减少停留在不期望状态的时间，增加停在期望状态的时间。其最终得到的干预策略属于MD。

根据公式（1）可计算出MFPT向量KD和KU

其中，e是由1组成的一个列向量，KD表示D中各状态首次到U的时间集合，KU表示U中各状态首次到D的时间集合。

为了尽可能早的到达期望状态以及离开不期望状态。MFPT定义了以下准则：若状态x∈U，则判断KD（x）- KD（）与阈值λ的关系;若状态x∈D，则判断KU（）- KU（x）与阈值λ的关系。前者是缩短到达D的时间，后者则是延长到达U的时间。通常情况下，我们取阈值λ=0。根据该准则可决定当前状态x的控制基因位是否翻转，从而得到最终干预策略。

1.1.2 BOA算法  到达期望状态并不代表该路径的顶端是期望吸引子。BOA算法注意到基因调控网络的长期动态行为主要由吸引子决定。故该算法设计从吸引子出发，其核心思想是减少到达期望吸引子的时间，增加到达不期望吸引子的时间。其准则如公式（2）（3）所示：

其中，B（x）、B（）分别表示状态x、最终归属的吸引子（环），dD（x）、dD（）分别表示状态x、到最近期望状态的距离，dU（x）、dU（）分别表示状态x、到最近不期望状态的距离。

根据以上准则可得相应的干预策略，且其属于MD。该准则保证了当前状态尽可能的进入期望吸引子，若无法进入，则尽可能早的到达期望状态。

1.1.3 SSD算法  以上两种算法虽均能通过干预策略改变网络的长期动态行为，但其获取干预策略的准则并非直接以稳态分布中不期望状态的概率和πU的变化来制定的。SSD算法则将此直接作为衡量准则，其核心思想是干预当前状态x是否能减少πU。根据公式（4）可得對状态x的控制基因位干预后的新稳态分布πx。

π=π-，Z=（I+P+eπ）（4）

其中π、πx分别表示干预前的稳态分布以及状态x在该分布中所对应的概率，P、P分别表示状态 x、在转移概率矩阵P中所对应的行向量，I表示单位矩阵。矩阵Z通常被称为基础矩阵。

SSD算法中干预策略的设计主要依据πU的变化，故其衡量准则如下：对状态x、，若πU≤min（π，π），则x、的控制基因位均不翻转;若 π≤π且π>min（π，π），则x的控制基因位翻转，的控制基因位不翻转;若π≤π且π>min（π，π），则的控制基因位翻转，x的控制基因位不翻转。

由此SSD算法可获得相应的干预策略。且其属于MD。但运用准则前依据公式（4）求出的πx并不能保证π≤π且π>min（π，π）。这在CSSD算法中得以实现。

1.1.4 CSSD算法  CSSD算法是通过迭代的思想得到干预策略的，每次迭代，它只从未实行干预策略的状态出发，根据公式（5），从中选取πU最大的状态的干预策略作为此次迭代的结果。当πU≤0时，迭代结束。整个网络的干预策略即可得到且属于MD。

π=π-π（5）

其中，π求法同SSD算法中。该算法能够保证每次迭代的结果π<π且应用整个干预策略后稳态分布中不期望状态的概率和是减少的。

1.1.5 UC算法  为在原始网络上获得较好的干预效果，UC算法从线性规划的角度出发，利用迭代的思想获取干预策略。该算法依旧直接以πU为衡量准则即公式（6），其约束条件为公式（7）：

（6）

其中，v表示对控制基因位g应用策略a∈{0，1}后最终进入稳态分布中状态j的概率;pij（ag）表示对状态i的控制基因位g应用策略a后到状态j的转移概率。

最终对于状态x采用策略a的概率μ*（a|x）可根据公式（8）获得：

μ*（a|x）=（8）

其中v是公式（6）得到解时的最优值。根据公式（8）可得整个网络的UC干预策略，且其属于MD。

1.2 约束性算法

1.2.1 conSSD算法和conCSSD算法  集合D中，仍然存在一些状态隐含着认知风险，但它们与病理无直接联系。若在稳态分布中能对其概率和加以控制便可降低潜在的风险。conSSD算法和conCSSD算法分别在SSD算法、CSSD算法基础上对此加以了约束，并设定可接受的最大风险值为λ，且πDa≤λ其中π=

π-

π。最终获取的干预策略仍属于MD。

1.2.2 PC算法  PC算法是在UC算法的基础上对Da中状态的稳态概率加以约束，其公式见（9）（10）。

式中V为最大风险值，j表示存在认知风险的任一状态。PC算法获取的最佳干预策略属于MS。

（9）

2 总结

设计干预策略用以改善网络的长期动态行为一直是网络干预领域所关注的。本文分析了各外部干预算法的设计理念，首先，发现MFPT算法、BOA算法、SSD算法、CSSD算法、UC算法属于非约束性算法;conSSD、conCSSD、PC算法属于约束性算法。其次，MFPT算法侧重于减少到 的时间，延长到 的时间;BOA算法侧重于减少到期望吸引子的时间;SSD、CSSD算法则以稳态分布为出发点;UC算法选择从线性规划的角度出发;conSSD、conCSSD以及PC算法则分别基于SSD算法、CSSD算法、UC算法对存在认知风险的状态概率加以约束。再者，这八种算法虽设计角度不一致，但却以减少稳态分布中不期望状态的概率为共同目标。

参考文献：

[1]G Vahedi，B Faryabi，J Chamberland，et al.Intervention in gene regulatory networks via a stationary mean-first-passage-time control policy[J].Biomedical Engineering， IEEE Transactions on，2008，55（10）：2319-2331.

[2]Qian X，Dougherty ER.Validation of gene regulatory network inference based on controllability[J].Frontiers in Genetics，2013，4（4）：272.

[3]Qian X，Dougherty ER.Effect of Function Perturbation on the Steady-State Distribution of Genetic Regulatory Networks： Optimal Structural Intervention[J].IEEE Transactions on Signal Processing，2008，56（10）：4966-4976.

[4]Xiao Y，Dougherty ER.The impact of function perturbations in boolean networks[J].Bioinformatics，2007，23（10）：1265-1273.

[5]Shmulevich I，Dougherty ER，Zhang W.Control of stationary behavior in probabilistic boolean networks by means of structural intervention[J].Journal of Biological Systems，2002，10（04）：431-445.