基于邏輯運(yùn)算的離散人工蜂群優(yōu)化雙聚類算法?

馬 衛(wèi) 朱 嫻

（1.南京旅游職業(yè)學(xué)院酒店管理學(xué)院 南京 211100）

（2.南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系計(jì)算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室 南京 210093）

（3.南京理工大學(xué)紫金學(xué)院計(jì)算機(jī)學(xué)院 南京 210046）

1 引言

DNA微陣列技術(shù)可以同時(shí)測量成千上萬個(gè)基因的表達(dá)水平，通過不同實(shí)驗(yàn)條件下的重復(fù)實(shí)驗(yàn)產(chǎn)生數(shù)百個(gè)實(shí)驗(yàn)資料。這種技術(shù)通常會(huì)產(chǎn)生大量的原始數(shù)據(jù)，通過分析提取有用的信息，對(duì)醫(yī)學(xué)臨床診斷、揭示疾病發(fā)生機(jī)制等方面起著重要作用。

為了挖掘基因表達(dá)數(shù)據(jù)中基因和實(shí)驗(yàn)條件相互表達(dá)的局部信息，Cheng和Church［1］提出了雙聚類CC算法，運(yùn)用貪心策略同時(shí)在基因和實(shí)驗(yàn)條件兩個(gè)維度上搜索雙聚類。隨后，可重疊、隨機(jī)搜索和多目標(biāo)進(jìn)化等雙聚類算法不斷提出。

Yang等［2］提出了概率算法（FLOC），在CC算法的基礎(chǔ)上進(jìn)行了改進(jìn)，解決了每次迭代只能發(fā)現(xiàn)單個(gè)雙聚類的問題，能夠發(fā)現(xiàn)可重疊的雙聚類。群體智能算法是近三十年非常普遍的數(shù)據(jù)挖掘方法，模擬退火算法、遺傳算法、粒子群算法、蟻群算法等均被應(yīng)用于雙聚類。Chakraborty［3］初始化雙聚類種子采用模擬退火法隨機(jī)搜索雙聚類，使得產(chǎn)生雙聚類結(jié)果達(dá)到全局最優(yōu)。Wolf等［4］采用模擬退火法在全局搜索的基礎(chǔ)上進(jìn)行了改進(jìn)。多目標(biāo)進(jìn)化雙聚類算法是目前雙聚類優(yōu)化采用最多的算法。Mitra等［5］采用經(jīng)典非支配排序遺傳算法優(yōu)化雙聚類，提出了具有多目標(biāo)進(jìn)化雙聚類框架。劉萬軍［6］提出了微陣列多目標(biāo)優(yōu)化雙聚類，分別用多目標(biāo)粒子群、多目標(biāo)蟻群、多目標(biāo)人工免疫等多目標(biāo)群體算法優(yōu)化雙聚類。Carlos等［7］采用基因和實(shí)驗(yàn)條件組表示雙聚類編碼，提出了一種改進(jìn)的多目標(biāo)遺傳雙聚類算法。

近年，Karaboga［8］提出了人工蜂群算法，該算法模擬蜜蜂采蜜行為隨機(jī)搜索優(yōu)化，具有尋優(yōu)精度高、全局搜索能力強(qiáng)等特點(diǎn)，被廣泛應(yīng)用于求解組合優(yōu)化以及各類工程問題的優(yōu)化。離散人工蜂群算法被提出應(yīng)用于離散優(yōu)化工程問題，比較常用的離散方法有SF（Sigmoid Function）方法［9］，二進(jìn)制粒子群算法［10］、離散人工蜂群算法［11］均采用SF方法。朱冰蓮等［12］提出了一種基于邏輯運(yùn)算的人工蜂群算法，解決了離散人工蜂群算法策略更新問題，有效提高了離散優(yōu)化的性能，加快了算法的收斂速度。

本文在離散人工蜂群算法的框架下，提出了基于邏輯運(yùn)算的離散人工蜂群優(yōu)化雙聚類算法（LOABCB算法）。該算法提高了雙聚類的全局尋優(yōu)能力，能發(fā)現(xiàn)基因表達(dá)數(shù)據(jù)中一個(gè)或多個(gè)具有生物意義的全局最優(yōu)雙聚類。

2 雙聚類

2.1 雙聚類模型

令基因表達(dá)數(shù)據(jù)矩陣為Am×n，其中矩陣A中的行集合為基因集合G={g1,g2,…,gm}，列集合為實(shí)驗(yàn)條件集合C={c1,c2,…,cn}，aij為表達(dá)矩陣Am×n的元素值，代表在第j列實(shí)驗(yàn)條件下第i行基因的表達(dá)值。

AI×J為雙聚類，其中I為基因集合的子集I?G，J為實(shí)驗(yàn)條件集合的子集J?C，在理想狀態(tài)下，雙聚類的元素值aij可以定義為行均值加上列均值減去矩陣均值（1）。然而，基因數(shù)據(jù)中存在噪聲，雙聚類并不一定是理想的，因此定義殘差值表達(dá)元素與雙聚類其他元素表達(dá)的標(biāo)準(zhǔn)。元素值aij的殘差值定義為式（2）。

元素值aij的殘差值越小，表示aij與雙聚類其他元素的相互表達(dá)一致性越大。因此，均方殘值是衡量雙聚類基因和實(shí)驗(yàn)條件相關(guān)性的重要指標(biāo)。均方殘值的表示為H(I,J)，定義為式（3）。

如果滿足H(I,J)≤δ，且δ≥0，則子矩陣AIJ叫做δ-雙聚類。

2.2 雙聚類基因差異表達(dá)

優(yōu)化具有生物意義的雙聚類是選擇相互表達(dá)的相似基因，如圖1所示，gt為初始基因，g1～g4為優(yōu)化產(chǎn)生的基因，其中，基因g1～g3表達(dá)模式與初始基因gt表達(dá)模式較一致，基因g4的表達(dá)模式有較高的差異度。

圖1 基因表達(dá)圖譜

對(duì)雙聚類矩陣Am×n進(jìn)行基因表達(dá)模式轉(zhuǎn)換，保持行基因m不變，列為實(shí)驗(yàn)條件集合兩兩組合n(n-1)/2，產(chǎn)生變換矩陣Bm×n(n-1)/2，矩陣B變換規(guī)則如式（4）。

其中，i∈[1…m]，j∈[1…n(n-1)/2]，p＜q。

表達(dá)差異度的確定公式如式（5）：

式中，Bt為目標(biāo)向量，Bi(t≠i) 為比較向量，COMPARE是Bt和Bi的比較操作符，di記錄比較操作在某一列的返回值，相同返回0不同則返回1。表達(dá)差異比率計(jì)算公式如式（6）：

式中，ε為表達(dá)差異比率，表示di中1的比率，其中，D=n(n-1)/2。

3 人工蜂群算法

人工蜂群算法（Artificial Bee Colony，ABC）是建立在群體性智能和蜂群高度社會(huì)化的一種隨機(jī)搜索優(yōu)化算法。人工蜂群算法分為三類群體，根據(jù)蜜蜂的分工協(xié)作分成雇傭蜂、跟隨蜂和偵察蜂。雇傭蜂負(fù)責(zé)搜索蜜源記錄相關(guān)信息，按照一定的概率分享將蜜源信息傳遞給跟隨蜂。跟隨蜂主要任務(wù)為開采蜜源，挑選高質(zhì)量蜜源進(jìn)一步進(jìn)行領(lǐng)域搜索。偵察蜂是一只虛擬蜂，具有全局隨機(jī)搜索引導(dǎo)作用。當(dāng)雇傭蜂和跟隨蜂多次搜索仍未獲得較高質(zhì)量的蜜源時(shí)，雇傭蜂轉(zhuǎn)變?yōu)閭刹旆渲匦码S機(jī)尋找新的蜜源。

假定蜜蜂種群的規(guī)模為N，蜜源、雇傭蜂、跟隨蜂的數(shù)量均為N。在一個(gè)D維空間里，Xi表示第i個(gè)食物的當(dāng)前位置，如式（7）所示。

雇傭蜂的初始位置從D維參數(shù)中隨機(jī)產(chǎn)生，由式（8）產(chǎn)生：

其中，i∈{1,2,...,N},j∈{1,2,...,D}，ub和lb分別表示搜索空間的上限與下限的范圍值。

ABC算法中，雇傭蜂根據(jù)式（9）從D維空間中隨機(jī)抽取一個(gè)維度進(jìn)行更新。

其中，k∈{1,2,...,N}-{i}，φi,j=rand[-1,1]為[-1,1]上的隨機(jī)數(shù)。xk,j表示第k只雇傭蜂第j維上的分量。

雇傭蜂進(jìn)行鄰域搜索、適應(yīng)度評(píng)價(jià)、蜜源位置更新后，產(chǎn)生較優(yōu)蜜源并傳遞給跟隨蜂。跟隨蜂按照一定的概率式（10）選擇蜜源，然后根據(jù)雇傭蜂鄰域搜索式（9）進(jìn)行位置更新。

其中，me為雇傭蜂的數(shù)量，fiti表示第i個(gè)蜜源的適用度，pi表示第i個(gè)蜜源被選中的概率。

當(dāng)雇傭蜂和跟隨蜂的搜索達(dá)到最大限制次數(shù)limit，表示當(dāng)前蜜源質(zhì)量未得到提升，則雇傭蜂轉(zhuǎn)為偵察蜂，根據(jù)式（8）進(jìn)行重新搜索，最后獲得全局最優(yōu)解。

4 基于邏輯運(yùn)算的離散人工蜂群雙聚類算法

4.1 編碼方式

將離散人工蜂群算法應(yīng)用到雙聚類搜索中，首先對(duì)雙聚類進(jìn)行編碼。雙聚類為一個(gè)長度為1*(m+n) 固定數(shù)組，解的形式為Xi={xi1,xi2,…,xi,m+n}，其中m和n分別表示基因表達(dá)數(shù)據(jù)矩陣的基因數(shù)和實(shí)驗(yàn)條件數(shù)。Xi∈{0,1}即解X的值非0即1，當(dāng)解xij=1，j∈{1,2,…,m+n}，表示對(duì)應(yīng)j位可選，對(duì)應(yīng)的基因或?qū)嶒?yàn)條件屬于該雙聚類；當(dāng)解xij=0則表示第j位不可選，不包括在雙聚類中。

4.2 鄰域搜索策略

人工蜂群算法鄰域搜索過程主要集中在偵察蜂和跟隨蜂兩個(gè)階段，即偵察蜂和跟隨蜂在D維空間中進(jìn)行單維度更新，離散人工蜂群算法解Xi在D維空間的值非0即1，由于新解的產(chǎn)生僅僅為簡單的取反運(yùn)算，這種隨機(jī)性操作導(dǎo)致大量劣質(zhì)雙聚類出現(xiàn)。

針對(duì)離散二進(jìn)制優(yōu)化問題，既要保證新解與原解的差異，又要考慮雙聚類的優(yōu)化程度。采用海明距離表示各個(gè)解向量之間的差異度［13］建立群體間的學(xué)習(xí)模型，通過表達(dá)差異比率平衡更新策略，加快優(yōu)質(zhì)雙聚類產(chǎn)生，策略如下：

設(shè)置交叉比率R，按照比率隨機(jī)抽取D維空間維度值更新，更新公式如式（11）：

式中，i≠k，“⊕”表示解向量在D維空間對(duì)應(yīng)維間的異或操作。

設(shè)置表達(dá)差異比率閾值th，當(dāng)xij=1且εij≥th，進(jìn)行解的變異更新如式（12）；否則保持原解不變。

在鄰域搜索過程中，Xi為當(dāng)前解，表示為Xi={xi1,xi2,…,xiD}，Xk為種群中隨機(jī)挑選出的鄰域解，表示為Xk={xk1,xk2,…,xkD}。式（11）通過當(dāng)前解和鄰域異或操作更新單個(gè)維度上的值產(chǎn)生新解，式（12）根據(jù)表達(dá)差異比率對(duì)當(dāng)前解進(jìn)行取反操作，產(chǎn)生新解。

4.3 算法步驟

LOABCB算法步驟：

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

基于邏輯運(yùn)算的離散人工蜂群優(yōu)化雙聚類算法實(shí)現(xiàn)環(huán)境為Windows 8.1，PC機(jī)為2.5GHz CPU Intel Core（TM）i7-4710MQ 12GB內(nèi)存，采用Matlab 2012b編程。實(shí)驗(yàn)數(shù)據(jù)采用酵母細(xì)胞基因表達(dá)數(shù)據(jù)集，該數(shù)據(jù)集為CC算法使用的基因表達(dá)數(shù)據(jù)集?；虮磉_(dá)數(shù)據(jù)集經(jīng)過處理后可以減少噪聲的影響，提高雙聚類的生成質(zhì)量，數(shù)據(jù)網(wǎng)址為http：//arep.med.harvard.edu/biclustering。

5.1 實(shí)驗(yàn)數(shù)據(jù)描述

酵母細(xì)胞基因表達(dá)數(shù)據(jù)集采用Tavazoie等［14］的生物實(shí)驗(yàn)，包含2884個(gè)基因17種實(shí)驗(yàn)條件下的表達(dá)數(shù)據(jù)。Cheng和Church［1］對(duì)原始酵母細(xì)胞基因表達(dá)數(shù)據(jù)集進(jìn)行預(yù)處理，缺失值用-1替換，其余值取對(duì)數(shù)后乘于100，使得表達(dá)數(shù)據(jù)的取值范圍在［0，600］。

5.2 性能分析

5.2.1 實(shí)驗(yàn)結(jié)果比較

為了驗(yàn)證LOABCB算法的有效性，本文選擇了近年來新提出的幾個(gè)優(yōu)化算法進(jìn)行比較，包括多目標(biāo)進(jìn)化算法以及在多目標(biāo)進(jìn)化算法基礎(chǔ)上進(jìn)行改進(jìn)的雙聚類算法SPEA2B［5］、eMOGB［7］，MOPSOB［6］，OMOACOB［6］，MOSFLB［16］，以及采用人工蜂群雙聚類的MOABCB［17］算法。

本文LOABCB算法參數(shù)設(shè)置與其他比較算法參數(shù)設(shè)置如表1所示，其余參數(shù)表達(dá)差異比率閾值th為0.3，最大迭代次數(shù)MCN為100，蜜源停留最大限制次數(shù)limit為10。

表1 酵母細(xì)胞基因表達(dá)數(shù)據(jù)集參數(shù)設(shè)置

從表2中可以看出，在酵母細(xì)胞基因表達(dá)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果中，本文算法獲得的雙聚類平均均方殘值優(yōu)于SPEA2B、eMOGB、MOABCB算法，但平均行數(shù)最低，主要原因是算法進(jìn)行了表達(dá)差異比率的雙聚類修正，降低了平均均方殘值和平均行數(shù)。對(duì)比于其它比較算法，LOABCB算法獲得的雙聚類平均列數(shù)高于其他比較算法，說明LOABCB算法具備最優(yōu)解優(yōu)化的性能。

表2 酵母細(xì)胞基因表達(dá)數(shù)據(jù)集結(jié)果比較

5.2.2 生物注釋富集比較

基因本體（Gene Ontology，GO）是目前應(yīng)用最廣泛的基因注釋體系之一，描述了基因產(chǎn)物相關(guān)的生物過程、細(xì)胞組成和分子功能。它是生物學(xué)中極為重要的方法和工具，基因表達(dá)數(shù)據(jù)雙聚類是挖掘具有某種生物學(xué)上意義的問題，為了驗(yàn)證本文算法獲得的雙聚類參與了生物過程，首先通過計(jì)算P-value評(píng)價(jià)雙聚類的統(tǒng)計(jì)相關(guān)性，然后用GO功能進(jìn)行評(píng)價(jià)衡量基因集合的富集程度。

實(shí)驗(yàn)采用在線工具FuncAssociate［18］（http：//llama.mshri.on.ca/funcassociate）計(jì)算P-value評(píng)價(jià)算法的統(tǒng)計(jì)相關(guān)性，當(dāng)P-value小于5%時(shí)說明基因在對(duì)應(yīng)GO上出現(xiàn)富集。如圖2所示，本文算法與CC［1］、ISA［19］、OPSM［20］、MBA［21］分別取P-value=5%、1%、0.5%、0.1%和0.001%進(jìn)行比較。本文算法獲得的雙聚類P-value為5%比例高于CC和ISA算法，低于OPSM和MBA算法。雙聚類P-value為0.001%比例高于CC、ISA、OPSM算法僅低于MBA算法。

圖2 雙聚類GO富集注釋比例

表3 雙聚類Bicluster10的GO富集注釋

實(shí)驗(yàn)采用FuncAssociate工具對(duì)每個(gè)雙聚類計(jì)算P-value，評(píng)價(jià)雙聚類中基因與對(duì)應(yīng)GO注釋富集的匹配程度。表3表示雙聚類Bicluster10中P-value小于5%時(shí)的GO注釋富集詳細(xì)情況，共富集了16個(gè)GO功能類別，其中最顯著富集注釋是P-value小于0.001的屬性“chromosome organization”，對(duì)應(yīng)的基因本體ID為GO：0051276。結(jié)果表明LOABCB算法所得結(jié)果具有富集注釋的多樣性，可以挖掘出具有顯著性富集注釋功能的生物信息。

綜上所述，本文提出的算法LOABCB發(fā)現(xiàn)的雙聚類具有較高的質(zhì)量，能夠在離散人工蜂群優(yōu)化的框架下維持最優(yōu)解的多樣性，同時(shí)具備生物學(xué)意義的雙聚類。

6 結(jié)語

本文在離散人工蜂群優(yōu)化算法基礎(chǔ)上提出了一種基于邏輯運(yùn)算的全局調(diào)控基因表達(dá)模式的雙聚類算法（LOABCB算法）。算法采用鄰域搜索策略不斷更新蜂群搜索位置，在優(yōu)化過程中采用均方殘值度量蜂群之間的優(yōu)劣，通過基因表達(dá)差異比率對(duì)雙聚類進(jìn)行修正。實(shí)驗(yàn)表明，LOABCB算法能夠在離散人工蜂群優(yōu)化的框架下通過鄰域搜索策略更新解，維持最優(yōu)解的多樣性產(chǎn)生具有高相關(guān)表達(dá)的雙聚類。此外，與其他算法相比，本文算法所得雙聚類具有高顯著的基因GO富集注釋，從而表明LOABCB算法的多樣性、有效性和生物意義。