林　勤， 薛　云, 林斯達(dá), 何明清

(1.廣東醫(yī)學(xué)院信息工程學(xué)院，東莞 523808；2.華南師范大學(xué)物理與電信工程學(xué)院，廣州 510006；3.廣東醫(yī)學(xué)院公共衛(wèi)生學(xué)院，東莞 523808)

?

多目標(biāo)人工蜂群雙聚類算法在基因表達(dá)數(shù)據(jù)中的應(yīng)用研究

林勤1， 薛云2*, 林斯達(dá)3, 何明清3

(1.廣東醫(yī)學(xué)院信息工程學(xué)院，東莞 523808；2.華南師范大學(xué)物理與電信工程學(xué)院，廣州 510006；3.廣東醫(yī)學(xué)院公共衛(wèi)生學(xué)院，東莞 523808)

摘要：基于多目標(biāo)優(yōu)化的雙聚類算法能夠同時優(yōu)化均方殘差和尺寸等多個相互沖突的目標(biāo)，更好地挖掘出均方殘差較小、尺寸較大的雙聚類，提出了一個多目標(biāo)人工蜂群雙聚類算法．該方法首先采用組信息對蜜源進(jìn)行編碼，然后使用2種交叉和1種變異操作分別實(shí)現(xiàn)算法的局部搜索和全局搜索，最后根據(jù)非劣排序和擁擠距離對外部檔案進(jìn)行修剪．在2套真實(shí)的基因表達(dá)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果表明：與其他公開算法相比，多目標(biāo)人工蜂群雙聚類算法具有較好的收斂性和種群多樣性，同時挖掘出具有顯著生物意義的雙聚類．

關(guān)鍵詞：基因表達(dá)數(shù)據(jù)； 雙聚類； 多目標(biāo)優(yōu)化； 人工蜂群

DNA微陣列技術(shù)產(chǎn)生了大量的基因表達(dá)數(shù)據(jù)集，這些數(shù)據(jù)集為深入認(rèn)知生命過程和本質(zhì)提供支撐，也為當(dāng)前分析方法帶來了嚴(yán)峻的挑戰(zhàn)．聚類是基因表達(dá)數(shù)據(jù)分析的基礎(chǔ)，可以用來發(fā)現(xiàn)具有相似表達(dá)行為的基因集，以預(yù)測未知基因的功能以及構(gòu)建基因調(diào)控網(wǎng)絡(luò)[1]．傳統(tǒng)聚類(如層次聚類[2]、K均值聚類[3]等)要求同類基因在所有條件下表達(dá)行為都要相似．但通常情況下，一些基因只在某些條件下有著相似的表達(dá)行為.在基因表達(dá)數(shù)據(jù)量少、維度低的情況下，這種方法對實(shí)際結(jié)果影響不大．但隨著基因表達(dá)數(shù)據(jù)維度的不斷增長，采用這種方法會丟失很多具有生物意義的局部模式．

為了發(fā)現(xiàn)部分實(shí)驗(yàn)條件下表達(dá)高度相似的基因集合，CHENG和CHURCH[4]提出了1種在基因和實(shí)驗(yàn)條件2個維度進(jìn)行聚類的雙聚類方法，定義了均方殘差(Mean Squared Residue，MSR)作為衡量雙聚類質(zhì)量的指標(biāo)，并采用增刪節(jié)點(diǎn)的貪婪啟發(fā)式策略和隨機(jī)數(shù)替換來尋找雙聚類．隨后，F(xiàn)LOC、OPSM、DBF等基于貪心策略的雙聚類算法相繼被提出[5-7]．雖然貪心策略比窮舉策略的效率高，但是容易陷入局部最優(yōu)，導(dǎo)致雙聚類質(zhì)量較差．2004年，BLEULER等[8]提出了基于進(jìn)化算法的雙聚類分析框架．2005年,BRYAN等[9]將模擬退火應(yīng)用于基因表達(dá)數(shù)據(jù)雙聚類分析中并得到較好的結(jié)果．然而，在求解過程中，搜索質(zhì)量較高的雙聚類不僅需要優(yōu)化均方殘差，同時還需優(yōu)化尺寸(Size)等多個相互沖突的目標(biāo)，因此，文獻(xiàn)[10]提出了多目標(biāo)進(jìn)化雙聚類(Multi-Objective Evolution Biclustering，MOEB)的框架，應(yīng)用非支配排序遺傳算法(Non-dominated Sorting Genetic Algorithm Ⅱ，NSGAⅡ)，并結(jié)合局部搜索得到了質(zhì)量較優(yōu)的結(jié)果．文獻(xiàn)[11]提出了改進(jìn)的多目標(biāo)遺傳雙聚類算法(Enhanced Multi-objective Genetic Biclustering，eMOGB)，采用了新穎的組信息編碼方式來高效地編碼雙聚類，并減少了局部搜索環(huán)節(jié)，提高了算法的執(zhí)行效率．文獻(xiàn)[12]提出了多目標(biāo)粒子群雙聚類算法(Multi-Objective Particle Swarm Optimization Biclustering，MOPSOB)．文獻(xiàn)[13]在MOPOSB的基礎(chǔ)上，引入了ε-支配、擁擠距離和最近搜索等優(yōu)化技術(shù)，提出了基于擁擠距離的多目標(biāo)粒子群雙聚類算法(Crowding distance based Multi-Objective Particle Swarm Optimization Biclustering，CMOPSOB,)，進(jìn)一步提高了最優(yōu)解的多樣性和收斂性．

人工蜂群算法(Artificial Bee Colony，ABC)是1種新型的智能仿生算法[14]．對比于遺傳、粒子群等常見的智能算法，ABC算法具有多種蜂種的分工協(xié)作，可通過不同的搜索策略來更好地完成搜索最優(yōu)解的工作．這使得算法更加靈活、更容易與其他技術(shù)融合，全局搜索能力更強(qiáng)[15]．本文以人工蜂群算法為框架，提出了多目標(biāo)人工蜂群雙聚類算法(Multi-Objective Artificial Bee Colony Biclustering，MOABCB)．為了更好地優(yōu)化均方殘差和尺寸這2個目標(biāo)，該算法在編碼、不同蜂群搜索方式、蜜源替換規(guī)則和外部檔案的維護(hù)等方面對框架進(jìn)行了關(guān)鍵設(shè)計(jì)和改進(jìn)．最后，將該算法應(yīng)用于酵母菌和人類B細(xì)胞2套真實(shí)的基因表達(dá)數(shù)據(jù)集，并與多個基于多目標(biāo)優(yōu)化的雙聚類算法進(jìn)行實(shí)驗(yàn)結(jié)果的比較．結(jié)果表明：所提算法能挖掘到更優(yōu)的雙聚類，所得種群具有較好的多樣性和收斂性．此外，使用GO和KEGG這2個重要的生物數(shù)據(jù)庫對所提算法得到的聚類結(jié)果進(jìn)行驗(yàn)證，結(jié)果表明所提算法可以挖掘出具有顯著生物意義的雙聚類．

1問題的描述

基因表達(dá)數(shù)據(jù)可以看成一個m×n的實(shí)數(shù)矩陣A．A的m行代表m個不同的基因，n列代表n種不同的實(shí)驗(yàn)條件．定義A的基因集G={x1,x2,…,xm}和實(shí)驗(yàn)條件集C={y1,y2,…,yn}．雙聚類是A的一個子矩陣AIJ，可表示為：AIJ=(I,J)，其中I={i1,i2,…,ik}是基因集G的子集，J={j1,j2,…,jl}是實(shí)驗(yàn)條件集C的子集．

定義1均方殘差是用于度量雙聚類內(nèi)數(shù)據(jù)相似性的指標(biāo)．在給定的子矩陣AIJ中，其均方殘差定義為：

(I?G,J?C)，

(1)

定義2尺寸的大小是用來衡量雙聚類好壞的另一個指標(biāo)．在給定的子矩陣AIJ中，其尺寸定義為：

(2)

算法的目標(biāo)是挖掘出基因數(shù)據(jù)之間的表達(dá)水平波動趨勢盡可能一致的簇，同時這些簇的規(guī)模不會太小，也就是說均方殘差較小且尺寸較大的雙聚類．

2多目標(biāo)人工蜂群雙聚類算法

2.1人工蜂群算法

人工蜂群算法是一種模擬蜂群分工采蜜的智能優(yōu)化算法[14]，將尋找最優(yōu)解轉(zhuǎn)化成蜜蜂搜索高質(zhì)量蜜源位置的過程．蜂群中有3種角色：采蜜蜂、觀察蜂和偵查蜂．蜜源代表當(dāng)前可行解，采蜜蜂與蜜源一一對應(yīng)．蜜源的尋找過程通過不同角色間的信息交流、身份轉(zhuǎn)換實(shí)現(xiàn)．在采蜜蜂階段，每只采蜜蜂在對應(yīng)的蜜源周圍搜索更優(yōu)解，并以搖擺舞的方式，將蜜源信息分享給觀察蜂．觀察蜂根據(jù)采蜜蜂提供的信息采用輪盤賭策略選擇蜜源，蜜源質(zhì)量越高，觀察蜂前往的概率越大．觀察蜂選取蜜源后對蜜源進(jìn)行更新．在算法中，參數(shù)trial用來記錄蜜源未被更新的次數(shù)，若trial超出閾值，即經(jīng)過若干次搜索后，蜜源質(zhì)量仍無法改善，相應(yīng)的采蜜蜂會放棄該蜜源，變成偵查蜂在可行解的范圍內(nèi)進(jìn)行隨機(jī)搜索，產(chǎn)生新蜜源．之后偵查蜂轉(zhuǎn)變?yōu)椴擅鄯洌^續(xù)與其他蜜蜂分享蜜源信息．

2.2多目標(biāo)人工蜂群雙聚類算法的框架設(shè)計(jì)

為了更好地優(yōu)化雙聚類的均方殘差和尺寸這2個相互沖突的目標(biāo)，采用了多目標(biāo)優(yōu)化的方法來求解基因表達(dá)數(shù)據(jù)的雙聚類問題．同時，蜂群算法相對于遺傳、粒子群等常見的智能算法具有更優(yōu)的全局尋優(yōu)潛力，應(yīng)用了多目標(biāo)人工蜂群雙聚類算法來求解基因表達(dá)數(shù)據(jù)的雙聚類問題，并給出了一個具體的解決框架，具體流程見圖1．

圖1　多目標(biāo)人工蜂群雙聚類算法流程圖

2.2.1編碼方式采用文獻(xiàn)[11]224的組信息編碼方式．編碼規(guī)則如下：每個蜜源擁有2條序列：基因序列和條件序列．如果基因序列中擁有值為g的元素，表示第g個基因在指定雙聚類中．條件序列同理．這種編碼方式只保留雙聚類在基因表達(dá)數(shù)據(jù)矩陣中基因以及實(shí)驗(yàn)條件的實(shí)際序號，具有簡潔高效的特點(diǎn)．例如，對圖2A所示的嵌入在基因表達(dá)數(shù)據(jù)矩陣中由灰色背景元素組成的雙聚類進(jìn)行編碼，根據(jù)組信息編碼規(guī)則，可知其編碼的結(jié)果(圖2B)．相反，組編碼所譯碼的雙聚類如圖2C所示．

圖2　一個雙聚類編碼和譯碼的例子

2.2.2適應(yīng)度函數(shù)為了便于求解，把目標(biāo)函數(shù)(1)、(2)統(tǒng)一轉(zhuǎn)換為最大化問題：

(3)

(4)

其中，δ是待設(shè)定的均方殘差閾值．

2.2.3搜索方式對不同蜂種的蜜蜂設(shè)計(jì)了不同的搜索策略，以克服傳統(tǒng)蜂群算法容易陷入局部最優(yōu)解的問題．

在采蜜蜂階段，規(guī)定第i只采蜜蜂(蜜源1)在進(jìn)行搜索時限定選取第n+i-1個蜜源(蜜源2)作為參照．利用eMOGB算法中的交叉規(guī)則[11]225進(jìn)行局部搜索．在兩蜜源的基因序列中隨機(jī)產(chǎn)生一個基因交叉位點(diǎn)Gpivot，將蜜源1的基因序列中基因序號小于等于Gpivot所在基因的序號賦予子代1，大于Gpivot所在基因的序號賦予子代2；將蜜源2的基因序列中基因序號大于等于Gpivot所在基因的序號賦予子代1，小于Gpivot所在基因的序號賦予子代2，條件序列同理．例如，對圖3A所示的2個蜜源進(jìn)行采蜜蜂領(lǐng)域搜索，其過程如下：隨機(jī)在2個蜜源選擇基因交叉位點(diǎn)(Gpivot=5)和條件交叉位點(diǎn)(Cpivot=2)，由于選擇的基因交叉位點(diǎn)對應(yīng)的基因序號是4，條件交叉位點(diǎn)對應(yīng)的條件序號是5，根據(jù)采蜜蜂的交叉規(guī)則，可知其子代1和子代2的基因序列和條件序列(圖3B)．

在觀察蜂階段，對文獻(xiàn)[11]225的交叉規(guī)則進(jìn)行改進(jìn)：觀察蜂通過輪盤賭策略選中蜜源1后，隨機(jī)選取蜜源2作為參照，在兩蜜源的基因序列中隨機(jī)產(chǎn)生一個基因交叉位點(diǎn)Gpivot，將蜜源1和蜜源2的基因序列中小于等于Gpivot所在基因的序號都賦予子代1，將大于Gpivot所在基因的序號賦予子代2，條件序列的交叉規(guī)則同理．例如，對圖4A所示的2個蜜源進(jìn)行觀察蜂領(lǐng)域搜索，其過程如下：隨機(jī)在2個蜜源選擇基因交叉位點(diǎn)(Gpivot=5)和條件交叉位點(diǎn)(Cpivot=2)，由于選擇的基因交叉位點(diǎn)對應(yīng)的基因序號是4，基因交叉位點(diǎn)對應(yīng)的基因序號是5，根據(jù)觀察蜂的交叉規(guī)則，可知其子代1、子代2的基因序列和條件序列(圖4B)．

圖3　采蜜蜂進(jìn)行鄰域搜索的例子

圖4　觀察蜂進(jìn)行鄰域搜索的例子

在偵查蜂階段，對于未更新系數(shù)trial超出閾值Limit的蜜源，引入變異操作，通過隨機(jī)增減蜜源的一行或一列的方式對蜜源進(jìn)行更新，以實(shí)現(xiàn)全局搜索更優(yōu)的蜜源．該偵查策略丟棄了蜜源的全部信息，導(dǎo)致ABC算法收斂速度減緩．本文設(shè)計(jì)的變異操作，使得偵查蜂能受到原蜜源部分有利信息的引導(dǎo)，在原蜜源的基礎(chǔ)上更快尋找到更優(yōu)解，加快算法的收斂速度．例如，對圖5A所示的蜜源進(jìn)行偵查蜂全局搜索，其具體的過程如下：按照基因70%、條件30%的概率來選擇新增加的一行或者一列．比如按上述概率選中了第5個實(shí)驗(yàn)條件，根據(jù)偵查蜂的變異規(guī)則，可知其變異后的蜜源(圖5B)．

圖5　偵查蜂進(jìn)行全局搜索的例子

2.2.4蜜源替換規(guī)則在多目標(biāo)問題上，不同的決策者目標(biāo)的側(cè)重程度不一樣．對于基因表達(dá)數(shù)據(jù)，當(dāng)子矩陣控制在一定的均方殘差閾值下，子矩陣尺寸大小相對比均方殘差重要．因此當(dāng)2個目標(biāo)不能兼優(yōu)時，通過犧牲均方殘差這一指標(biāo)，讓雙聚類的尺寸達(dá)到更優(yōu)．本文通過改進(jìn)CI指標(biāo)[10]，定義ObjVal指標(biāo)，具體表達(dá)式如下：

(5)

在蜜源Foodi和蜜源Foodj的替換選擇問題上，結(jié)合Pareto支配關(guān)系[13]建立以下蜜源替換規(guī)則來判別兩者的優(yōu)劣，蜜源Foodi優(yōu)于Foodj須滿足以下任一條件：

(1)FoodiPareto支配Foodj，即Foodi?Foodj；

(2)若2個蜜源間無支配關(guān)系，滿足：ObjVali>ObjValj．

2.2.5輪盤賭改進(jìn)策略在多目標(biāo)人工蜂群算法中，蜜源的質(zhì)量是由平均平方殘差和尺寸共同決定．所以對傳統(tǒng)蜂群算法的輪盤賭概率進(jìn)行改進(jìn)，確定選取的概率：

(6)

該指標(biāo)結(jié)合ObjVal指標(biāo)并引入最小選擇概率α，可以保證每個蜜源至少有α的概率被觀察蜂選中，這為質(zhì)量較差的蜜源提供一定的機(jī)會，保證了種群的多樣性．

2.2.6外部檔案的維護(hù)本文使用外部檔案來維護(hù)種群的Pareto最優(yōu)解集[13]，外部檔案的大小與蜜源的個數(shù)都設(shè)定為SN．外部檔案具體維護(hù)過程如下：首先，外部檔案保留了上一代的種群，并把該代進(jìn)化后的新一代種群也并入外部檔案當(dāng)中；然后，通過NSGA-Ⅱ算法[13]的非劣排序和擁擠距離的方法來維護(hù)外部檔案，對其進(jìn)行修剪，使得在下一代開始之前，外部檔案始終保留了當(dāng)前SN個最優(yōu)蜜源并為下一代提供更優(yōu)的初始種群．這種外部檔案的維護(hù)方式能保證種群盡可能收斂于Pareto最優(yōu)解集，同時也維持了種群內(nèi)個體的多樣性．

2.3多目標(biāo)人工蜂群雙聚類算法的實(shí)現(xiàn)

多目標(biāo)人工蜂群雙聚類算法的大致實(shí)現(xiàn)描述如下：第一階段，初始化SN個蜜源并依據(jù)2.2節(jié)設(shè)計(jì)的編碼規(guī)則對每個蜜源進(jìn)行編碼；第二階段，依據(jù)2.2節(jié)設(shè)計(jì)的搜索、選擇、更新規(guī)則對蜜源進(jìn)行鄰域和全局搜索、選擇以及更新；第三階段，依據(jù)2.2節(jié)設(shè)計(jì)的外部檔案的維護(hù)規(guī)則從更新后的蜜源中篩選出SN個蜜源作為下一代蜜源.最后，重復(fù)第二、三階段，直到蜜源進(jìn)化到規(guī)定的代數(shù)，輸出這SN個蜜源.多目標(biāo)人工蜂群算法的詳細(xì)實(shí)現(xiàn)可參考其偽代碼(算法1)．

算法1MOABCB

輸入：基因表達(dá)數(shù)據(jù)矩陣，蜜源個數(shù)SN，MSR閾值δ，代數(shù)n，未更新系數(shù)閾值Limit；

輸出：雙聚類集

step1.隨機(jī)產(chǎn)生SN個不同蜜源，生成第一代種群P0，設(shè)置未更新系數(shù)trial(i)=0；

step2.將種群P0置入外部檔案；

step3.for種群代數(shù)iter=1 tondo

step4.所有采蜜蜂根據(jù)鄰域搜索方式進(jìn)行局部搜索，再按照蜜源替換規(guī)則進(jìn)行更新，未更新蜜源的未更新系數(shù)加1，即trial(i)=trial(i)+1;

step5.根據(jù)式(6)計(jì)算概率pi；觀察蜂根據(jù)概率pi選擇蜜源并按其搜索方式進(jìn)行局部搜索，然后按照蜜源替換規(guī)則進(jìn)行更新，對未更新蜜源的未更新系數(shù)加1，即trial(i)=trial(i)+1;

step6.如果trial(i)>Limit，重置未更新系數(shù)trial(i)，偵查蜂按其搜索方式進(jìn)行全局搜索；

step7.將更新后的蜜源并入外部檔案，對檔案中所有蜜源進(jìn)行非劣排序，計(jì)算擁擠距離；

step8.根據(jù)非劣排序秩次和擁擠距離大小，保留SN個蜜源在外部檔案中，生成下一代種群Pi；

Step9.end for

Step10.return 雙聚類集．

3結(jié)果與分析

實(shí)驗(yàn)使用的數(shù)據(jù)分別為酵母菌和人類B細(xì)胞數(shù)據(jù)集[4]．其中，酵母菌數(shù)據(jù)收集了2 884個基因在17種不同條件下的表達(dá)數(shù)據(jù)，所有值位于0～600之間，其中34個缺失值用0～800的隨機(jī)數(shù)代替．人類B細(xì)胞數(shù)據(jù)集收集了4 026個基因和96種不同條件下的表達(dá)數(shù)據(jù)，其值位于-750～650之間，其中12.3%的缺失值用-800～800的隨機(jī)數(shù)代替．表1和表2呈現(xiàn)了各算法在2套數(shù)據(jù)集上的參數(shù)設(shè)置．

3.1實(shí)驗(yàn)結(jié)果的統(tǒng)計(jì)意義驗(yàn)證

采用CI指標(biāo)[10]2470對算法所得的雙聚類結(jié)果進(jìn)行綜合評估：

(7)

CI指標(biāo)越小，說明雙聚類的平均尺寸越大，且平均均方殘差越小，因此雙聚類綜合質(zhì)量越高．

表1　各個算法在酵母菌數(shù)據(jù)集上的參數(shù)設(shè)置

從表3看出，多目標(biāo)人工蜂群雙聚類算法所得結(jié)果的CI指標(biāo)為0.018 9，所得雙聚類的綜合質(zhì)量優(yōu)于其他比較算法．另外，獲得的雙聚類集的平均基因數(shù)較多，尺寸相對大．驗(yàn)證了多目標(biāo)人工蜂群雙聚類算法在酵母菌數(shù)據(jù)集上的測試結(jié)果在收斂性和多樣性上具有較優(yōu)的性能．

表2各個算法在人類B細(xì)胞數(shù)據(jù)集上的參數(shù)設(shè)置

Table 2The parameter settings of each algorithm in Human B cell dataset

算法聚類個數(shù)種群代數(shù)δ交叉概率變異概率MOEB[10]24705040012000.750.03SPEA2B[10]24705040012000.750.03OMOACOB[16]2001001200——MOABCB504001200——

表3　各算法在酵母菌數(shù)據(jù)集的結(jié)果比較

由表4可知，多目標(biāo)人工蜂群雙聚類算法的CI指標(biāo)為0.029 2，小于其他比較算法，所找到的雙聚類綜合質(zhì)量同樣優(yōu)于其他比較算法．另外，對比于其他比較算法，本文算法能獲得的雙聚類集的平均基因數(shù)、平均尺寸、最大尺寸較大．驗(yàn)證本文算法在人類B細(xì)胞數(shù)據(jù)集上的測試結(jié)果在收斂性和多樣性上具有較優(yōu)的性能．

3.2研究結(jié)果的生物學(xué)意義驗(yàn)證

3.2.1GO分析基因本體論(Gene Ontology，GO)數(shù)據(jù)庫[18]，是目前應(yīng)用最廣泛的基因注釋體系之一．通過對雙聚類進(jìn)行GO分析，可根據(jù)P值定位最可能相關(guān)的GO Term，從而通過已標(biāo)注功能的基因來預(yù)測未標(biāo)注基因的功能．本文采用GOTooLBox工具[19]對酵母菌數(shù)據(jù)集上發(fā)現(xiàn)的雙聚類進(jìn)行GO分析．表5列舉了3個GO節(jié)點(diǎn)具有顯著意義的雙聚類結(jié)果，選擇其中一個結(jié)果來進(jìn)行闡釋．雙聚類C45有11個基因參與繁殖過程， 11個與RNA指導(dǎo)的DNA聚合酶功能相關(guān)， 18個與逆轉(zhuǎn)錄轉(zhuǎn)座子殼蛋

表4　各算法在人類B細(xì)胞數(shù)據(jù)集的結(jié)果比較

表5　3個GO節(jié)點(diǎn)具有顯著意義的雙聚類結(jié)果

白的形成有關(guān)．由其P值均小于0.05可知，雙聚類C45在基因的生物過程、分子功能及細(xì)胞組分等3個方面均具有顯著的生物意義．這說明了本文算法能挖掘出有顯著生物意義的雙聚類．

3.2.2KEGG通路分析京都基因與基因組百科全書 (Kyoto Encyclopedia of Genes and Genomes，KEGG)[20]用于將基因及表達(dá)信息作為一個整體進(jìn)行研究．通過KEGG的pathway分析，可根據(jù)P值發(fā)現(xiàn)較顯著的代謝通路．采用基于網(wǎng)絡(luò)訪問的功能注釋系統(tǒng)(the Database for Annotation Visualization and Integrated Discovery，DAVID)工具[21]對所發(fā)現(xiàn)的雙聚類進(jìn)行通路富集分析．表6列舉了2個富集代謝通路具有顯著意義的雙聚類結(jié)果,選擇其中一個結(jié)果進(jìn)行闡釋．雙聚類C24有谷氨酸脫羧酶、精脒合酶等7個基因富集在β-丙氨酸代謝通路中．由其P值為0.016可知，雙聚類C24在β-丙氨酸代謝通路出現(xiàn)了顯著的富集．這說明了本文算法能挖掘出有顯著生物意義的雙聚類．

表6　2個富集代謝通路具有顯著意義的雙聚類結(jié)果

4結(jié)語

提出了一個應(yīng)用多目標(biāo)人工蜂群算法來尋找雙聚類問題的框架，并在算法的編碼、不同蜂種的搜索方案、蜜源質(zhì)量評價和外部檔案修剪等環(huán)節(jié)進(jìn)行了關(guān)鍵的設(shè)計(jì)，加大了算法的局部和全局搜索能力，使結(jié)果更逼近全局最優(yōu)解．將本文算法在酵母菌和人類B細(xì)胞數(shù)據(jù)集上與多個基于多目標(biāo)優(yōu)化的雙聚類算法獲得的實(shí)驗(yàn)結(jié)果進(jìn)行比較,結(jié)果表明本文算法能挖掘到更優(yōu)的雙聚類，同時，所得的種群具有較好的多樣性和收斂性．最后，利用了GO和KEGG這2個生物數(shù)據(jù)庫驗(yàn)證了本文算法可以挖掘出具有顯著生物意義的雙聚類結(jié)果．然而，隨著高通量微陣列技術(shù)的繼續(xù)發(fā)展，該算法難免會遇到單機(jī)內(nèi)存不足以及CPU處理能力的瓶頸，如何將算法進(jìn)行并行優(yōu)化設(shè)計(jì)以提高其擴(kuò)展性將是未來工作的一個重點(diǎn)．

參考文獻(xiàn)：

[1]李霞，李亦學(xué)，廖飛.生物信息學(xué)[M].北京：人民衛(wèi)生出版社, 2010：188-189.

[2]LUO F, KHAN L, KHAN L. Hierarchical clustering of gene expression data[C]∥Proceedings of the 3rd IEEE Conference on Bioinformatics and Bioengineering.USA:IEEE Computer Society, 2003,67(3):328-335.

[3]SHERLOCK G. Analysis of large-scale gene expression data[J].Brief Bioinform, 2001, 2(4):350-362.

[4]CHENG Y, CHURCH G M. Biclustering of expression data[C]∥Proceeding of the 8th International Conference on Intelligent Systems for Molecular Biology. New York:ACM Press, 2000:93-103.

[5]YANG J, WANG H, WANG W, et al. Enhanced biclustering on expression data[C]∥Proceedings of the 3rd IEEE Conference on Bioinformatics and Bioengineering. Maryland：IEEE Computer Society, 2003:321-327.

[6]BEN-DOR A, CHOR B, KARP R, et al. Discovering local structure in gene expression data: the order-preserving submatrix problem[J].Journal of Computational Biology, 2003, 10(3/4): 373-384.

[7]ZHANG Z, TEO A, OOI B C, et al. Mining deterministic biclusters in gene expression data[C]∥Proceeding of the 4th IEEE Symposium on Bioinformatics and Bioengineering. Taiwan: IEEE Computer Society, 2004: 283-290.

[8]BLEULER S, PRELIC A, ZITZLER E. An EA frame work for biclustering of gene expression data[C]∥Proceedings of the 2004 Congress on Evolutionary Computation. Switzerland:IEEE Computer Society, 2004: 166-173.

[9]BRYAN K, CUNNFNGHAM P, BOLSHAKOVA N. Biclustering of expression data using simulated annealing[C]∥Proceedings of the 18th IEEE Symposium on Computer-Based Medical Systems. Ireland: IEEE Computer Society, 2005:1063-7125.

[10]MITRA S, BANKA H. Multi-objective evolutionary biclustering on gene expression data[J]. Pattern Recognition, 2006, 39(12):2464-2477.

[11]BRIZUELA C A, LUNA-TAYLOR J E, MARTINEZ-PEREZ I, et al. Improving an Evolutionary Multi-objective Algorithm for the Biclustering of Gene Expression Data[C]∥IEEE Congress on Evolutionary Computation. Mexico: IEEE Computer Society, 2013:221-228.

[12]LIU J W, LI Z J, LIU F F, et al. Multi-objective particle swarm optimization biclustering of microarray data[C]∥IEEE International Conference on Bioinformatics and Biomedicine. Philadelphia:IEEE Computer Society, 2008: 363-366.

[13]LIU J W, LI Z J, HU X H. Biclustering of microarray data with MOSPO based on crowding distance[J].BMC Bioinformatics, 2009, 10(4):59.

[14]KARABOGA D. An idea based on honey bee swarm for numerical optimization, Technical Report-TR06[R]. Kayseri: Erciyes University, 2005.

[15]張超群, 鄭建國, 王翔. 蜂群算法研究綜述[J].計(jì)算機(jī)應(yīng)用研究,2011,28(9):3201-3205.

ZHANG C Q, ZHENG J G, WANG X.Overview of research on bee colony algorithms[J]. Application Research of Computers,2011,28(9): 3201-3205.

[16]LIU J W, LI Z J, HU X H, et al. Online MOACO biclustering of microarray data[C]∥IEEE International Conference on Granular Computing. Kaohsiung: IEEE Computer Society, 2011: 431.

[17]LIU J W, LI Z J,HU X H, et al. Multi-objective dynamic population shuffled frogleaping biclustering of microarray data[C]∥IEEE International Conference on Bioinformatics and biomedicine. Atlanta: IEEE Computer Society, 2011: 155.

[18]ASHBURNER M. Gene ontology:tool for the unification of biology[J]. Nature Genetics, 2000, 25(1):25.

[19]MARTIN D, BRUN C, REMY E, et al. GOToolBox:functional analysis of gene datasets based on Gene Ontology[J].Genome Biology,2004,5(12):6.

[20]KANEHISA M，GOTO S．KEGG: Kyoto encyclopedia of genesand genomes[J].Nucleic Acids Research，2000，28(1):27-30．

[21]HUANG D W, SHERMAN B T, TAN Q W E, et al. DAVID bioinformatics resources: expanded annotation database and novel algorithms to better extract biology from large gene lists[J]. Nucleic Acids Research, 2007, 35(S2): 172.

【中文責(zé)編：莊曉瓊英文責(zé)編：肖菁】

Research and Application of Multi-Objective Artificial Bee Colony Biclustering in Gene Expression Data

LIN Qin1, XUE Yun2*, LIN Sida3, HE Mingqing3

(1.School of Information Engineering, Guangdong Medical College, Dongguan 523808, China；2.School of Physics and Telecommunication Engineering, South China Normal University, Guangzhou 510006, China；3. School of Public Health, Guangdong Medical College, Dongguan 523808, China)

Abstract：Biclustering algorithms based on multi-objective optimization, which can optimize several objectives simultaneously in conflict with each other, such as the mean squared residue and the size. In order to mine better biclusters with lower mean squared residue but larger size, a novel algorithm named Multi-objective Artificial Bee Colony Biclustering is proposed. Firstly, the approach adopts a group based representation for the genes-conditions associations to encode foods, then two different crossovers and a mutation operation are used to realize local search and global search respectively. Consequently, the non-dominated sort and crowding distance are applied to prune external archives. Experiments are performed on two real gene expression datasets, and it is found that compared with competing algorithms, the method has better global astringency and diversity of the population. Besides, it can obtain significantly biological biclusters.

Key words：gene expression data; biclustering; multi-objective optimazition; artificial bee colony

中圖分類號：TP391

文獻(xiàn)標(biāo)志碼：A

文章編號:1000-5463(2016)02-0116-08

*通訊作者:薛云，副教授，Email:xueyun@scnu.edu.cn.

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(71272084，71102146)；廣東省教育部產(chǎn)學(xué)研結(jié)合項(xiàng)目(2012B091100349)；廣東醫(yī)學(xué)院面上基金項(xiàng)目(XK1330)；廣東醫(yī)學(xué)院大學(xué)生創(chuàng)新實(shí)驗(yàn)重點(diǎn)項(xiàng)目(2014FZDG003)

收稿日期：2015-07-16《華南師范大學(xué)學(xué)報(bào)(自然科學(xué)版)》網(wǎng)址：http://journal.scnu.edu.cn/n