崔振東 劉文斌

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

關(guān)鍵詞：外部干預(yù)算法;干預(yù)策略;穩(wěn)態(tài)分布;MFPT;BOA;SSD;CSSD;UC

中圖分類(lèi)號(hào)：O157.4? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? DOI：10.3969/j.issn.1006-1959.2018.21.004

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

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

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

1.1非約束性算法

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

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

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

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

1.1.2 BOA算法? 到達(dá)期望狀態(tài)并不代表該路徑的頂端是期望吸引子。BOA算法注意到基因調(diào)控網(wǎng)絡(luò)的長(zhǎng)期動(dòng)態(tài)行為主要由吸引子決定。故該算法設(shè)計(jì)從吸引子出發(fā)，其核心思想是減少到達(dá)期望吸引子的時(shí)間，增加到達(dá)不期望吸引子的時(shí)間。其準(zhǔn)則如公式（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ù)以上準(zhǔn)則可得相應(yīng)的干預(yù)策略，且其屬于MD。該準(zhǔn)則保證了當(dāng)前狀態(tài)盡可能的進(jìn)入期望吸引子，若無(wú)法進(jìn)入，則盡可能早的到達(dá)期望狀態(tài)。

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

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

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

SSD算法中干預(yù)策略的設(shè)計(jì)主要依據(jù)πU的變化，故其衡量準(zhǔn)則如下：對(duì)狀態(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。但運(yùn)用準(zhǔn)則前依據(jù)公式（4）求出的πx并不能保證π≤π且π>min（π，π）。這在CSSD算法中得以實(shí)現(xiàn)。

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

π=π-π（5）

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

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

（6）

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

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

μ*（a|x）=（8）

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

1.2 約束性算法

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

π-

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

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

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

（9）

2 總結(jié)

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

參考文獻(xiàn)：

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