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

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

?

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

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

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

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

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

1問(wèn)題的描述

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

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

(I?G,J?C)，

(1)

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

(2)

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

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

2.1人工蜂群算法

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

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

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

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

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

圖2　一個(gè)雙聚類(lèi)編碼和譯碼的例子

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

(3)

(4)

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

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

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

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

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

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

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

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

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

(5)

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

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

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

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

(6)

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

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

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

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

算法1MOABCB

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

輸出：雙聚類(lèi)集

step1.隨機(jī)產(chǎn)生SN個(gè)不同蜜源，生成第一代種群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)行更新，對(duì)未更新蜜源的未更新系數(shù)加1，即trial(i)=trial(i)+1;

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

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

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

Step9.end for

Step10.return 雙聚類(lèi)集．

3結(jié)果與分析

實(shí)驗(yàn)使用的數(shù)據(jù)分別為酵母菌和人類(lèi)B細(xì)胞數(shù)據(jù)集[4]．其中，酵母菌數(shù)據(jù)收集了2 884個(gè)基因在17種不同條件下的表達(dá)數(shù)據(jù)，所有值位于0～600之間，其中34個(gè)缺失值用0～800的隨機(jī)數(shù)代替．人類(lèi)B細(xì)胞數(shù)據(jù)集收集了4 026個(gè)基因和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對(duì)算法所得的雙聚類(lèi)結(jié)果進(jìn)行綜合評(píng)估：

(7)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4結(jié)語(yǔ)

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

中圖分類(lèi)號(hào)：TP391

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

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

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

基金項(xiàng)目：國(guó)家自然科學(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