李 梁，陳佳瑜

(重慶理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 400054)

基于粒子群算法的基因表達(dá)譜聚類分析方法

李 梁，陳佳瑜

(重慶理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 400054)

雙向聚類算法可以發(fā)現(xiàn)基因表達(dá)譜中隱藏的信息。為了尋找規(guī)模較大的基因相似矩陣，結(jié)合粒子群算法強(qiáng)大的搜索能力，提出了GP-Cluster雙向聚類算法?；诹Ｗ尤?PSO)算法，引入Sigmoid函數(shù)進(jìn)行動(dòng)態(tài)調(diào)整，并在粒子飛行過程中加入了遺傳算法(GA)“優(yōu)勝劣汰”的思想，增加粒子運(yùn)動(dòng)的多變性和隨機(jī)性，避免算法陷入局部最優(yōu)。實(shí)驗(yàn)結(jié)果證明:相比GA算法和PSO算法，改進(jìn)后的混合粒子群算法GP-Cluster能找到質(zhì)量更佳的雙向聚類，取得更好的聚類效果。

數(shù)據(jù)挖掘；基因表達(dá)譜；雙向聚類；粒子群算法；遺傳算法

隨著生物技術(shù)的迅速發(fā)展，出現(xiàn)了基因芯片和DNA微陣列等高通量檢測技術(shù)，人們已經(jīng)可以對(duì)某一特定狀態(tài)下的組織或細(xì)胞進(jìn)行基因表達(dá)譜的測序。而具有相似表達(dá)譜的基因之間很有可能存在某種聯(lián)系，可以通過聚類的方法，將表達(dá)水平相近的基因聚在同一個(gè)類中，從而發(fā)現(xiàn)未知基因的功能和具有生物科學(xué)價(jià)值的基因信息。

目前，基因表達(dá)數(shù)據(jù)分析最常用的方法是聚類。但是傳統(tǒng)的聚類方法在分析基因數(shù)據(jù)時(shí)會(huì)受到很大的限制，因?yàn)槟承┗蛑辉诓糠痔囟l件下才會(huì)表現(xiàn)出相似特性，而不是這些基因在所有條件下表現(xiàn)都相似。為了更好地尋找有價(jià)值的基因聚類，Cheng和Curch[1]于2000年提出了一種基于貪心策略的雙向聚類算法(又稱CC算法)，第1次將雙向聚類應(yīng)用于基因表達(dá)譜的聚類上。該算法拋棄了傳統(tǒng)聚類只從單方向上尋找相似特征的方法，而是同時(shí)從行和列兩個(gè)方向進(jìn)行聚類，這樣可以找到隱藏在局部數(shù)據(jù)中的生物信息。其基本思想是通過刪除或添加某些行和列減少基因矩陣在表達(dá)上的差異性，從而產(chǎn)生雙向聚類。

本文針對(duì)基因表達(dá)譜聚類的復(fù)雜性和多變性，提出了一種基于粒子群算法(particle swarm optimization,PSO)和遺傳算法(genetic algorithm,GA)的混合雙向聚類算法，稱為GP-Cluster算法。

1 雙向聚類

CC算法在被提出時(shí)就給出了雙向聚類(bicluster)的定義：

定義1 設(shè)X是基因集，Y是對(duì)應(yīng)的表達(dá)條件集，aij是基因表達(dá)矩陣A中的元素。設(shè)I,J分別為X,Y的子集，則(I,J)對(duì)指定的子矩陣Aij具有以下平均平方殘差：

(1)

雙向聚類的目的就是從基因表達(dá)矩陣中找到滿足條件的子矩陣，使子矩陣在表達(dá)波動(dòng)上盡可能一致。目前應(yīng)用比較廣泛的雙向聚類的模型有4種：等值模型、加法模型、乘法模型和信息共演變模型[2]。

2 粒子群算法和遺傳算法

2.1 粒子群算法

相較于其他群體智能算法，粒子群優(yōu)化算法具有概念簡明、易于實(shí)現(xiàn)、收斂速度快、參數(shù)數(shù)量少等特點(diǎn)，是一種高效的搜索算法[3-5]。同時(shí)也存在一些缺點(diǎn)，PSO算法在求解復(fù)雜多峰問題[6]時(shí)速度較慢，容易陷入早熟，并且算法的收斂精度不高[7]。

在PSO算法中，每一個(gè)粒子(particle)都代表一個(gè)解，一系列的粒子組成群(swarm)。與其他群體智能算法不同，粒子群算法是將每個(gè)粒子個(gè)體看成解空間中的一個(gè)沒有體積和質(zhì)量的微粒，以一定的速度飛行尋找最優(yōu)解，這個(gè)速度是根據(jù)粒子自身的飛行經(jīng)驗(yàn)和其相鄰粒子的飛行經(jīng)驗(yàn)共同決定并進(jìn)行動(dòng)態(tài)調(diào)整的[8]。通常情況下，粒子追隨當(dāng)前的最優(yōu)粒子活動(dòng)，經(jīng)過逐代搜索最后得到最優(yōu)解。

標(biāo)準(zhǔn)粒子群算法的數(shù)學(xué)描述如下[9]：

設(shè)有D維搜索空間，總的粒子數(shù)為N。Xi=(xi1,xi2,…,xin)為第i個(gè)粒子的當(dāng)前位置；Vi=(vi1,vi2,…,vin)為第i個(gè)粒子的當(dāng)前飛行速度；第i個(gè)粒子在飛行過程中的最優(yōu)位置為Pi=(pi1,pi2,…,pin)，所有粒子的全局最優(yōu)位置為Pg=(pg1,pg2,…,pgn)。每個(gè)粒子的位置變化公式為：

Vid(t+1)=wvid(t)+c1r1(pid(t)-

xid(t))+c2r2(pgd(t)-xid(t))

(2)

Xid(t+1)=xid(t)+vid(t+1)

1≤i≤n,1≤d≤D

(3)

其中：w為慣性權(quán)重，w較大時(shí)適合對(duì)解空間進(jìn)行大范圍的搜索，w較小時(shí)適合進(jìn)行小范圍的搜索；c1,c2是學(xué)習(xí)因子，為常數(shù)；r1,r2是[0,1]之間的隨機(jī)數(shù)；vid=[-vmax,vmax]，vmax是常數(shù)。

2.2 遺傳算法

遺傳算法是一種隨機(jī)搜索算法，它借鑒了生物界的遺傳選擇機(jī)制，適合處理復(fù)雜的非線性優(yōu)化問題。

遺傳算法的基本思想是“優(yōu)勝劣汰，適者生存”，模擬自然界的生物由低級(jí)向高級(jí)的演化過程，根據(jù)問題的目標(biāo)函數(shù)構(gòu)造一個(gè)適應(yīng)度函數(shù)，問題的每一個(gè)解都對(duì)應(yīng)1條染色體，對(duì)1個(gè)由多個(gè)解構(gòu)成的種群進(jìn)行初始化、變異、交叉，經(jīng)過多代繁衍，將獲得的適應(yīng)值最好的個(gè)體作為問題的最優(yōu)解。

遺傳算法可以形式化地描述為

GA=(POP(t),N,l,s,g,p,f,t)

(4)

式(4)中：l表示染色體的二進(jìn)制串的長度；s代表選擇策略；g表示遺傳算子；p表示遺傳算子的操作概率；f表示適應(yīng)度函數(shù)；t為終止條件。

遺傳算法從初始給定的多個(gè)解開始，通過一定的規(guī)則逐步迭代產(chǎn)生新解。初始給定的多個(gè)解的集合被稱為種群，它是問題的解空間里的一個(gè)子集，記為POP(t)，其中t為迭代步，POP(t)中每一個(gè)個(gè)體的適應(yīng)度為fi=fitness(POPi(t))。

相較于粒子群算法，遺傳算法采用二進(jìn)制編碼，因此更適合求解離散型問題，特別是0-1非線性優(yōu)化問題[10-11]。粒子群算法沒有交叉和變異操作，而是根據(jù)自己的速度來決定搜索方向，并且每一個(gè)粒子都擁有記憶功能，能記住搜尋到的最佳位置。

3 混合粒子群算法模型

在本算法中，每一個(gè)粒子都看成是一個(gè)小的雙向聚類。在粒子運(yùn)動(dòng)中，表達(dá)相似的粒子合在一起成為一個(gè)新的較大的雙向聚類。算法以隨機(jī)產(chǎn)生的解為初始解，通過二進(jìn)制編碼，以上一代粒子的平方殘差值H為適應(yīng)度函數(shù)，采取精英選擇策略，保存較優(yōu)的粒子進(jìn)入下一次迭代。為了防止算法收斂過早，使粒子的運(yùn)動(dòng)陷入局部最優(yōu)，在迭代尋優(yōu)的過程中引入了遺傳算法的交叉、變異的操作，使粒子的運(yùn)動(dòng)更隨機(jī)多變。

3.1 慣性權(quán)重調(diào)整

在粒子群算法中，慣性權(quán)重平衡著粒子的全局和局部搜索能力[12]，具體是指上一代粒子速度對(duì)當(dāng)前代粒子速度的影響。權(quán)重較大時(shí)，算法的全局搜索能力較強(qiáng)；權(quán)重較小時(shí)，算法的局部搜索能力較強(qiáng)。本文粒子群算法的權(quán)重引入Sigmoid函數(shù)使其進(jìn)行非線性遞減[13]。實(shí)驗(yàn)結(jié)果表明：動(dòng)態(tài)調(diào)整慣性權(quán)重可以得到較好的結(jié)果，并能提高問題的求解效率。

(5)

式(5)中w0和λ為常數(shù)。

3.2 編碼方式

設(shè)A是一個(gè)M行N列的基因表達(dá)矩陣，M為實(shí)驗(yàn)條件數(shù)，N為基因個(gè)數(shù)。對(duì)任意一個(gè)基因或條件，只可能有2種情況：一種是在算法最終產(chǎn)生的雙向聚類里面；一種是不在最后的雙向聚類里面。所以，算法需要采用0-1二進(jìn)制編碼。每一個(gè)粒子都由一個(gè)0-1二進(jìn)制串構(gòu)成，這個(gè)二進(jìn)制串的長度為N+M，即為基因數(shù)N和條件數(shù)M的和，前N位編碼基因，后M位編碼實(shí)驗(yàn)條件。若基因或條件在雙聚類里面，則對(duì)應(yīng)位置上的值為1；若不在，就設(shè)為0。設(shè)粒子種群規(guī)模為P，則粒子初始位置X就是一個(gè)P行的0-1向量組成的矩陣。

3.3 算法描述

GP-Cluster算法最后是要尋找均方殘差值H越小越好的最優(yōu)解，具體算法描述如下：

1) 初始化種群規(guī)模P、加速因子、權(quán)重因子、最大迭代次數(shù)等參數(shù)，產(chǎn)生初始粒子X和速度V。

2) 計(jì)算目標(biāo)函數(shù)值，產(chǎn)生第1代粒子的均方殘差值。

3) 初始化個(gè)體極值和群體極值：挑出第1代粒子中最好的個(gè)體，也就是均方殘差值H最小的個(gè)體。

4) 迭代尋優(yōu)：先要對(duì)每一代粒子都計(jì)算1次自適應(yīng)的權(quán)值，更新粒子的速度和位置，對(duì)粒子進(jìn)行交叉和變異的操作，然后計(jì)算目標(biāo)函數(shù)值，更新個(gè)體最優(yōu)和群體最優(yōu)。

5) 當(dāng)前迭代次數(shù)到達(dá)初始設(shè)定的最大迭代次數(shù)時(shí)，算法結(jié)束。

4 實(shí)驗(yàn)及結(jié)果分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

急性白血病基因表達(dá)譜(leukaemia)數(shù)據(jù)集[14]共有38個(gè)急性白血病樣本和7 129個(gè)基因，其中：27個(gè)被診斷為急性淋巴性白血病(ALL)；11個(gè)被診斷為急性骨髓性白血病( AML)。乳腺癌基因表達(dá)譜(breast cancer)數(shù)據(jù)集[15]共有1 213個(gè)基因和98個(gè)樣本，其中：34例在5年內(nèi)癌細(xì)胞發(fā)生轉(zhuǎn)移；44例表現(xiàn)正常；20例BRCA基因變異。

4.2 實(shí)驗(yàn)分析

雙向聚類算法實(shí)驗(yàn)使用Matlab對(duì)數(shù)據(jù)進(jìn)行分析和處理，采取Max-Min方法對(duì)數(shù)據(jù)進(jìn)行歸一化處理，如式(6)所示。其中：x是樣本數(shù)據(jù)中的原始值；X是標(biāo)準(zhǔn)化后的值。

(6)

算法的結(jié)束條件，即最大迭代次數(shù)為200；種群規(guī)模為200；加速因子c1,c2為0.15。粒子的最大速度和最小速度不宜過大，否則容易收斂過早，陷入局部最優(yōu)。本研究把最大速度設(shè)為0.1，最小速度設(shè)為-0.1，交叉率為0.8，變異率為0.2。

分別用粒子群算法、遺傳算法和本文中提出的GP-Cluster算法對(duì)上述2個(gè)數(shù)據(jù)集進(jìn)行測試。測試結(jié)果見表1～2和圖1～4。

表1 急性白血病數(shù)據(jù)集實(shí)驗(yàn)結(jié)果比較

表2 乳腺癌基因表達(dá)數(shù)據(jù)實(shí)驗(yàn)結(jié)果比較

圖1 GP-Cluster(急性白血病)迭代曲線

圖2 GA(急性白血病)迭代曲線

圖3 GP-Cluster(乳腺癌)迭代曲線Fig.3 Iterative curve of GP-Cluster(Breast cancer)

圖4 GA(乳腺癌)迭代曲線

本文采用均方殘差值、雙聚類規(guī)模、基因數(shù)與條件數(shù)的比值、對(duì)原基因矩陣的覆蓋率和算法運(yùn)行時(shí)間這5個(gè)指標(biāo)來評(píng)價(jià)聚類結(jié)果質(zhì)量。其中：均方殘差值為10次實(shí)驗(yàn)得到的所有均方殘差值的平均值，越小越好；規(guī)模就是算法產(chǎn)生的基因聚類矩陣的大小，其值越大越好；行列比即基因聚類矩陣中基因數(shù)與條件數(shù)的比值，在均方殘差值相同的情況下，這個(gè)值越小越好。

與粒子群算法相比，從表1、2中明顯可以看出：改進(jìn)后的GP-Cluster算法的均方殘差值比粒子群算法的均方殘差值減小了一個(gè)數(shù)量級(jí)，改進(jìn)效果十分明顯；從雙向聚類的規(guī)模上看，GP-Cluster算法得到的聚類規(guī)模和覆蓋率都比PSO算法要略大一些，尤其從行列分配上看，GP-Cluster算法的基因數(shù)和條件數(shù)的分布更加均勻。也就是說，GP-Cluster算法產(chǎn)生的雙向聚類盡可能多地同時(shí)覆蓋了原基因矩陣中的基因和條件。所以，GP-Cluster產(chǎn)生的雙聚類質(zhì)量要高于粒子群算法所產(chǎn)生的雙聚類的質(zhì)量。

遺傳算法和GP-Cluster算法的均方殘差相差不大，遺傳算法的均方殘差要略小一點(diǎn)，但是在雙聚類的規(guī)模上GP-Cluster算法產(chǎn)生的雙聚類的行數(shù)和列數(shù)都有所增加，尤其是在列數(shù)上增加明顯，這樣就導(dǎo)致了行列比比遺傳算法的行列比小了近一半，對(duì)原基因矩陣的覆蓋率也比遺傳算法高了近1倍。因此，GP-Cluster算法產(chǎn)生的雙聚類的質(zhì)量優(yōu)于遺傳算法產(chǎn)生的雙聚類的質(zhì)量。從圖1、2上可以看出：GP-Cluster算法在迭代150次時(shí)就達(dá)到了遺傳算法170次左右的效果。從圖3、4上可以看出：GP-Cluster算法迭代到50次時(shí)就達(dá)到了遺傳算法迭代150次時(shí)的效果。由此可以說明：GP-Cluster收斂較快，比遺傳算法效率更高。

雖然結(jié)合了遺傳算法的混合粒子群優(yōu)化算法找到的雙聚類質(zhì)量更佳，但是從算法運(yùn)行所花費(fèi)的時(shí)間上看，GP-Cluster算法消耗的時(shí)間明顯增加。

5 結(jié)束語

分析基因表達(dá)數(shù)據(jù)具有重要的醫(yī)學(xué)價(jià)值和生物研究意義。本文介紹了一種基于遺傳算法和粒子群算法的雙向聚類算法——GP-Cluster雙向聚類算法。它將遺傳算法中的“優(yōu)勝劣汰”思想引入到了粒子群算法中，平衡了局部搜索和全局搜索的關(guān)系，大大改進(jìn)了粒子群算法在解決雙聚類問題上易陷入局部最優(yōu)的不足。兩組實(shí)驗(yàn)結(jié)果表明：改進(jìn)后的混合優(yōu)化算法對(duì)解決基因表達(dá)譜聚類問題表現(xiàn)出了較為理想的效果，能找到更優(yōu)的基因相似矩陣。但GP-Cluster算法也存在不足，那就是計(jì)算量大，花費(fèi)時(shí)間較多，有待繼續(xù)改進(jìn)。

[1] CHENG Y,CHURCH G M.Biclustering of Expression Data[C]//Proceeding of the 8th International Conference on Intelligent Systems for Molecular Biology.ACM Press.(ISMB’00).2000:93-103.

[2] 張敏,戈文航.雙聚類的研究與進(jìn)展[J].微型機(jī)與應(yīng)用,2012，31(4):4-10.

ZHANG Min,GE Wenhang.Research and progress of double clustering[J].Micro computer and application,2012,31(4):4-10.

[3] 周康渠，趙慧真． 混合離散粒子群算法在混流裝配線生產(chǎn)調(diào)度中的應(yīng)用[J]． 重慶理工大學(xué)學(xué)報(bào)(自然科學(xué))，2015(3):58-64．

ZHOU Kangqu，ZHAO Hu-zhen． Application on Scheduling of Mixed Model Assembly Lines with Hybrid Distribution Particle Swarm Optimization Algorithm[J]． Journal of Chongqing University of Technology(Natural Science)，2015(3):58-64．

[4] 劉敏,李智彪.基于粒子群優(yōu)化脈沖耦合神經(jīng)網(wǎng)絡(luò)的紅外圖像分割[J].激光雜志,2016(2):50-53.

LIU Min，LI Zhi-biao.Infrared Image Segmentation Based on Particle Swarm Optimization Pulse Coupled Neural Network[J].Laser Journal,2016(2):50-53.

[5] 孫延維,彭智明,李健波.基于粒子群優(yōu)化與模糊聚類的社區(qū)發(fā)現(xiàn)算法[J].重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,27(5):660-666.

SUN Yanwei，PENG Zhiming，LI Jianbo.Community detection algorithm based on particle swarmoptimization and fuzzy clustering[J].Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition),2015,27(5):660-666.

[6] 周文剛,趙宇．具有完全學(xué)習(xí)策略的量子行為粒子群癌癥基因聚類算法[J].北京郵電大學(xué)學(xué)報(bào),2014，37(4):59-63.

ZHOU Wengang,ZHAO Yu.A complete learning strategies quantum-behaved particle swarm cancer gene clustering algorithm[J].Journal of Beijing university of posts and telecommunications,2014 37(4):59-63.

[7] 梁軍.粒子群算法在最優(yōu)化問題中的研究[D].南寧：廣西師范大學(xué)，2008.LIANG Jun.The particle swarm algorithm in the optimization research[D].Nanning:Guangxi normal university,2008.[8] 謝曉鋒,文俊,楊之廉．微粒群算法綜述[J]．控制與決策，2003，18(2)：129-142.

XIE Xiaofeng,WEN Jun,YANG Zhilian.Particle swarm algorithm[J].Control and decision,2003,19(2):129-142.

[9] SHI Y,EBERHART R C.Particle swarm optimization:developments,applications and resource[ C] // In:Proc of Congress onEvolutionary Computation.Seoul.Korea:IEEE Service Center.2001:81-86.

[10]林秀芳，陳淑梅，陳金蘭．運(yùn)用遺傳算法的磁流變阻尼器減震的模糊控制[J] ． 重慶理工大學(xué)學(xué)報(bào)(自然科學(xué))，2015(9):64-69．

LIN Xiufang， CHEN Shumei，CHEN Jin lan．Genetic Algorithm-Based Fuzzy Control Strategy for A Magnetorheological Damper[J]．Journal of Chongqing University of Technology(Natural Science)，2015(9):64-69．

[11]陳磊,霍永亮.利用改進(jìn)的遺傳算法求解約束優(yōu)化問題[J].重慶工商大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,31(9):63-67.

CHEN Lei，HUO Yongliang.The Solution to Constrained Optimization Problem by Improved Genetic Algorithm[J].Journal of Chongqing Technology and Business University(Natural Science Edition),2014,31(9):63-67.

[12]劉偉，周育人.一種改進(jìn)慣性權(quán)重的PSO 算法[J].計(jì)算機(jī)工程與應(yīng)用,2009，45(7)：46-48.

LIU Wei,ZHOU Yuren.An improved inertia weight PSO algorithm[J].Computer engineering and application,2009,45(7):46-48.

[13]沈明明，毛力.融合K-調(diào)和均值的混沌粒子群聚類算法[J].計(jì)算機(jī)工程與應(yīng)用,2011，47(27)：144-151.

SHEN Mingming,MAO Li.Fusion K - harmonic mean of chaotic particle cluster algorithm[J].Computer engineering and application,2011，47(27)：144-151.

[14]GOLUB T R,SLONIM D K,TAMAYO P,et al.Molecular classification of cancer:class discovery and class prediction by gene expression monitoring[J].Science,1999,286(15):531-537.

[15]van’t VEER L J,DAI H,van de VIJVER M J,et al.Gene expression profiling predicts clinical outcome of breast cancer[J].Nature,2002,415(6871):530-536.

(責(zé)任編輯 楊黎麗)

Gene Expression Profile Clustering Based on Improved Particle Swarm Algorithm

LI Liang, CHEN Jia-yu

(College of Computer Science and Engineering, Chongqing University of Technology, Chongqing 400054, China)

Bi-clustering algorithm can find the hidden information in the gene expression patterns. In order to find a larger genetic similarity matrix, combined with powerful search ability of particle swarm optimization, GP-Cluster algorithm was proposed. This algorithm was based on particle swarm algorithm (PSO), introducing the Sigmiod function to adjust the weights dynamically, and using the genetic algorithm(GA), the thought of “evolution”, to increase the variability and randomness of particle movements and to avoid algorithm falls into local optimum. The experimental results show that compared with GA algorithm and PSO algorithm, the improved hybrid particle swarm algorithm(GP-Cluster) can find a better quality of bi-clustering.

data mining; gene expression; bi-clustering; particle swarm algorithm; genetic algorithm

2016-08-15 基金項(xiàng)目：重慶市應(yīng)用開發(fā)計(jì)劃項(xiàng)目(CSTC2013yykf A40002).

李梁(1964—)，男，重慶人，副教授，主要從事數(shù)據(jù)挖掘和數(shù)據(jù)倉庫、數(shù)據(jù)庫技術(shù)研究；陳佳瑜(1992—)，女，湖北十堰人，碩士研究生，主要從事數(shù)據(jù)挖掘和數(shù)據(jù)倉庫技術(shù)研究，E-mail：934415724@qq.com。

李梁，陳佳瑜.基于粒子群算法的基因表達(dá)譜聚類分析方法[J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué))，2017(2):89-94.

format：LI Liang, CHEN Jia-yu.Gene Expression Profile Clustering Based on Improved Particle Swarm Algorithm[J].Journal of Chongqing University of Technology(Natural Science)，2017(2):89-94.

10.3969/j.issn.1674-8425(z).2017.02.016

TP301

A

1674-8425(2017)02-0089-06