人工魚群算法在基因調控網絡中的應用研究

田旺蘭,李加升

(湖南城市學院通信與電子工程學院,湖南益陽413000)

人工魚群算法在基因調控網絡中的應用研究

田旺蘭,李加升

(湖南城市學院通信與電子工程學院,湖南益陽413000)

在分析基因調控網絡現狀及優缺點的基礎上,提出利用人工魚群算法對閾值布爾網絡模型構建下的基因調控網絡進行研究。將閾值布爾網絡模型應用于花發育形態模型,構建基于預定義吸引子和極限環的綜合網絡。比較人工魚群算法與模擬退火算法在基因調控網絡中的應用情況,分析網絡節點更新機制變化時布爾網絡保留吸引子的能力,發現在極限環長度為2和特定網絡拓撲下網絡才具有魯棒性。實驗結果表明,與模擬退火算法相比,人工魚群算法在網絡發現、魯棒性方面具有更好的性能,因此利用人工魚群算法學習布爾網絡結構是有效可行的。關鍵詞:人工魚群算法;模擬退火算法;布爾網絡;吸引子;極限環;花發育形態模型

1 概述

近年來,基因調控網絡 (Gene Regulatory Network,GRN)已經引起了機器學習界的廣泛關注。研究人員對GRN的不同數學模型進行了研究,分別提出了布爾網絡[1]、概率布爾網絡[2]、Petri網[3]、貝葉斯網絡[4]、遞歸神經網絡[5]等。文獻[6]利用蜂群算法(Bees Algorithm,BA)、文獻[7-10]利用模擬退火(Simulated Annealing,SA)分別從不同方面對GRN進行了研究,證明了利用群體智能算法研究GRN的可行性,同時表明算法的網絡發現頻率和網絡節點更新序列數量之間存在冪律關系,但是網絡發現率不太高、魯棒性不太好。

人工魚群算法[11](Artificial Fish Swarm Algorithm,AFSA)是一種較新的群體智能優化算法,文獻[12]等提出了一種雙域模型人工魚群算法;文獻[13]等用人工魚群算法對支持型QoS單播路由機制進行了研究,另有學者從不同方面對人工魚群算法進行了優化和改進,如文獻[14]借鑒模擬退火算法中的Metropolis判別準則和利用模擬退火算子改進了人工魚群的覓食行為,提出了利用模擬退火算法來改進的人工魚群算法;文獻[15]提出了利用高斯變異算子加差分進化變異算子的改進人工魚群算法;文獻[16]提出了基于遺傳算法的人工魚群優化算法,但目前無人將人工魚群算法用于研究GRN網絡。

目前,GRN構建中具有代表性的布爾網絡已經廣泛應用于酵母細胞周期表達、果蠅體節極性網絡、哺乳動物細胞周期表達、花發育形態表達等不同生物的基因調控網絡的研究[17]中。本文將人工魚群算法應用到閾值布爾網絡構建的花發育形態模型中,可獲得較好的魯棒性和網絡發現頻率。

2 人工魚群算法

2.1 布爾網絡

1969年,Kauffuman[1]提出了著名的布爾網絡模型,用于研究基因調控網絡和細胞分化過程。

設A為關于n的有限集,A={a1,a2,…,an},ai屬于{0,1},i=1,2,…,n。一個布爾網絡就是一個(G,F)對,這里G=(V,E)為有限有向圖,V是n個節點的集合,E是邊的集合。F是布爾函數,F:{0,1}n({0,1}由n個局部函數fi:{0,1}n組成,且每個局部函數僅依賴屬于鄰域Vi={j∈V|(j,i)∈E}的變量。

節點定期更新,根據網絡收斂的動力學特性,吸引子分為固定吸引子和極限環,定義為:

固定吸引子:

極限環:

其中,p為極限環,是大于等于1的正整數。

因此,每個節點在t+1時刻的狀態可以寫為:

其中,wji∈{-1,0,1},是從節點j到節點i的權值,對于所有的節點i,θi=0。這種模型就叫做閾值布爾網絡。

對于用閾值布爾網絡構建的基因調控網絡的邊和權值,需要用到一個鄰接矩陣M,邊表示基因間的相互作用,權值表示基因間的激勵或抑制關系。初始矩陣Mi,i=1,2,…,ns在人工魚群算法里是隨機生成的,如圖1所示,但該矩陣嚴格服從節點入度R等的約束。

圖1 隨機初始矩陣M及其對應布爾網絡

網絡初始化后,網絡節點的更新有很多種方法,人們最感興趣的有以下2種[6]:

(1)并行或同步模式:每個節點同時更新。

(2)串行模式:在每個時間步長節點按預定義順序更新。

2.2 算法介紹

2.2.1 適應度函數的定義

布爾網絡B的適應度函數即為人工魚群算法的食物濃度,定義為為每個節點i的網絡輸出oi和每個節點i的目標值ci間的方差,計算公式為:

其中,n為網絡節點個數;p為吸引子環長度。

2.2.2 人工魚群算法及算法步驟

人工魚群算法作為一種有效的智能群體尋優算法,通過模擬魚類的覓食、聚群、追尾和隨機等行為在搜索域內進行尋優,是利用群體智能思想解決優化問題的一個具體應用。

如圖2所示,用Pcurr表示人工魚虛擬實體的當前位置,Visual為其視野范圍,Pvisu為其在某時刻的視點所在位置,如果該位置的食物濃度優于當前位置,則可往該方向游進Step,即到達Pnext,Step為其可移動的最大步長。如果位置Pvisu不比當前位置Pcurr更優,則繼續巡視視野內的其他位置。巡視次數越多,則對視野內的狀態了解越全面,從而對周圍的環境有一個全方位的立體認知,這有助于人工魚群做出相應的判斷和決策[18]。Pn1,Pn2,Pn3為視野范圍內魚的位置。

圖2 人工魚的視野域和最大移動步長

位置Pcurr=(p1,p2,…,pn),位置Pvisu=(,,…,),則從Pcurr到達Pvisu的過程可以表示為:

其中,rand為區間[-1,1]內的隨機數。

人工魚群算法中用到的參數如表1所示。

表1 人工魚群算法輸入輸出參數

算法偽代碼如下:

輸入N,Visual,Step,trynum,λ,maxgen

輸出 最優解

2.2.3 模擬退火算法

模擬退火源于固體加熱至一定溫度呈液態后,接著再對其慢慢冷卻、降溫到預期穩定狀態的過程。后來用于解決可以描述為退火過程的最優化問題,固體狀態表示可行的最優解,狀態能量表示解的客觀函數值,最小能量值就是問題的優化解[7]。為了用退火過程來解決現有問題,給出以下4個定義:

(1)解決方案:同人工魚群算法。

(2)適應度函數的定義:同人工魚群算法。

(3)搜索策略:同人工魚群算法,但模擬退火中m的每次迭代,鄰域數ngh的減少遵循下式:

其中,ΔE是當前值與新產生的候選解之差。如果ngh＜1,則將ngh置1。

(4)冷卻進度表:參考標準幾何學冷卻規則,溫度T為:

其中,λ為冷卻率常數,λ＜1。本文中溫度不會在每次迭代后下降,而是每10次迭代才運用此公式一次。

3 人工魚群算法在基因調控網絡中的應用

人工魚群算法是一種新的不同于傳統優化模式的問題解決辦法,它只使用目標函數值,對搜索空間具有一定的自適應能力,算法對初值無要求,系統初始化為一隨機解,對各參數的選擇也不敏感。而對布爾網絡的研究,通常是給出節點的初始化矩陣,然后通過計算節點關聯的布爾函數,得出節點間的相互關系,這正好與基因調控網絡中基因間的激勵與抑制關系相對應,所以將人工魚群算法用于研究布爾網絡構建的基因調控網絡是可行的。將人工魚群算法用于花發育形態模型,該模型由EMF1,TFL1, LEF,AP1,CAL,LUG,UFO,BFU,AG,AP3,PI和SUP等基因組成[19],這12個基因即為網絡中的12個節點,也就是人工魚群算法中的魚群規模。算法行為如下:

(1)覓食行為

設人工魚即花發育形態網絡中的某節點當前狀態值為Pi,在其感知域中隨機選擇一個狀態Pj,食物濃度用Y表示,在最大值問題求解中,若食物濃度Yi＜Yj(最小值問題求解中Yi＞Yj,與此類似),則向該方向游進一步;否則,再重新隨機選擇狀態Pj,判斷是否滿足前進條件。如此反復嘗試trynum次后,如果仍不滿足前進條件,則隨機移動一步。覓食過程如圖3所示。

圖3 覓食行為流程

(2)聚群行為

設人工魚即花發育形態網絡中的某節點當前狀態為Pi,搜索當前感知域內(即Di,j＜Visual)的伙伴數hf和中心位置Pc,如果Yc/hf＞λYi(λ為擁擠度),說明伙伴中心位置的食物濃度較大且不太擁擠,則朝伙伴中心位置方向游進一步;否則執行覓食行為。聚群過程如圖4所示。

圖4 聚群行為流程

(3)追尾行為

設人工魚即花發育形態網絡中的某節點當前狀態為Pi,搜索當前感知域內(即Di,j＜Visual)的伙伴數hf和這群伙伴中Yj為最大的伙伴Pj,如Yj/hf＞λYi,表明該伙伴Pj的周圍不太擁擠,且具有較高的食物濃度,則朝伙伴Pj游進一步;反之執行覓食行為。追尾過程如圖5所示。

圖5 追尾行為流程

(4)隨機行為

隨機行為的實現較為簡單,就是當某人工魚即花發育形態網絡中的某節點狀態在最優值附近徘徊時,在視野范圍隨機選擇一個狀態,并向該方向游進,這也就是覓食行為的缺省狀態,即Pi的下一個位置Pi|next為:

其中,rand為區間[-1,1]內的隨機數;Visual為感知域范圍。

在算法實現過程中,設立一個公告板來記錄最優的網絡節點狀態。每次尋優后就將節點自身狀態與公告板記錄進行比較,若優于公告板,則將公告板記錄更新為自身狀態。

4 實驗與結果分析

布爾網絡的狀態分為暫態和吸引子,吸引子又分為固定吸引子和極限環,本文從吸引子和極限環2個方面評估運用人工魚群算法所研究的GRN的性能,同時與模擬退火算法在基因調控網絡中的應用進行了比較。

4.1 基于固定吸引子的實驗

本文實例中,人工魚群算法用預定義的固定吸引子來研究閾值布爾網絡,用到的6個吸引子數據源于文獻[19],分別是(0110 0000 1000,1000 0001 1110,0001 0000 0100,0001 1001 0110,1100 0000 0001,0100 0001 0110)。人工魚群算法、模擬退火分別運行500次并記下每次運行記錄以核實它們是否有能力來研究6個固定吸引子。2個算法的參數是在多次運行后根據網絡研究和執行時間的有效性根據經驗來確定的。設人工魚群的規模N=12、每條人工魚的可視范圍Visual=3、最大步長Step=1、每次隨機移動可嘗試的最大次數trynum=5、擁擠度因子λ=0.65,最大迭代次數maxgen=50,對于模擬退火,m=1000,ngh=11,λ=0.7,初始溫度T(0)=100。

用于研究閾值布爾網絡的6個吸引子實際由42 bit組成(6個吸引子×7個節點)。人工魚群算法和模擬退火算法運行500次后的結果如圖6所示。從圖6可看出,當錯誤位數分別為1,2,3,4,5時,人工魚群算法發現網絡的頻率都明顯比模擬退火算法要低。

圖6 算法運行500次后的結果

4.2 基于極限環的實驗

當一個運行在并行更新模式下的網絡更新為串行更新模式時,極限環會發生什么變化,極限環會保留還是會破壞,網絡拓撲(入度R)會影響輸出,為解答以上問題,所以,本實例主要研究網絡的魯棒性。

給定網絡節點數為6,預定義的極限環為p=2, 3,4和5,入度R=1,2,3,4,5和6,式(3)中的候選解輸出采用并行更新模式。對每一對(p,R),每個網絡都有100個不同的極限環被研究,極限環是隨機產生且各不相同的常量。然后,當此能夠研究極限環的網絡更新模式變為串行時(所有可能狀態數為6!=720),能保留極限環的網絡就會被記錄。人工魚群算法的參數設置如前,模擬退火的為:m= 500,ngh=5,λ=0.7,初始溫度T(0)=100。

4.2.1 極限環為2時的實驗

圖7為極限環p=2時的結果,P/S表示更新機制由并行變為串行時仍能保留極限環的網絡,從圖7可看出,當節點入度為3和5時,發現的網絡才具有保留極限環的能力。圖8為入度為3時利用人工魚群算法得到的布爾網絡,網絡在并行更新模式下擁有極限環(100101,011010),并且當它從并行變為串行時,串行更新順序為6-3-5-1-2-4。圖9為入度為5時利用人工魚群算法得到的布爾網絡,網絡在并行和串行更新模式下的極限環為(110010,001101),順序為4-1-6-5-3-2。

圖7 極限環p=2時算法的網絡發現頻率

圖8 R=3時利用人工魚群算法得到的布爾網絡

圖9 R=5時利用人工魚群算法得到的布爾網絡

4.2.2 極限環為3,4,5時的實驗

為了更進一步說明人工魚群算法的優越性,以下對極限環p=3,4,5時進行了實驗,結果顯示,更新模式由并行變為串行時沒有網絡能保留極限環,結果如圖10～圖12所示。

圖10 極限環p=3時算法發現網絡的頻率

圖11 極限環p=4時算法的網絡發現頻率

圖12 極限環p=5時算法的網絡發現頻率

綜上,由4.1節和4.2節可見,人工魚群算法在利用預定義吸引子研究閾值布爾網絡時要優于模擬退火算法。兩者都使用了相同的解決方案、局部搜索策略及適應度函數,而人工魚群算法得到了顯著好的結果。在4.1節中,人工魚群算法得到的平均入度要低于模擬退火,意味著使用人工魚群算法比模擬退火僅需較少的邊就可以得到更為緊湊的效果。這也表明,利用智能人工魚群算法搜索解,在每一次迭代中得到的結果比模擬退火方法在每一次迭代時僅用一個候選解要好。

在4.2節中,P/S網絡僅出現在p=2時,R=3, 5的情況下,且P/S網絡的數量小于網絡總數的35%。從圖7、圖10～圖12也可以清楚地看出,隨著p的增大,發現網絡的頻率則減小。當p＞2,R= 1時,2種算法都很難發現網絡。事實上,當p=3時,模擬退火根本不能發現網絡,而人工魚群算法也僅發現了極少的網絡。

5 結束語

本文提出利用人工魚群算法來研究閾值布爾網絡模型構建的GRN,介紹了魚群算法在基因調控網絡中的應用。與模擬退火算法的比較結果表明,魚群算法利用群體智能算法研究GRN在網絡發現和魯棒性方面具有更好的能力。在以后的研究中,可考慮其他群體智能算法在GRN中的應用,或者改進魚群算法,因為人工魚在可見鄰域內如果搜索不到比自身狀態更優的人工魚個體,則說明它達到了局部最優值。在覓食行為中,人工魚會選擇隨機移動。隨機移動的步長大小對最優值的穩定有很大的影響;太大可能會導致人工魚個體在最優值的附近徘徊,不利于結果的收斂與穩定。為此,可考慮引入隨機移動因子來減慢隨機移動速度,以得到更快更優的算法。

[1] Kauffman S A.Metabolic Stability and Epigenesist in Randomly Constructed Genetic Nets[J].Journal of Theoretical Biology,1969,22(3):437-467.

[2] Shmulevich I,Dougherty E R.Probabilistic Boolean Networks:The Modeling and Control of Gene Regulatory Networks[M].Philadelphia,USA:SIAMSociety for Industrial and Applied Mathematics,2009.

[3] Steggles L J,Banks R,WipatA.Modelling and Analyzing Genetic Networks:From Boolean Networks to Petri Nets[C]//Proc.of CMSB’06.[S.1.]:IEEE Press,2006:127-141.

[4] Yu J,Smith V A,Wang P P,et al.Advances to Bayesian Network Inference for Generating Causal Networks from Observational Biological Data[J].Bioinformatics,2004, 20(1):3594-3603.

[5] Lee W,Yang K.Applying IntelligentComputing Techniques to Modeling BiologicalNetworksfrom Expression Data[J].Genomics,Proteomics & Bioinformatics,2006,6(2):111-120.

[6] EricGoles G R.LearningGeneRegulatory Networks Using the Bees Algorithm[J].Neural Comput&Applic, 2013,22(1):63-70.

[7] Kirkpatrick S,Gelatt C D,Vecchi M P.Optimization by Simulated Annealing[J].Science,1983,220(4598): 671-680.

[8] Liu G,Feng W,Wang H,et al.Reconstruction of Gene Regulatory Networks Based on Two-stage Bayesian Network Structure Learning Algorithm[J].Journal of Bionic Engineering,2009,6(1):86-92.

[9] Tomshine J,Kaznessis Y N.Optimization of Astochastically Simulated Gene Network Model via Simulate Dannealing [J].Biophys Journal,2006,91(1):3196-3205.

[10] Ruz G A,Goles E.Learning Gene Regulatory Networks with Predefined AttractorsforSequentialUpdating Schemes Using Simulated Annealing[C]//Proceedings of the 9th IEEE International Conference on Machine Learning and Applications.[S.1.]:IEEE Press,2010: 889-894.

[11] 李曉磊.一種新型的智能優化算法——人工魚群算法[D].杭州:浙江大學,2003.

[12] 馬 炫,劉 慶.基于人工魚群算法的多播樹演化尋優[J].通信學報,2012,33(9):1-7.

[13] 王興偉,秦培玉,黃 敏.基于人工魚群的ABC支持型QoS單播路由機制[J].計算機學報,2010,33(4): 718-725.

[14] 劉 佳,劉麗娜,李 靖,等.基于模擬退火算法的改進人工魚群算法研究[J].計算機仿真,2011,28(10): 195-198.

[15] 曲良東,何登旭.混合變異算子的人工魚群算法[J].計算機工程與應用,2008,44(35):50-52.

[16] 劉 白,周永權.基于遺傳算法的人工魚群優化算法[J].計算機工程與設計,2008,29(22):5827-5829.

[17] 王向紅,王 欣,劉莉莉,等.布爾網絡動態行為研究[J].浙江師范大學學報:自然科學版,2012,35(1): 47-52.

[18] 王宗利,劉希玉,王文平.一種改進的人工魚群算法[J].信息技術與信息化,2010,(3):46-49.

[19] Mendoza L,Alvarez-BuyllaE R.Dynamicsofthe Genetic Regulatory Network for Arabidopsis Thaliana Flower Morphogenesis[J].JournalofTheoretical Biology,1998,193(2):307-319.

編輯 索書志

Research on Application of Artificial Fish Swarm Algorithm in Gene Regulatory Network

TIAN Wang-lan,LI Jia-sheng
(College of Communication and Electronic Engineering,Hunan City University,Yiyang 413000,China)

Based on the analysis of the advantages and disadvantages of the current appliance of swarm intelligence algorithm into Gene Regulatory Network(GRN),this paper studies the gene regulatory network constructed under Boolean network model using Artificial Fish Swarm Algorithm(AFSA).Especially,the comprehensive network of predefined attractors and limit cycle is formulated by applying Boolean network model into flower growth morphogenesis. After comparing AFSA with Simulated Annealing(SA)and analyzing the ability of the networks to preserve the attractors when the updating schemes is changed from parallel to sequential,the paper finds the network has robustness within the limit cycle length equal to two and specific network topologies.Experimental results show that the intelligence algorithm outperforms simulated annealing in network discovery and robustness.Therefore,it is feasible to learn Boolean network using AFSA.

Artificial Fish Swarm Algorithm(AFSA);Simulated Annealing(SA)algorithm;Boolean network;

1000-3428(2014)10-0204-06

A

TP18

10.3969/j.issn.1000-3428.2014.10.038

湖南省科技計劃基金資助項目(2012FJ3025)。

田旺蘭(1977-),女,講師、碩士,主研方向:網絡通信;李加升,教授。

2014-03-20

2014-06-20E-mail:angletw@sohu.com

中文引用格式:田旺蘭,李加升.人工魚群算法在基因調控網絡中的應用研究[J].計算機工程,2014,40(10):204-209.

英文引用格式:Tian Wanglan,Li Jiasheng.Research on Application of Artificial Fish Swarm Algorithm in Gene Regulatory Network[J].Computer Engineering,2014,40(10):204-209.

attractor;limit circle;flower growth morphogenesis model