幾種外部干預(yù)算法的比較

崔振東 劉文斌

摘? ?要：網(wǎng)絡(luò)干預(yù)始終是基因調(diào)控網(wǎng)絡(luò)研究的終極目標。本文關(guān)注于8種不改變調(diào)控規(guī)則的干預(yù)算法，對這些算法的設(shè)計角度進行了分析，發(fā)現(xiàn)MFPT、BOA、SSD、CSSD、UC這五種算法未對存在認知風(fēng)險的狀態(tài)加以約束，而conSSD算法、conCSSD算法、PC算法對此加以了限制;其次，這8種算法雖從不同的角度進行干預(yù)策略的設(shè)計，但所得干預(yù)策略的應(yīng)用均能改善網(wǎng)絡(luò)的長期動態(tài)行為。

關(guān)鍵詞：外部干預(yù)算法;干預(yù)策略;穩(wěn)態(tài)分布;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

基因調(diào)控網(wǎng)絡(luò)的長期動態(tài)行為在某種層面上反映了細胞的狀態(tài)（如癌變），這往往是由關(guān)鍵基因的表達值決定的，該關(guān)鍵基因也稱為目標基因。整個狀態(tài)空間S可根據(jù)該基因在布爾機制下的表達值分為：期望狀態(tài)集D、不期望狀態(tài)集U，在D中仍存在一些模棱兩可的狀態(tài)Da，它們雖與不期望狀態(tài)無直接關(guān)系，但卻存在認知風(fēng)險。特定的干預(yù)可使網(wǎng)絡(luò)動態(tài)行為沿期望方向發(fā)展，并規(guī)避該風(fēng)險，進而改變細胞狀態(tài)。然而生物學(xué)中普遍存在一種情況：一個基因或蛋白質(zhì)的激活（抑制）可能比其他基因或蛋白質(zhì)更容易導(dǎo)致一個特定的細胞功能狀態(tài)或顯型的產(chǎn)生[1]。選出最佳干預(yù)基因并制定相應(yīng)的干預(yù)策略便構(gòu)成了干預(yù)的兩大元素，且二者均是基于推理網(wǎng)絡(luò)獲取的，其在原始網(wǎng)絡(luò)上的作用效果將直接反映是否推理出網(wǎng)絡(luò)的核心骨架，錢曉寧將此作為了評估推理網(wǎng)絡(luò)有效性的一個衡量準則[2]。

干預(yù)分為結(jié)構(gòu)干預(yù)和外部干預(yù)，結(jié)構(gòu)干預(yù)是一種從本質(zhì)上改變狀態(tài)轉(zhuǎn)移路徑的干預(yù)方法。它通過改變網(wǎng)絡(luò)調(diào)控規(guī)則來達到改善穩(wěn)態(tài)分布的效果[3-5]。外部干預(yù)則通過是否翻轉(zhuǎn)當前狀態(tài)的控制基因位來改善穩(wěn)態(tài)分布，其網(wǎng)絡(luò)結(jié)構(gòu)并未發(fā)生變化[1]。本文關(guān)注于外部干預(yù)的幾種典型算法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）。從干預(yù)策略的設(shè)計角度對算法進行了分析1 外部干預(yù)算法

干預(yù)算法主要用來獲取干預(yù)基因所對應(yīng)的干預(yù)策略，這又可分為三種：馬爾科夫策略MM、平穩(wěn)策略MS、平穩(wěn)確定策略MD。若uk∈MM，則uk發(fā)生的概率與時間和當前狀態(tài)有關(guān);若uk∈MS，則uk發(fā)生的概率與當前狀態(tài)有關(guān)，且對于當前狀態(tài)x采用策略a的概率為u（a∣x）∈[0，1]，a=1表示對當前狀態(tài)的控制基因位翻轉(zhuǎn)，翻轉(zhuǎn)后狀態(tài)記為，反之不翻轉(zhuǎn);若uk∈MD，則uk發(fā)生的概率與當前狀態(tài)有關(guān)，且u（a∣x）=0或1。

1.1非約束性算法

1.1.1 MFPT算法? MFPT算法設(shè)計是基于網(wǎng)絡(luò)的狀態(tài)轉(zhuǎn)移的。根據(jù)目標基因的值可將狀態(tài)轉(zhuǎn)移矩陣表示為以下情況P=。該算法的核心思想是減少停留在不期望狀態(tài)的時間，增加停在期望狀態(tài)的時間。其最終得到的干預(yù)策略屬于MD。

根據(jù)公式（1）可計算出MFPT向量KD和KU

其中，e是由1組成的一個列向量，KD表示D中各狀態(tài)首次到U的時間集合，KU表示U中各狀態(tài)首次到D的時間集合。

為了盡可能早的到達期望狀態(tài)以及離開不期望狀態(tài)。MFPT定義了以下準則：若狀態(tài)x∈U，則判斷KD（x）- KD（）與閾值λ的關(guān)系;若狀態(tài)x∈D，則判斷KU（）- KU（x）與閾值λ的關(guān)系。前者是縮短到達D的時間，后者則是延長到達U的時間。通常情況下，我們?nèi)￠撝郸?0。根據(jù)該準則可決定當前狀態(tài)x的控制基因位是否翻轉(zhuǎn)，從而得到最終干預(yù)策略。

1.1.2 BOA算法? 到達期望狀態(tài)并不代表該路徑的頂端是期望吸引子。BOA算法注意到基因調(diào)控網(wǎng)絡(luò)的長期動態(tài)行為主要由吸引子決定。故該算法設(shè)計從吸引子出發(fā)，其核心思想是減少到達期望吸引子的時間，增加到達不期望吸引子的時間。其準則如公式（2）（3）所示：

其中，B（x）、B（）分別表示狀態(tài)x、最終歸屬的吸引子（環(huán)），dD（x）、dD（）分別表示狀態(tài)x、到最近期望狀態(tài)的距離，dU（x）、dU（）分別表示狀態(tài)x、到最近不期望狀態(tài)的距離。

根據(jù)以上準則可得相應(yīng)的干預(yù)策略，且其屬于MD。該準則保證了當前狀態(tài)盡可能的進入期望吸引子，若無法進入，則盡可能早的到達期望狀態(tài)。

1.1.3 SSD算法? 以上兩種算法雖均能通過干預(yù)策略改變網(wǎng)絡(luò)的長期動態(tài)行為，但其獲取干預(yù)策略的準則并非直接以穩(wěn)態(tài)分布中不期望狀態(tài)的概率和πU的變化來制定的。SSD算法則將此直接作為衡量準則，其核心思想是干預(yù)當前狀態(tài)x是否能減少πU。根據(jù)公式（4）可得對狀態(tài)x的控制基因位干預(yù)后的新穩(wěn)態(tài)分布πx。

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

其中π、πx分別表示干預(yù)前的穩(wěn)態(tài)分布以及狀態(tài)x在該分布中所對應(yīng)的概率，P、P分別表示狀態(tài) x、在轉(zhuǎn)移概率矩陣P中所對應(yīng)的行向量，I表示單位矩陣。矩陣Z通常被稱為基礎(chǔ)矩陣。

SSD算法中干預(yù)策略的設(shè)計主要依據(jù)πU的變化，故其衡量準則如下：對狀態(tài)x、，若πU≤min（π，π），則x、的控制基因位均不翻轉(zhuǎn);若 π≤π且π>min（π，π），則x的控制基因位翻轉(zhuǎn)，的控制基因位不翻轉(zhuǎn);若π≤π且π>min（π，π），則的控制基因位翻轉(zhuǎn)，x的控制基因位不翻轉(zhuǎn)。

由此SSD算法可獲得相應(yīng)的干預(yù)策略。且其屬于MD。但運用準則前依據(jù)公式（4）求出的πx并不能保證π≤π且π>min（π，π）。這在CSSD算法中得以實現(xiàn)。

1.1.4 CSSD算法? CSSD算法是通過迭代的思想得到干預(yù)策略的，每次迭代，它只從未實行干預(yù)策略的狀態(tài)出發(fā)，根據(jù)公式（5），從中選取πU最大的狀態(tài)的干預(yù)策略作為此次迭代的結(jié)果。當πU≤0時，迭代結(jié)束。整個網(wǎng)絡(luò)的干預(yù)策略即可得到且屬于MD。

π=π-π（5）

其中，π求法同SSD算法中。該算法能夠保證每次迭代的結(jié)果π<π且應(yīng)用整個干預(yù)策略后穩(wěn)態(tài)分布中不期望狀態(tài)的概率和是減少的。

1.1.5 UC算法? 為在原始網(wǎng)絡(luò)上獲得較好的干預(yù)效果，UC算法從線性規(guī)劃的角度出發(fā)，利用迭代的思想獲取干預(yù)策略。該算法依舊直接以πU為衡量準則即公式（6），其約束條件為公式（7）：

（6）

其中，v表示對控制基因位g應(yīng)用策略a∈{0，1}后最終進入穩(wěn)態(tài)分布中狀態(tài)j的概率;pij（ag）表示對狀態(tài)i的控制基因位g應(yīng)用策略a后到狀態(tài)j的轉(zhuǎn)移概率。

最終對于狀態(tài)x采用策略a的概率μ*（a|x）可根據(jù)公式（8）獲得：

μ*（a|x）=（8）

其中v是公式（6）得到解時的最優(yōu)值。根據(jù)公式（8）可得整個網(wǎng)絡(luò)的UC干預(yù)策略，且其屬于MD。

1.2 約束性算法

1.2.1 conSSD算法和conCSSD算法? 集合D中，仍然存在一些狀態(tài)隱含著認知風(fēng)險，但它們與病理無直接聯(lián)系。若在穩(wěn)態(tài)分布中能對其概率和加以控制便可降低潛在的風(fēng)險。conSSD算法和conCSSD算法分別在SSD算法、CSSD算法基礎(chǔ)上對此加以了約束，并設(shè)定可接受的最大風(fēng)險值為λ，且πDa≤λ其中π=

π-

π。最終獲取的干預(yù)策略仍屬于MD。

1.2.2 PC算法? PC算法是在UC算法的基礎(chǔ)上對Da中狀態(tài)的穩(wěn)態(tài)概率加以約束，其公式見（9）（10）。

式中V為最大風(fēng)險值，j表示存在認知風(fēng)險的任一狀態(tài)。PC算法獲取的最佳干預(yù)策略屬于MS。

（9）

2 總結(jié)

設(shè)計干預(yù)策略用以改善網(wǎng)絡(luò)的長期動態(tài)行為一直是網(wǎng)絡(luò)干預(yù)領(lǐng)域所關(guān)注的。本文分析了各外部干預(yù)算法的設(shè)計理念，首先，發(fā)現(xiàn)MFPT算法、BOA算法、SSD算法、CSSD算法、UC算法屬于非約束性算法;conSSD、conCSSD、PC算法屬于約束性算法。其次，MFPT算法側(cè)重于減少到 的時間，延長到 的時間;BOA算法側(cè)重于減少到期望吸引子的時間;SSD、CSSD算法則以穩(wěn)態(tài)分布為出發(fā)點;UC算法選擇從線性規(guī)劃的角度出發(fā);conSSD、conCSSD以及PC算法則分別基于SSD算法、CSSD算法、UC算法對存在認知風(fēng)險的狀態(tài)概率加以約束。再者，這八種算法雖設(shè)計角度不一致，但卻以減少穩(wěn)態(tài)分布中不期望狀態(tài)的概率為共同目標。

參考文獻：

[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.