饒臻, 鄭明

(1.廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院, 廣西 南寧 530004;2.梧州學(xué)院 大數(shù)據(jù)與軟件工程學(xué)院, 廣西 梧州 543003)

0 引言

隨著人類基因組計(jì)劃的開始,生物信息學(xué)作為一門新的交叉學(xué)科而興起，內(nèi)容包括對(duì)分子生物學(xué)數(shù)據(jù)庫的研究和推理、基因之間的調(diào)控關(guān)系研究等。研究基因之間的調(diào)控關(guān)系對(duì)生物醫(yī)藥的研究有著重大意義,例如人類常見的疾病的發(fā)生歸根溯源都是基因的異常表達(dá)結(jié)果,且在基因之間存在促進(jìn)和抑制的調(diào)控關(guān)系,調(diào)控與被調(diào)控的基因之間構(gòu)成了基因調(diào)控網(wǎng)絡(luò)[1]。傳統(tǒng)的通過實(shí)驗(yàn)對(duì)比進(jìn)行基因調(diào)控網(wǎng)絡(luò)驗(yàn)證的方法的耗費(fèi)巨大,因此利用現(xiàn)有的實(shí)驗(yàn)樣本中的基因表達(dá)數(shù)據(jù)，使用機(jī)器學(xué)習(xí)或統(tǒng)計(jì)分析的方法構(gòu)建基因調(diào)控網(wǎng)絡(luò)，取得對(duì)生物研究者有一定指導(dǎo)作用的成果,成為許多研究者廣泛關(guān)注的問題[2]。

貝葉斯網(wǎng)絡(luò)[3]模型是一種可以反映變量之間的依賴關(guān)系的網(wǎng)絡(luò)模型,具有可以進(jìn)行圖形化表示,因果關(guān)系清楚,可以進(jìn)行不確定推理等優(yōu)點(diǎn),在相當(dāng)多的領(lǐng)域都有著廣泛的應(yīng)用,研究者們先后將各個(gè)領(lǐng)域的問題引入到貝葉斯網(wǎng)絡(luò)模型中求解,取得了不錯(cuò)的成果。本文采用貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)來構(gòu)建基因調(diào)控網(wǎng)絡(luò),而學(xué)習(xí)一個(gè)由離散變量組成的貝葉斯網(wǎng)絡(luò)的最優(yōu)結(jié)構(gòu)在幾乎所有情形下都是NP問題,其網(wǎng)絡(luò)空間隨著節(jié)點(diǎn)個(gè)數(shù)的增加呈指數(shù)增加,所以只能用啟發(fā)搜索算法來尋找接近最優(yōu)的網(wǎng)絡(luò),目前主流方向有以下3種:①基于約束的統(tǒng)計(jì)分析方法；②基于評(píng)分搜索的方法；③前述2種算法結(jié)合的混合搜索算法。

基于統(tǒng)計(jì)分析的方法通過檢測(cè)互信息值的方式判定在網(wǎng)絡(luò)中節(jié)點(diǎn)的邊是否存在并構(gòu)建有向圖,如最早的SGS[4]算法、改進(jìn)后的PC[5]算法、FCNSLA[6]算法等。該類學(xué)習(xí)算法需要依次判別各節(jié)點(diǎn)之間的條件獨(dú)立性,隨著網(wǎng)絡(luò)規(guī)模增加,時(shí)間復(fù)雜度指數(shù)級(jí)增長(zhǎng),因此該類算法只能適用于較小的稀疏網(wǎng)絡(luò)。

基于評(píng)分搜索的方法則使用啟發(fā)式搜索來構(gòu)建有向圖,搜索算法和評(píng)分函數(shù)決定了生成網(wǎng)絡(luò)的準(zhǔn)確度,目前常用的經(jīng)典搜索算法有爬山(Hill Climbing)算法,需要提供節(jié)點(diǎn)序的K2[7]算法等;評(píng)分函數(shù)有BIC[8]、BDe[9]、MDL[10]等。近幾年,評(píng)分搜索廣泛使用了基于仿生學(xué)理論的優(yōu)化方法,如蟻群算法[11]、人工免疫算法等[12]。

上述2種方法各有其缺點(diǎn),適用場(chǎng)景也有限，因此,混合學(xué)習(xí)的方法成為現(xiàn)今研究的重點(diǎn),此類方法利用獨(dú)立性測(cè)試分析效率較高的優(yōu)勢(shì)來約束搜索空間的大小,然后再用評(píng)分搜索進(jìn)行最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)的尋找,最終完成一個(gè)最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)。第一個(gè)混合學(xué)習(xí)算法是CB[13]算法,通過PC算法確定節(jié)點(diǎn)間的先后順序,之后再使用K2算法對(duì)結(jié)構(gòu)進(jìn)行學(xué)習(xí);MMHC算法[14]是結(jié)合稀疏候選算法思想的另一種經(jīng)典混合學(xué)習(xí)算法,使用MMPC算法構(gòu)建貝葉斯網(wǎng)絡(luò)的搜索結(jié)構(gòu),再用K2算法來確定最優(yōu)的網(wǎng)絡(luò)。已有實(shí)驗(yàn)表明,無論從網(wǎng)絡(luò)的質(zhì)量還是時(shí)間復(fù)雜度上來看,MMHC算法都要較優(yōu)。

本文提出了貝葉斯網(wǎng)絡(luò)的混合學(xué)習(xí)算法構(gòu)建基因調(diào)控網(wǎng)絡(luò)的方法,基于最大信息系數(shù)MIC[15]估算各個(gè)基因變量之間的關(guān)聯(lián)程度并據(jù)此構(gòu)建初始網(wǎng)絡(luò),通過在縮小搜索空間的初始網(wǎng)絡(luò)上進(jìn)行評(píng)分搜索,構(gòu)建更加準(zhǔn)確的基因調(diào)控網(wǎng)絡(luò)，并在規(guī)模較小的單細(xì)胞的蛋白質(zhì)因果表達(dá)網(wǎng)絡(luò)(SACHS)和規(guī)模較大的大腸桿菌表達(dá)網(wǎng)絡(luò)(ECOLI)數(shù)據(jù)集進(jìn)行了不同樣本數(shù)量的多次實(shí)驗(yàn),與Hill Climbing算法、MMHC算法等經(jīng)典算法在3個(gè)性能指標(biāo)上進(jìn)行對(duì)比,驗(yàn)證了該方法的有效性和優(yōu)越性。

1 理論與方法

1.1 貝葉斯網(wǎng)絡(luò)

定義1 貝葉斯網(wǎng)絡(luò)[3]由一個(gè)無環(huán)的有向圖G=(V,E)和一個(gè)條件概率表θ構(gòu)成,在圖G=(V,E)中,V={x1,x2,…,xn},表示一個(gè)網(wǎng)絡(luò)中的隨機(jī)變量集合,xi為隨機(jī)變量。E是以V中隨機(jī)變量的有向邊的集合,如表示網(wǎng)絡(luò)中存在x1到x2的邊,當(dāng)存在xi到xj的邊時(shí),稱xi是xj的父節(jié)點(diǎn)。條件概率表θ則表示了各個(gè)父子節(jié)點(diǎn)之間的條件概率,θi∈θ表示網(wǎng)絡(luò)中隨機(jī)變量xi的條件概率分布。

貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)就是根據(jù)給定的數(shù)據(jù)集D盡可能找出與其最擬合的網(wǎng)絡(luò)結(jié)構(gòu)模型,并將其用有向無環(huán)圖表示的過程。擬合程度的評(píng)分標(biāo)準(zhǔn)以評(píng)分函數(shù)計(jì)算,本文使用的評(píng)分函數(shù)為BDe評(píng)分函數(shù)[9],BDe評(píng)分函數(shù)使用數(shù)據(jù)和先驗(yàn)知識(shí)查找后驗(yàn)概率最大的網(wǎng)絡(luò)結(jié)構(gòu),方便使用且有直觀意義。其定義如下:

(1)

1.2 最大信息系數(shù)

為了盡量消除對(duì)2個(gè)變量進(jìn)行互信息檢測(cè)時(shí)其他變量對(duì)相關(guān)性判定的影響,使用MIC檢測(cè)網(wǎng)絡(luò)中各個(gè)基因節(jié)點(diǎn)的依賴關(guān)系。MIC是針對(duì)2個(gè)具有一定相關(guān)性的變量,利用這2個(gè)變量的散點(diǎn)圖上進(jìn)行某種網(wǎng)格劃分后的近似概率密度分布進(jìn)行互信息計(jì)算并正則化的值,可衡量這2個(gè)向量的相關(guān)程度。相較于互信息,MIC具有更高的準(zhǔn)確度,不受數(shù)據(jù)的影響,也不會(huì)限定在特定的關(guān)聯(lián)函數(shù)種,能夠廣泛應(yīng)用且更有公平性,是一種優(yōu)秀的數(shù)據(jù)關(guān)聯(lián)性的計(jì)算方式。

定義2 對(duì)于一個(gè)含有隨機(jī)變量X和Y的數(shù)據(jù)集D,按i行和j列將一坐標(biāo)平面劃分成網(wǎng)格Gr,i*j

(2)

定義3 有限數(shù)據(jù)集D中的2個(gè)節(jié)點(diǎn)X和Y的特征矩陣M(D)的公式定義為

(3)

式中I*(X,Y,D,i,j)表示有限數(shù)據(jù)集D中變量X和Y在網(wǎng)格Gr中的最大互信息值,也即I*(X,Y,D,i,j)=maxI(X,Y,D|Gr)。I(X,Y,D|Gr)為網(wǎng)格Gr下變量X和Y的互信息值,i和j為使得I(X,Y,D|Gr)達(dá)到最大值的網(wǎng)格的行和列。

定義4 2個(gè)節(jié)點(diǎn)變量X和Y在坐標(biāo)平面的最大信息系數(shù)的定義如下:

M(X,Y|D)=maxi*j

(4)

由于隨機(jī)變量之間的MI存在對(duì)稱性質(zhì),MIC也具有對(duì)稱性。

1.3 融合方法的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)

根據(jù)1.2所述的MIC定義,可知MIC值與2個(gè)隨機(jī)變量之間的依賴程度是正相關(guān)的,也就是說，如果隨機(jī)變量X和Y之間的MIC值越大,二者的依賴程度就越高,說明它們?cè)诰W(wǎng)絡(luò)中可能相連。反之,如果隨機(jī)變量X和Y之間的MIC值越小,則依賴程度越低,當(dāng)2個(gè)變量間的MIC值為0時(shí),表示變量相互獨(dú)立,說明二者在網(wǎng)絡(luò)中不存在調(diào)控關(guān)系。本文提出MIC-TS算法,根據(jù)MIC構(gòu)建初始網(wǎng)絡(luò)以縮小搜索空間并使用優(yōu)化算法進(jìn)行評(píng)分搜索。下面以蛋白質(zhì)因果表達(dá)數(shù)據(jù)集(SACHS)為例說明初始網(wǎng)絡(luò)構(gòu)建的過程。

首先根據(jù)最大信息系數(shù)的定義計(jì)算數(shù)據(jù)集中變量之間的MIC值(表1)并根據(jù)MIC值進(jìn)行初始網(wǎng)絡(luò)的構(gòu)建。

表1 SACHS網(wǎng)絡(luò)的MIC表Tab.1 MIC table of SACHS network

根據(jù)計(jì)算出的MIC值(表1),將每一列(行)中值最大的MIC記為MICmax,如果表中存在變量X和Y的MIC滿足式(5),那么變量X和變量Y在網(wǎng)絡(luò)中可能存在一條邊,表中用粗體標(biāo)注所示。

(5)

式中μ為控制因子。根據(jù)Zhang等的研究[12],對(duì)于此類稀疏圖,μ取值為0.9時(shí),能使得初始網(wǎng)絡(luò)中添加盡量多的可能存在的邊的同時(shí)添加盡量少的無關(guān)邊。

根據(jù)表1的標(biāo)注對(duì)所有滿足式(5)的MIC值從大到小進(jìn)行排序,并根據(jù)大小順序在空?qǐng)DG的節(jié)點(diǎn)間依次添加有向邊以構(gòu)建初始網(wǎng)絡(luò),這樣可以最大限度地將關(guān)聯(lián)性更強(qiáng)的邊添加到網(wǎng)絡(luò)中,邊的方向?yàn)榱泄?jié)點(diǎn)指向行節(jié)點(diǎn),如Erk→Ark,此步驟到所有滿足式(5)的MIC值全部判斷完畢,得到一個(gè)非連通的有向圖為止,在添加有向邊的時(shí)候,有3條規(guī)則:

① 在根據(jù)MIC值向網(wǎng)絡(luò)中添加有向邊的時(shí)候,為了避免出現(xiàn)冗余的邊,如果該節(jié)點(diǎn)有其他有向邊,則跳過該列的判斷。

② 如果在添加有向邊時(shí),該邊的反向邊已經(jīng)存在,則跳過繼續(xù)判斷下一對(duì)滿足條件的節(jié)點(diǎn)對(duì)。

③ 當(dāng)往網(wǎng)絡(luò)中添加有向邊的操作會(huì)導(dǎo)致出現(xiàn)環(huán)時(shí),則跳過該邊繼續(xù)判斷下一對(duì)滿足條件的節(jié)點(diǎn)對(duì)。

根據(jù)以上的加邊規(guī)則構(gòu)造出的有向圖如圖1(a)所示,可發(fā)現(xiàn)使用上述方法并不一定能獲得一個(gè)連通的有向圖,為獲得一個(gè)連通的有向圖,需要繼續(xù)在圖中的連通分量中添加有向邊。

假設(shè)一個(gè)非連通圖G由N個(gè)連通分量組成,記為G={G1,G2,…,Gn},Gi=Vi,Ei,為了將圖G修復(fù)成連通圖,要在N個(gè)連通分量之間添加N-1條邊,具體方式如下:設(shè)有變量集Vi、Vj,為使兩變量集之間相連通,需要在Vi、Vj間添加一條邊,并使其滿足

MICmax(Vi,Vj)=max MIC(Xi,Xj)。

(6)

計(jì)算非連通圖中的2個(gè)連通分量任意節(jié)點(diǎn)的MIC值,并且根據(jù)(6)式選取連通分量之間MIC值最大的2個(gè)連通分量Xi、Xj,在Xi、Xj之間添加一條有向邊,并以此類推直到圖G變?yōu)檫B通圖為止,如圖1(b)所示。

(a) 連通前

(b) 連通后

根據(jù)MIC計(jì)算出的初始網(wǎng)絡(luò)能夠有效的縮減評(píng)分搜索過程中的搜索空間,減少計(jì)算過程中的隨機(jī)性,有效的提高最終網(wǎng)絡(luò)的準(zhǔn)確性。隨后以該初始網(wǎng)絡(luò)作為起點(diǎn),引入Tabu算法的思想和使用BDe評(píng)分函數(shù)進(jìn)行基于評(píng)分的網(wǎng)絡(luò)搜索,在Tabu算法運(yùn)行中,通過將一些可能使得算法產(chǎn)生重復(fù)循環(huán)的解置入禁忌表,提高算法效率跳出局部最優(yōu),生成最終的基因調(diào)控網(wǎng)絡(luò)(圖2),算法如下所示。

算法1 MIC-TS

輸入:矩陣化MIC表MIClist,MICmax,E={},DAG={},數(shù)據(jù)集D

輸出:貝葉斯網(wǎng)絡(luò)DAG

1.For col=1:n

2. For row=1:n

3. IF MIC(Xi,Yj)≥μMICmax(Y)

4. List=sort(MIC(Xi,Yj))//將節(jié)點(diǎn)之間的MIC值從大到小排序

5. FOR len=1:len(list)

6. IF(Xj,Xi)∈Eor isCycle(Xi,Yj) // isCycle(Xi、Yj)檢查Xi、Yj之間連接邊是否會(huì)導(dǎo)致圖中出現(xiàn)環(huán)

7. CONTINUE

8. ELSE

9. add(Xi,Yj) to E//將Xi→Yj的有向邊添加到邊集合中

10.E→BN

11.DAG=tabu(BN,bde,D)//以BN為初始網(wǎng)絡(luò),bde為評(píng)分函數(shù),D為擬合數(shù)據(jù)集進(jìn)行Tabu搜索

12.Return DAG

2 實(shí)驗(yàn)結(jié)果與分析

2.1 實(shí)驗(yàn)準(zhǔn)備

本文中實(shí)驗(yàn)使用R語言的Bnlearn包,通過R語言進(jìn)行編程完成算法進(jìn)行網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)。R語言的Bnlearn包是一個(gè)貝葉斯網(wǎng)絡(luò)工具包,內(nèi)置各種評(píng)分函數(shù)和用于比較的經(jīng)典算法,主要用于貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)和參數(shù)學(xué)習(xí)等方面,本文使用4.6.1版本。實(shí)驗(yàn)的運(yùn)行環(huán)境:Windows10操作系統(tǒng),64bit,Intel i5-9300H處理器,2.40 GHz,8 GB內(nèi)存。

為了便于進(jìn)行性能對(duì)比,實(shí)驗(yàn)采用了已經(jīng)驗(yàn)證過的蛋白質(zhì)因果表達(dá)網(wǎng)絡(luò)(SACHS)和大腸桿菌表達(dá)網(wǎng)絡(luò)(ECOLI)2個(gè)標(biāo)準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集,在Bayesian Network Repository下載標(biāo)準(zhǔn)網(wǎng)絡(luò)的rda文件,隨機(jī)生成相應(yīng)大小的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，見表2。

表2 本文實(shí)驗(yàn)使用數(shù)據(jù)集Tab.2 Data sets are used in this experiment

2.2 實(shí)驗(yàn)指標(biāo)

為了能夠評(píng)估基因調(diào)控網(wǎng)絡(luò)建立的效率,本文將使用F值和漢明距離值(Hamming distance, HD)對(duì)算法生成的網(wǎng)絡(luò)進(jìn)行評(píng)價(jià)以驗(yàn)證算法的有效性。式(7)中,TPR表示真陽率(true positive rate),反映了算法對(duì)標(biāo)準(zhǔn)網(wǎng)絡(luò)中存在的邊的預(yù)測(cè)正確率,TP表示在標(biāo)準(zhǔn)網(wǎng)絡(luò)和算法生成網(wǎng)絡(luò)中均存在的邊數(shù),FN表示在標(biāo)準(zhǔn)網(wǎng)絡(luò)中存在,但是算法并沒有生成的邊數(shù),(8)式中,PPV表示查準(zhǔn)率(sitive predicted value),反映了算法預(yù)測(cè)出來的網(wǎng)絡(luò)邊的準(zhǔn)確度,FP表示標(biāo)準(zhǔn)算法中不存在但是算法生成了的邊數(shù)。由(9)(10)式可知,TP值和F值越高,HD值越低,算法生成的網(wǎng)絡(luò)就越貼近真實(shí)網(wǎng)絡(luò)。

(7)

(8)

(9)

HD=FP+FN。

(10)

2.3 結(jié)果分析

實(shí)驗(yàn)中對(duì)2個(gè)不同大小的標(biāo)準(zhǔn)網(wǎng)絡(luò):小型網(wǎng)絡(luò)SACHS數(shù)據(jù)集,大型網(wǎng)絡(luò)大腸桿菌表達(dá)網(wǎng)絡(luò)數(shù)據(jù)集(ECOLI)進(jìn)行了對(duì)比,將其按照2 000、5 000、1 000的樣本量進(jìn)行采樣,與其他經(jīng)典貝葉斯算法，如 MMHC[14]、Hill Climbing[17]、Banjo[18]、TS[19]等在F值、HD值(漢明距離)、TP(正確邊數(shù))這3個(gè)指標(biāo)進(jìn)行了對(duì)比分析,為使實(shí)驗(yàn)結(jié)果盡量排除隨機(jī)因素影響,對(duì)每個(gè)樣本量都進(jìn)行10次采樣學(xué)習(xí),最后使用10次交叉驗(yàn)證結(jié)果的指標(biāo)的平均值和標(biāo)準(zhǔn)差對(duì)比(表3、4),表中括號(hào)內(nèi)的值為10次實(shí)驗(yàn)結(jié)果的標(biāo)準(zhǔn)差。

表3 MIC-TS與各個(gè)算法在SACHS數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Tab.3 Experimental results of MIC-TS and various algorithms on SACHS data set

對(duì)于規(guī)模較小的SACHS網(wǎng)絡(luò),從表3的數(shù)據(jù)中可以直觀的看出,本文中的MIC-TS算法與其他的結(jié)構(gòu)算法相比,取得了較優(yōu)的實(shí)驗(yàn)結(jié)果。從樣本數(shù)量為2 000、5 000、10 000的實(shí)驗(yàn)結(jié)果可以看出,本文算法的TP與F值與其他算法相比均為最高,HD值為最低,并且在樣本量為2 000時(shí),就學(xué)習(xí)到了與標(biāo)準(zhǔn)網(wǎng)絡(luò)完全相同的網(wǎng)絡(luò)結(jié)構(gòu)(圖3所示),說明了本文算法在該數(shù)據(jù)集上生成的網(wǎng)絡(luò)相較于其他經(jīng)典算法更接近于真實(shí)網(wǎng)絡(luò),相較于Hill Climbing、MMHC算法有明顯的優(yōu)越性;MMHC算法由于其僅在縮減后的搜索空間進(jìn)行搜索,在樣本量不足(2 000、5 000)時(shí),構(gòu)建的搜索空間并不準(zhǔn)確,在減少假陽率的同時(shí),能搜索到的正確邊也會(huì)變少,導(dǎo)致在性能上不如Hill Climbing算法,而樣本量充足時(shí)(10 000),MMHC的性能會(huì)有較大的提升,生成網(wǎng)絡(luò)穩(wěn)定,實(shí)驗(yàn)標(biāo)準(zhǔn)差為0,此時(shí)各項(xiàng)指標(biāo)優(yōu)于Hill Climbing算法。表中的Banjo算法和TS算法在該數(shù)據(jù)集上的實(shí)驗(yàn)也取得了相對(duì)較好的結(jié)果,略低于本文的MIC-TS算法,圖4以條狀圖的形式展示了不同算法在樣本數(shù)量為2 000、5 000、10 000的實(shí)驗(yàn)時(shí)的F值和正確邊數(shù)。另外MIC-TS和TS算法構(gòu)建網(wǎng)絡(luò)的指標(biāo)的對(duì)比證明了初始網(wǎng)絡(luò)的選取會(huì)較大程度的影響算法性能,通過MIC構(gòu)建初始網(wǎng)絡(luò),在一定程度上有效地排除了評(píng)分搜索階段中的隨機(jī)因素的影響,增強(qiáng)了算法的魯棒性。

圖3 MIC-TS算法生成的SACHS網(wǎng)絡(luò)Fig.3 SACHS network generated by MIC-TS

(a) F值

(b) TP

對(duì)于ECOLI網(wǎng)絡(luò)數(shù)據(jù)集,因?yàn)槠鋵儆谶B續(xù)型數(shù)據(jù),需要進(jìn)行預(yù)處理才能使用。將得到的數(shù)據(jù)集進(jìn)行歸一化、標(biāo)準(zhǔn)化,隨后進(jìn)行離散化處理,Yu等[17]研究表明,對(duì)于貝葉斯網(wǎng)絡(luò),三值離散化方法有較高的準(zhǔn)確率和穩(wěn)定性,因此本文采用“均值-方差”的三值離散化方法對(duì)ECOLI數(shù)據(jù)集進(jìn)行處理。

設(shè)隨機(jī)變量i在第j個(gè)數(shù)據(jù)樣本中的取值為xij,變量i在不同數(shù)據(jù)樣本中表達(dá)均值為μi,方差為σi,則對(duì)xij有

(11)

離散化后,取值2表示與實(shí)驗(yàn)中表達(dá)量對(duì)比,出現(xiàn)了高水平表達(dá);取值1表示正常水平表達(dá),取值0表示低水平表達(dá),在處理后的ECOLI數(shù)據(jù)集上進(jìn)行不同樣本量的交叉驗(yàn)證的結(jié)果見表4。

表4 MIC-TS與各個(gè)算法在ECOLI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Tab.4 Experimental results of MIC-TS and various algorithms on ECOLI data set

從表4可以看出, MIC-TS算法在較大的ECOLI網(wǎng)絡(luò)下相比經(jīng)典算法也存在優(yōu)勢(shì),在樣本數(shù)量為2 000、5 000、10 000的實(shí)驗(yàn)結(jié)果中,F值和TP值都顯著高于其他算法,但HD值相比于MMHC和Banjo算法的結(jié)果也偏高,圖5為MIC-TS算法生成的SACHS基因調(diào)控網(wǎng)絡(luò)圖。隨著樣本數(shù)量的增多,MIC-TS算法學(xué)習(xí)的更加充分,性能的提升幅度也更高。在數(shù)據(jù)量較少(2 000)時(shí),MIC-TS學(xué)習(xí)的基因調(diào)控網(wǎng)絡(luò)各項(xiàng)指標(biāo)與TS,Hill Climbing算法差距不大,推測(cè)是因?yàn)榈蛿?shù)據(jù)量時(shí)通過最大信息系數(shù)構(gòu)建的初始網(wǎng)絡(luò)較不準(zhǔn)確,生成了標(biāo)準(zhǔn)網(wǎng)絡(luò)中沒有的邊所導(dǎo)致,隨著數(shù)據(jù)量的增多(5 000,10 000),MIC-TS的實(shí)驗(yàn)指標(biāo)中的TP值明顯增大,生成網(wǎng)絡(luò)與真實(shí)網(wǎng)絡(luò)更加接近,提升明顯。MIC-TS算法的實(shí)驗(yàn)結(jié)果在HD值上略大于MMHC以及Banjo算法,推測(cè)是因?yàn)镸MHC算法因其僅在篩選后的網(wǎng)絡(luò)空間內(nèi)搜索,較為有效的降低了HD值,但同時(shí)學(xué)習(xí)到的正確邊也會(huì)減少,TP值略小,圖6以條狀圖的形式給出了不同樣本量下各個(gè)算法在F值以及正確邊數(shù)(TP)上的數(shù)據(jù)對(duì)比,可以直觀地看出,本文的MIC-TS算法的數(shù)據(jù)相比其他算法更為優(yōu)秀,隨著數(shù)據(jù)量的增多,學(xué)習(xí)到的正確邊數(shù)增長(zhǎng)明顯。

圖5 MIC-TS算法生成的ECOLI網(wǎng)絡(luò)Fig.5 ECOLI network generated by MIC-TS

(a) F

為了驗(yàn)證本文的MIC-TS算法是否優(yōu)于其他使用MIC構(gòu)建初始網(wǎng)絡(luò)時(shí)的評(píng)分搜索算法,在上文2個(gè)數(shù)據(jù)集的不同樣本量上對(duì)本文MIC-TS算法和在MIC初始網(wǎng)絡(luò)上進(jìn)行評(píng)分搜索的Hill Climbing算法(以下簡(jiǎn)稱MIC-HC)進(jìn)行實(shí)驗(yàn)對(duì)比(表5),表中的數(shù)據(jù)顯示在2個(gè)不同大小數(shù)據(jù)集的各個(gè)樣本量上,MIC-TS的數(shù)據(jù)都要更優(yōu)秀,和上文的實(shí)驗(yàn)結(jié)果對(duì)比,證明了MIC-TS算法在評(píng)分搜索階段使用禁忌表跳出局部最優(yōu)的方式能得到更為優(yōu)秀的結(jié)果,有效提高了算法的性能。

表5 MIC-TS與MIC-HC算法在不同數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果Tab.5 Experimental results of MIC-TS and MIC-HC algorithms in different datasets

3 結(jié)語

本文將貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)和最大信息系數(shù)MIC結(jié)合生成的MIC-TS算法應(yīng)用于基因調(diào)控網(wǎng)絡(luò)的構(gòu)建。通過計(jì)算網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的MIC值,篩出網(wǎng)絡(luò)中可能性較大的邊來構(gòu)成初始網(wǎng)絡(luò)結(jié)構(gòu),進(jìn)一步使用Tabu搜索和BDe評(píng)分函數(shù)學(xué)習(xí)最終的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu),有效地提高了算法的性能。經(jīng)過在2個(gè)不同規(guī)模的基因調(diào)控網(wǎng)絡(luò)數(shù)據(jù)上進(jìn)行實(shí)驗(yàn),并與若干經(jīng)典算法進(jìn)行指標(biāo)上的對(duì)比,驗(yàn)證了文中算法的準(zhǔn)確性和普適性。如何使用其他算法與MIC構(gòu)成的初始網(wǎng)絡(luò)進(jìn)行結(jié)合,充分利用不同算法的優(yōu)勢(shì)提高算法的準(zhǔn)確性以進(jìn)行基因調(diào)控網(wǎng)絡(luò)的構(gòu)建仍需要進(jìn)行進(jìn)一步的研究。