一種改進的時延動態(tài)貝葉斯網(wǎng)絡構建算法研究

劉飛

(寶雞文理學院 物理與光電技術學院，陜西 寶雞 721016)

?

一種改進的時延動態(tài)貝葉斯網(wǎng)絡構建算法研究

劉飛

(寶雞文理學院 物理與光電技術學院，陜西 寶雞 721016)

從大規(guī)模實驗數(shù)據(jù)中構建的網(wǎng)絡可以反向發(fā)掘網(wǎng)絡結點之間潛在的相互作用關系，可以更深層次解釋網(wǎng)絡結點間復雜的作用機理，因此產(chǎn)生了很多網(wǎng)絡構建的理論建模方法。在一些實驗數(shù)據(jù)中某個時間點的樣本值表達減少或者被敲除，這會影響網(wǎng)絡構建的精度。為了克服這個問題提出了相對變化率的策略來識別結點間潛在的作用關系。在時序?qū)嶒灁?shù)據(jù)中，用策略融合時延動態(tài)貝葉斯方法來進行網(wǎng)絡構建?？梢钥s減貝葉斯的搜索空間，以此來獲得較高的網(wǎng)絡構建性能和精度。DREAM(Dialogue for Reverse Engineering Assessments and Methods)競賽項目最早被提出用來嚴格檢測結點間網(wǎng)絡構建模型方法的性能和優(yōu)劣。在這個數(shù)據(jù)集上推測出來的網(wǎng)絡在AUROC(area under the ROC curve)和AUPR (area under the precision recall curve)指標上和其它方法進行了比較，實驗結果驗證算法在網(wǎng)絡構建過程中總體性能略勝一籌。

復雜網(wǎng)絡；網(wǎng)絡構建；相對變化率；時延；貝葉斯網(wǎng)絡

0 引 言

隨著高通量數(shù)據(jù)的產(chǎn)生和計算機技術的發(fā)展，對這些大數(shù)據(jù)的處理和挖掘已經(jīng)成為研究的熱點。一個網(wǎng)絡可以抽象為由結點和邊組成的一個圖，結點表示現(xiàn)實網(wǎng)絡中的一些研究對象，邊可以理解為結點之間潛在的相互作用關系。如在疾病基因網(wǎng)絡中，一些疾病基因可以看成網(wǎng)絡中的結點，基因之間的相互作用關系可以理解為網(wǎng)絡中的邊，那么就可以通過網(wǎng)絡的手段知道哪些基因作用關系密切，可能會成為致病因素，這就對藥物設計和疾病治療起到一定的理論意義。因此構建的網(wǎng)絡可以系統(tǒng)地研究網(wǎng)絡中結點之間的調(diào)配關系，為深入挖掘結點之間的復雜關系及作用機制提供理論模型。

現(xiàn)今已經(jīng)誕生了很多數(shù)學模型和計算機方法來推斷網(wǎng)絡構建，這些模型方法主要包括布爾網(wǎng)絡模型(Boolean networks)[1]，常微分方程模型[2]，信息論模型[3-4]，線性規(guī)劃[5]模型和貝葉斯網(wǎng)絡模型[6-7]。這些方法能夠?qū)W(wǎng)絡系統(tǒng)動態(tài)行為提供更深層次的理解，但是構建方法的精度對模型中參數(shù)的依賴性非常大，且算法的時間復雜度非常大，這就使得構建大規(guī)模網(wǎng)絡變得異常困難[8]。由于基因調(diào)控過程的復雜性、調(diào)控的方向性、網(wǎng)絡的規(guī)模性以及基因表達數(shù)據(jù)的噪聲等因素的影響，這些都會影響基因調(diào)控網(wǎng)絡構建性能。如基于互信息的方法不能檢測網(wǎng)絡的方向，不能區(qū)分直接和間接調(diào)控；基于優(yōu)化模型的方法很難解決高維低樣本數(shù)據(jù)；基于貝葉斯網(wǎng)絡的方法具有較高的計算復雜度，且很難處理大規(guī)模網(wǎng)絡等。如何克服這些模型和方法中的缺點，是基因調(diào)控網(wǎng)絡構建方法提高其性能的關鍵所在。

貝葉斯網(wǎng)絡模型是一種圖形概率模型，利用貝葉斯規(guī)則建立結點間的聯(lián)合概率分布來構造調(diào)控網(wǎng)絡的。貝葉斯網(wǎng)絡模型是基于統(tǒng)計理論的，并且能夠應用到各種類型的生物數(shù)據(jù)中，因此能夠捕捉到表達數(shù)據(jù)中固有的噪聲，而且準許在決定結點間相互作用關系的過程中可以利用貝葉斯規(guī)則來結合一些先驗生物學知識。動態(tài)貝葉斯網(wǎng)絡(DBN)是貝葉斯網(wǎng)絡的擴展版，既可以使用穩(wěn)態(tài)數(shù)據(jù)，也可以應用到基因表達時間序列數(shù)據(jù)中。當構建的調(diào)控網(wǎng)絡包含大量的基因結點時，DBN需要花費大量時間來學習條件依賴關系。為此我們提出了一種數(shù)據(jù)相對變化率的策略來預處理隨機結點數(shù)據(jù)，以此來識別出網(wǎng)絡中一些關鍵的結點，在這個基礎之上我們再采用時延的動態(tài)貝葉斯方法和一些先驗知識來構建網(wǎng)絡，所構建網(wǎng)絡的優(yōu)劣用性能指標AUPR和AUROC值來評估。試驗結果驗證我們的方法取得了良好的網(wǎng)絡構建性能，在網(wǎng)絡的構建準確率和精度方面都取得了較好的結果。

1 理論方法

1.1 相對變化率

網(wǎng)絡中的邊表示結點之間潛在的相互作用關系，在給定的網(wǎng)絡中，一個結點的表達水平值發(fā)生變化會影響那些和它有相互作用關系的結點的表達值。如果結點在整個網(wǎng)絡中扮演了一個非常重要的角色，那么它的變化會引起其周圍近鄰結點的變化，我們也稱這些點為中心結點或者關鍵結點(Hub Node)。因此一些結點值的表達類型不同(如原態(tài)數(shù)據(jù)，表達缺失數(shù)據(jù)，表達值減小數(shù)據(jù)和帶有噪聲的數(shù)據(jù)等)就會影響網(wǎng)絡構建的精度。這里我們引入相對變化率的數(shù)據(jù)預處理策略來識別出一些中心結點，為進一步網(wǎng)絡構建減小時間復雜度。

對于給定實驗數(shù)據(jù)集中的每一個結點數(shù)據(jù)，我們以它的原態(tài)表達數(shù)據(jù)作為參照點，然后計算每個數(shù)據(jù)結點的相對變化率，數(shù)據(jù)的相對變化率公式定義如下：

i=1,…,n;j=1,…,n

其中Ri,j表示結點j在結點i表達值敲除情況下的相對變化率，Gi,j表示結點j在結點i表達值敲除情況下的表達值，Wj表示結點j原態(tài)表達值，Max(G:,j)-Min(G:,j)表示結點j對所有結點表達值變化范圍，如果i=j，則相對變化率Ri,j為零。

如果結點的變化率大于給定的一個閾值，我們就認為這個結點是關鍵結點，在整個網(wǎng)絡中扮演非常重要的角色。當結點的表達值相對于參照結點的變化小于給定的一個閾值時，我們認為它是噪聲，把它從潛在的調(diào)控結點表單中剔除。如圖1所示，計算結點1到10對于結點1的相對變化率，其中結點2,4,5,7,8明顯高出閾值，那么我們就認為這些節(jié)點潛在的被結點1調(diào)控，結點1在整個網(wǎng)絡中是一個關鍵結點。

圖1 相對變率的事例框圖

1.2 動態(tài)貝葉斯網(wǎng)絡

圖2 動態(tài)貝葉斯網(wǎng)絡

1.3 時延動態(tài)貝葉斯網(wǎng)絡

K Murphy[11-12]提出了動態(tài)貝葉斯的表示方法，網(wǎng)絡推斷及結構學習，但是這個模型有兩個主要的缺陷。第一，這個算法的時間復雜度非常大，對于網(wǎng)絡中某結點，其父節(jié)點可能是剩余結點的一個或者多個，其算法的時間復雜度會隨著網(wǎng)絡規(guī)模成指數(shù)級增長。由于計算的時間太長一般認為一個結點的父節(jié)點數(shù)量限制在30個以內(nèi)。第二，這個算法沒有考慮相關性的延時問題，這會降低網(wǎng)絡構建的精度。

為了克服這個缺陷，Conzen[7]74提出了基于時序數(shù)據(jù)的帶有時延的動態(tài)貝葉斯網(wǎng)絡構建算法，這種方法能夠有效地降低算法的時間復雜度和提高算法的準確性。在網(wǎng)絡中相互作用的兩個結點，它們的時序表達值都有一個相應的延時趨勢或者同時發(fā)生變化，那么用這種方法就可以限制一個結點的父節(jié)點的數(shù)量，以此來降低算法的時間復雜度。還發(fā)現(xiàn)在生物分子網(wǎng)絡中，調(diào)控結點和被調(diào)控結點之間都會存在一個轉(zhuǎn)錄時延周期，那么結點表達值的延遲就代表了生物相對延時周期。這種方法考慮了結點變量間的相對關系，借助表達值的變化來估計調(diào)控結點和被調(diào)控結點之間的關系。那么用這種帶有延遲的動態(tài)貝葉斯方法就可以直接從時序的基因表達數(shù)量識別出其對應的網(wǎng)絡。

在我們的方法中，首先用相對變化率從時序數(shù)據(jù)中找出那些關鍵的網(wǎng)絡結點，這些結點比其它結點更可能成為其它節(jié)點的父節(jié)點，在生成的網(wǎng)絡中這些結點會扮演非常重要的角色，用相關性給這些關鍵結點先構建出一個調(diào)控網(wǎng)絡。其次用時延的動態(tài)貝葉斯網(wǎng)絡方法再從這些時序數(shù)據(jù)中構建另一個調(diào)控網(wǎng)絡，把兩個網(wǎng)絡中都存在的那些邊保留成為我們構建的最終網(wǎng)絡，用DREAM[13]人工合成數(shù)據(jù)和真實網(wǎng)絡數(shù)據(jù)來對我們的算法進行檢測，證明我們方法的有效性和準確性。

2 結果分析討論

2.1 構建的網(wǎng)絡和標準網(wǎng)絡比對結果

網(wǎng)絡預測的性能可以用如下參數(shù)來評估，用真陽性(true positive, TP)，假陽性(false positiv, FP)，真陰性(true negative, TN)，假陰性(flase negative, FN)，召回率(Recall)也叫真陽性率(true positive rate, TPR)，假陽性率(flase positive rate, FPR)，精確度(Precision)也叫查準率(Positive Predictive Value, PPV)和準確率(accuracy, ACC)來對構建的網(wǎng)絡進行檢測，它們的公式定義如下：TPR=TP/(TP+FN)，F(xiàn)PR=FP/(FP+TN)，PPV=TP/(TP+FP)，ACC=(TP+TN)/(TP+FP+TN+FN)。除了上述指標外還有受試者工作特性曲線(Receiver Operation Characteristic Curve, ROC曲線)和其曲線下的面積(Area under ROC, AUROC)，精度召回率曲線(Precision and Recall Curve, PR曲線)和其曲線下的面積(Area under PR, AUPR)來衡量構建算法的優(yōu)劣性。

我們的方法成功地應用到了人工合成數(shù)據(jù)集上[14-15]，在E.coli數(shù)據(jù)集上，真實網(wǎng)絡有10個結點，10條邊。我們預測出來的網(wǎng)絡共有11條邊，其中7條正確，精度達到70%。在另外一個酵母(yeast)數(shù)據(jù)中，有50個結點，77條邊，我們的方法預測的帶有方向的網(wǎng)絡如圖3所示，其中預測正確的邊有52條，準確率達到了68%。實驗驗證了我們的方法取得了較好的性能。

圖3 50個結點的預測網(wǎng)絡

2.2 相對變化率在網(wǎng)絡構建中的作用

在三個不同的實驗數(shù)據(jù)集上用我們的方法來構建網(wǎng)絡，在10個結點的實驗數(shù)據(jù)集上，只用相對變化率的方法來構建網(wǎng)絡；在50個結點的實驗數(shù)據(jù)集上，用相對變化率結合時延動態(tài)貝葉斯的方法來構建網(wǎng)絡；在100個結點的實驗數(shù)據(jù)集上，只用動態(tài)貝葉斯網(wǎng)絡的方法來構建網(wǎng)絡，以此來測試這三種網(wǎng)絡構建方法的性能。

結果顯示在10個結點和50個結點的網(wǎng)絡構建中效果明顯好于100個節(jié)點的網(wǎng)絡構建，在E.coli數(shù)據(jù)集上構建網(wǎng)絡的效果明顯好于在yeast數(shù)據(jù)集上，具體參數(shù)如表1所示。結果顯示采用了相對變化率策略可以比單獨使用延遲動態(tài)貝葉斯方法取得更高的網(wǎng)絡構建性能，這就可以解釋為什么在100個結點的網(wǎng)絡構建中，AUPR和AUROC值都相對偏低，在10個結點和50個結點的網(wǎng)絡構建中，AUPR和AUROC值都相對偏高。這是因為在100個結點的網(wǎng)絡構建中只采用了延遲的動態(tài)貝葉斯方法，在10個和50個結點的網(wǎng)絡構建中都有相對變率策略的干預，由此可見，相對變化率的策略能提高網(wǎng)絡構建的精度。

為了進一步說明相對變化率策略在網(wǎng)絡構建中所起的作用，在10個結點的數(shù)據(jù)集上分別采用延遲動態(tài)貝葉斯方法，相對變化率策略方法和它們二者結合的方法來構建網(wǎng)絡，這三種網(wǎng)絡構建方法所獲得的AUPR值如圖4所示。實驗結果說明采用相對變化率策略的方法和它們二者相結合的方法性能都優(yōu)于單獨使用時延動態(tài)貝葉斯方法，這充分說明相對變化率策略在網(wǎng)絡構建中起著比較重要的作用。動態(tài)時延貝葉斯網(wǎng)絡構建方法在計算結點潛在調(diào)控的父節(jié)點時，選取范圍偏大導致網(wǎng)絡中有較高的假陽性邊，以致降低了網(wǎng)絡構建的精度，如何把相對變化率策略和時延動態(tài)貝葉斯網(wǎng)絡更好的結合，以提高網(wǎng)絡構建的精度將是我們將來繼續(xù)研究的問題。

表1 預測三種網(wǎng)絡取得的參數(shù)性能

圖4 三種不同方法在三個網(wǎng)絡上的AUPR值比較圖

3 結束語

文中提出了一種數(shù)據(jù)相對變化率的策略來預處理隨機結點數(shù)據(jù)，以此來識別出網(wǎng)絡中一些關鍵的結點，為后續(xù)的網(wǎng)絡構建提供幫助，這些關鍵結點在生成的網(wǎng)絡中會扮演一個非常重要的角色，它們會潛在地調(diào)控網(wǎng)絡中的其它結點。在這個基礎之上我們再采用時延的動態(tài)貝葉斯方法和一些先驗知識來構建網(wǎng)絡，所構建網(wǎng)絡的優(yōu)劣用性能指標AUPR和AUROC值來評估。試驗結果驗證我們的方法取得了良好的網(wǎng)絡構建性能，在網(wǎng)絡的構建準確率和精度都取得了較好的結果。如何把相對變化率策略和時延動態(tài)貝葉斯網(wǎng)絡更好地結合，以提高網(wǎng)絡構建的精度將是我們將來繼續(xù)研究的問題。

[1] SHMULEVICH I,DOUGHERTY E R, KIM S, et al. Probabilistic Boolean networks: a rule-based uncertainty model for gene regulatory networks[J]. Bioinformatics, 2002, 18(2): 261-274.

[2] CASTELO R, ROVERATO A. Reverse engineering molecular regulatory networks from microarray data with qp-graphs[J]. Journal of Computational Biology, 2009, 16(2): 213-227.

[3] MEYER P E, LAFITTE F,BONTEMPI G. AR/bioconductor package for inferring large transcriptional networks using mutual information[J]. BMC bioinformatics, 2008, 9(1): 461.

[4] ZHANG X, ZHAO X M, HE K, et al. Inferring gene regulatory networks from gene expression data by path consistency algorithm based on conditional mutual information[J]. Bioinformatics, 2012, 28(1): 98-104.

[5] SAKAMOTO E, IBA H. Inferring a system of differential equations for a gene regulatory network by using genetic programming[C]. Evolutionary Computation, 2001. Proceedings of the 2001 Congress on. IEEE, 2001, 1: 720-726.

[6] YOUNG W C, RAFTERY A E, YEUNG K Y. Fast bayesian inference for gene regulatory networks using ScanBMA[J]. BMC Systems Biology, 2014, 8(1): 47.

[7] ZOU M, CONZEN S D. A new dynamic bayesian network (DBN) approach for identifying gene regulatory networks from time course microarray data[J]. Bioinformatics, 2005, 21(1): 71-79.

[8] MADHAMSHETTIWAR P B, MAETSCHKE S R, DAVIS M J, et al. Gene regulatory network inference: evaluation and application to ovarian cancer allows the prioritization of drug targets[J]. Genome Medicine, 2012, 4(5): 1-16.

[10] FRIEDMAN N, MURPHY K,RUSSELL S. Learning the structure of dynamic probabilistic networks[C]. Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann Publishers Inc., 1998: 139-147.

[11] MURPHY K P. Dynamic bayesian networks: representation, inference and learning[D].University of California, Berkeley, 2002.

[12] MURPHY K, MIAN S. Modelling gene expression data using dynamic Bayesian networks[R]. Technical Report, Computer Science Division,University of California, Berkeley, CA, 1999.

[13] MARBACH D, SCHAFFTER T, MATTIUSSI C, et al. Generating realistic in silico gene networks for performance assessment of reverse engineering methods[J]. Journal of Computational Biology, 2009, 16(2): 229-239.

[14] MARBACH D, PRILL R J, SCHAFFTER T, et al. Revealing strengths and weaknesses of methods for gene network inference[J]. Proceedings of the National Academy of Sciences, 2010, 107(14): 6286-6291.

[15] PRILL R J, MARBACH D, SAEZ-RODRIGUEZ J, et al. Towards a rigorous assessment of systems biology models: the DREAM3 challenges[J]. PloS One, 2010, 5(2):9202.

The Study on an Improved Time-delayed Dynamic Bayesian Network Construction Algorithm

Liu Fei

(Institute of Physics and Optoelectronics Technology, Baoji University of Arts and Science, Baoji Shaanxi 721016, China)

Networks constructed from large-scale experimental data can reversely explore potential interaction among network nodes and help us understand at a deeper level the complex functional mechanism among these nodes. In this context, many theoretical approaches have been presented for network construction. The reduction or knockout of sample values at a certain time point in some experimental data would affect the accuracy of network construction. To solve this problem, we present the strategy of relative variation ratio to recognize potential interaction among the nodes. In the time sequence experimental data, this strategy and time-delayed dynamic Bayesian method are integrated for network construction. Our approach can reduce Bayesian searching space so as to obtain better performance and accuracy in network construction. The Dialogue for Reverse Engineering Assessments and Methods (DREAM) competitive event was first proposed for rigorous assessment of the performance and advantages/disadvantages of modeling methods for inter-node network construction. The network speculated with our data set is compared with other methods in two metrics: area under the ROC curve (AUROC) and area under the precision-recall curve (AUPR). Experimental results show that overall performance of our algorithm is slightly better than others in the process of network construction.

complex network; network construction; relative variation ratio; time delay; Bayesian network

國家自然科學基金(11547247,11105003);寶雞市科技計劃項目 (15RKX-1-5-18,14GYGG-5-2);寶雞文理學院科研項目(ZK16009,ZK16028)資助;陜西省科技攻關計劃項目(2014K08-17)；陜西省教育廳科研計劃項目(15JK1043)。

10.3969/j.issn.1000-3886.2016.04.011

TP391

A

1000-3886(2016)04-0033-03

劉飛，男(1981-)，陜西榆林人，碩士，講師，主要研究方向為復雜網(wǎng)絡和數(shù)據(jù)挖掘。

定稿日期: 2015-12-28