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

李 梁，陳佳瑜

(重慶理工大學 計算機科學與工程學院，重慶 400054)

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

李 梁，陳佳瑜

(重慶理工大學 計算機科學與工程學院，重慶 400054)

雙向聚類算法可以發現基因表達譜中隱藏的信息。為了尋找規模較大的基因相似矩陣，結合粒子群算法強大的搜索能力，提出了GP-Cluster雙向聚類算法。基于粒子群(PSO)算法，引入Sigmoid函數進行動態調整，并在粒子飛行過程中加入了遺傳算法(GA)“優勝劣汰”的思想，增加粒子運動的多變性和隨機性，避免算法陷入局部最優。實驗結果證明:相比GA算法和PSO算法，改進后的混合粒子群算法GP-Cluster能找到質量更佳的雙向聚類，取得更好的聚類效果。

數據挖掘；基因表達譜；雙向聚類；粒子群算法；遺傳算法

隨著生物技術的迅速發展，出現了基因芯片和DNA微陣列等高通量檢測技術，人們已經可以對某一特定狀態下的組織或細胞進行基因表達譜的測序。而具有相似表達譜的基因之間很有可能存在某種聯系，可以通過聚類的方法，將表達水平相近的基因聚在同一個類中，從而發現未知基因的功能和具有生物科學價值的基因信息。

目前，基因表達數據分析最常用的方法是聚類。但是傳統的聚類方法在分析基因數據時會受到很大的限制，因為某些基因只在部分特定條件下才會表現出相似特性，而不是這些基因在所有條件下表現都相似。為了更好地尋找有價值的基因聚類，Cheng和Curch[1]于2000年提出了一種基于貪心策略的雙向聚類算法(又稱CC算法)，第1次將雙向聚類應用于基因表達譜的聚類上。該算法拋棄了傳統聚類只從單方向上尋找相似特征的方法，而是同時從行和列兩個方向進行聚類，這樣可以找到隱藏在局部數據中的生物信息。其基本思想是通過刪除或添加某些行和列減少基因矩陣在表達上的差異性，從而產生雙向聚類。

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

1 雙向聚類

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

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

(1)

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

2 粒子群算法和遺傳算法

2.1 粒子群算法

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

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

標準粒子群算法的數學描述如下[9]：

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

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為慣性權重，w較大時適合對解空間進行大范圍的搜索，w較小時適合進行小范圍的搜索；c1,c2是學習因子，為常數；r1,r2是[0,1]之間的隨機數；vid=[-vmax,vmax]，vmax是常數。

2.2 遺傳算法

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

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

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

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

(4)

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

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

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

3 混合粒子群算法模型

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

3.1 慣性權重調整

在粒子群算法中，慣性權重平衡著粒子的全局和局部搜索能力[12]，具體是指上一代粒子速度對當前代粒子速度的影響。權重較大時，算法的全局搜索能力較強；權重較小時，算法的局部搜索能力較強。本文粒子群算法的權重引入Sigmoid函數使其進行非線性遞減[13]。實驗結果表明：動態調整慣性權重可以得到較好的結果，并能提高問題的求解效率。

(5)

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

3.2 編碼方式

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

3.3 算法描述

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

1) 初始化種群規模P、加速因子、權重因子、最大迭代次數等參數，產生初始粒子X和速度V。

2) 計算目標函數值，產生第1代粒子的均方殘差值。

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

4) 迭代尋優：先要對每一代粒子都計算1次自適應的權值，更新粒子的速度和位置，對粒子進行交叉和變異的操作，然后計算目標函數值，更新個體最優和群體最優。

5) 當前迭代次數到達初始設定的最大迭代次數時，算法結束。

4 實驗及結果分析

4.1 實驗數據

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

4.2 實驗分析

雙向聚類算法實驗使用Matlab對數據進行分析和處理，采取Max-Min方法對數據進行歸一化處理，如式(6)所示。其中：x是樣本數據中的原始值；X是標準化后的值。

(6)

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

分別用粒子群算法、遺傳算法和本文中提出的GP-Cluster算法對上述2個數據集進行測試。測試結果見表1～2和圖1～4。

表1 急性白血病數據集實驗結果比較

表2 乳腺癌基因表達數據實驗結果比較

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

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

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

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

本文采用均方殘差值、雙聚類規模、基因數與條件數的比值、對原基因矩陣的覆蓋率和算法運行時間這5個指標來評價聚類結果質量。其中：均方殘差值為10次實驗得到的所有均方殘差值的平均值，越小越好；規模就是算法產生的基因聚類矩陣的大小，其值越大越好；行列比即基因聚類矩陣中基因數與條件數的比值，在均方殘差值相同的情況下，這個值越小越好。

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

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

雖然結合了遺傳算法的混合粒子群優化算法找到的雙聚類質量更佳，但是從算法運行所花費的時間上看，GP-Cluster算法消耗的時間明顯增加。

5 結束語

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

[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].微型機與應用,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] 周康渠，趙慧真． 混合離散粒子群算法在混流裝配線生產調度中的應用[J]． 重慶理工大學學報(自然科學)，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] 劉敏,李智彪.基于粒子群優化脈沖耦合神經網絡的紅外圖像分割[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] 孫延維,彭智明,李健波.基于粒子群優化與模糊聚類的社區發現算法[J].重慶郵電大學學報(自然科學版),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] 周文剛,趙宇．具有完全學習策略的量子行為粒子群癌癥基因聚類算法[J].北京郵電大學學報,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] 梁軍.粒子群算法在最優化問題中的研究[D].南寧：廣西師范大學，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]林秀芳，陳淑梅，陳金蘭．運用遺傳算法的磁流變阻尼器減震的模糊控制[J] ． 重慶理工大學學報(自然科學)，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].重慶工商大學學報(自然科學版),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]劉偉，周育人.一種改進慣性權重的PSO 算法[J].計算機工程與應用,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-調和均值的混沌粒子群聚類算法[J].計算機工程與應用,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.

(責任編輯 楊黎麗)

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 基金項目：重慶市應用開發計劃項目(CSTC2013yykf A40002).

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

李梁，陳佳瑜.基于粒子群算法的基因表達譜聚類分析方法[J].重慶理工大學學報(自然科學)，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