幾種外部干預算法的比較

崔振東 劉文斌

摘? ?要：網絡干預始終是基因調控網絡研究的終極目標。本文關注于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.