雙聚類(lèi)的研究與進(jìn)展

近年來(lái)隨著基因芯片和DNA微陣列等高通量檢測(cè)技術(shù)的發(fā)展，產(chǎn)生了眾多的基因表達(dá)數(shù)據(jù)。對(duì)這些數(shù)據(jù)進(jìn)行有效的分析已經(jīng)成為后基因組時(shí)代的研究重點(diǎn)。一般的聚類(lèi)是根據(jù)數(shù)據(jù)的全部屬性將數(shù)據(jù)聚類(lèi)，這種聚類(lèi)方式稱(chēng)為傳統(tǒng)聚類(lèi)。傳統(tǒng)聚類(lèi)只能尋找全局信息，無(wú)法找到局部信息，而大量的生物學(xué)信息就隱藏在這些局部信息中。為了更好地在數(shù)據(jù)矩陣中搜索局部信息，人們提出雙聚類(lèi)概念，目前這種聚類(lèi)方法得到了越來(lái)越廣泛的應(yīng)用。

本文對(duì)雙聚類(lèi)提出以來(lái)的研究成果進(jìn)行綜述。從基本思想、性能和雙聚類(lèi)結(jié)果評(píng)價(jià)等角度總結(jié)重要的雙聚類(lèi)算法類(lèi)型。

1 雙聚類(lèi)概念

自從基因芯片技術(shù)產(chǎn)生以來(lái)，大量的生物數(shù)據(jù)需要分析，這些數(shù)據(jù)大多規(guī)格化后以矩陣形式表示和存儲(chǔ)?；蛐酒瑪?shù)據(jù)中隱藏了大量有用的局部模式，為尋找這些信息，CHENG and CHURCH于2000年提出了雙聚類(lèi)(bicluster)概念[1]，并給出了雙聚類(lèi)的定義：

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

雙聚類(lèi)的目的就是在基因表達(dá)數(shù)據(jù)矩陣中尋找滿(mǎn)足條件的子矩陣，使得子矩陣中基因集在對(duì)應(yīng)的條件集上表達(dá)波動(dòng)一致，反之亦然。不同的雙聚類(lèi)算法采用不同的方式度量結(jié)果質(zhì)量，所能找到的雙聚類(lèi)類(lèi)型是有很大差別的。目前較廣泛的模型有四種：矩陣等值模型、矩陣加法模型、矩陣乘法模型和信息共演變模型。圖1顯示了這幾種模型。

2 雙聚類(lèi)算法分類(lèi)

2.1 基于傳統(tǒng)聚類(lèi)的雙聚類(lèi)

這是一類(lèi)最基本的雙聚類(lèi)方法，以傳統(tǒng)聚類(lèi)為雙聚類(lèi)的基礎(chǔ)，基本思想是通過(guò)傳統(tǒng)聚類(lèi)分別對(duì)矩陣的行和列進(jìn)行聚類(lèi)，然后合并聚類(lèi)結(jié)果。具有代表性的是GETZ G等人[2]提出的耦合雙向聚類(lèi)(Coupled two-way clustering)算法。算法開(kāi)始于初始矩陣，創(chuàng)建兩個(gè)集合，一個(gè)只包含所有行，另一個(gè)只包含所有列。對(duì)這兩個(gè)集合分別運(yùn)用分層聚類(lèi)，以產(chǎn)生穩(wěn)定的行和列的聚類(lèi)，迭代上述聚類(lèi)過(guò)程來(lái)尋找符合條件的穩(wěn)定子集，將每次產(chǎn)生的穩(wěn)定基因子集和條件子集分別加在各自的集合中，如此直到?jīng)]有新的穩(wěn)定的雙聚類(lèi)出現(xiàn)?；趥鹘y(tǒng)聚類(lèi)的算法還有很多，如QU[3]等人采用模糊c均值來(lái)尋找相似子矩陣模型，通過(guò)分別對(duì)行和列應(yīng)用傳統(tǒng)聚類(lèi)得到中間結(jié)果，然后合并這些中間結(jié)果得到最終雙聚類(lèi)。這類(lèi)算法實(shí)現(xiàn)上較為容易，可以根據(jù)不同的需求選擇不同的傳統(tǒng)聚類(lèi)算法，算法更加靈活。但這類(lèi)算法無(wú)法完全脫離聚類(lèi)的全局性，不能很好地尋找局部模式。為克服基于傳統(tǒng)聚類(lèi)算法的缺陷，應(yīng)該盡量避免傳統(tǒng)聚類(lèi)的全局聚類(lèi)的思想。如BHATTA A等[4]提出的BCCA算法就很好地避免了全局聚類(lèi)，算法基于傳統(tǒng)聚類(lèi)的一種距離度量方式，即pearson相關(guān)系數(shù)，通過(guò)計(jì)算刪除一些使person相關(guān)系數(shù)明顯增加的行列，從而得到雙聚類(lèi)。但BCCA算法不能尋找波動(dòng)一致而pearson距離較遠(yuǎn)的雙聚類(lèi)。

2.2 貪心迭代搜索

為擺脫傳統(tǒng)聚類(lèi)的局限性和更好地提高效率，很多算法采用了貪心迭代搜索方法尋找雙聚類(lèi)。CHENG and CHURCH首次使用這種方法尋找雙聚類(lèi)，提出了著名的CC（CHENG and CHURCH）算法[1]。CC算法通過(guò)逐步刪除可以使子矩陣的平均平方殘基降低的行和列，得到一個(gè)最初的雙聚類(lèi)，然后逐步添加不會(huì)使子矩陣平均平方殘基增加的行和列，得到一個(gè)較滿(mǎn)意的雙聚類(lèi)。為找到更多雙聚類(lèi)，算法使用隨機(jī)數(shù)覆蓋已經(jīng)找到的雙聚類(lèi)，再進(jìn)行刪除和添加過(guò)程從而得到指定個(gè)數(shù)的雙聚類(lèi)結(jié)果。算法能夠較快地得到用戶(hù)指定數(shù)目的雙聚類(lèi)，但缺陷很明顯，隨機(jī)數(shù)替換會(huì)改變?cè)紨?shù)據(jù)，造成結(jié)果的不精確，也無(wú)法找到重疊的雙聚類(lèi)，而且容易陷入局部最優(yōu)。YANG[5]等人對(duì)CC算法進(jìn)行了改進(jìn)，提出了FLOC算法。該算法首先生成一定數(shù)量的種子，然后通過(guò)計(jì)算添加或刪除某一行或列，每一步盡量使得雙聚類(lèi)的中間結(jié)果增益改變最大。FLOC算法雖然可以找到可重疊的雙聚類(lèi)，但雙聚類(lèi)結(jié)果的好壞與運(yùn)行時(shí)間都很大程度地依賴(lài)于初始聚類(lèi)，而這些初始聚類(lèi)往往都是隨機(jī)產(chǎn)生的。雙聚類(lèi)的貪心策略效率較高，但聚類(lèi)結(jié)果容易陷入局部最優(yōu)。為克服貪心策略陷入局部最優(yōu)的缺陷，一些算法首先采用貪心策略尋找雙聚類(lèi)，然后對(duì)找到的雙聚類(lèi)再應(yīng)用智能優(yōu)化算法以得到較理想的結(jié)果。如STEFAN等人[6]對(duì)CC算法進(jìn)行了改進(jìn)，即在添加刪除過(guò)程中好的行列有較大保留概率，反之較小，迭代得到的結(jié)果作為種子，應(yīng)用進(jìn)化算法優(yōu)化產(chǎn)生較理想的雙聚類(lèi)。

2.3 雙聚類(lèi)窮舉策略

嚴(yán)格地說(shuō),采用窮舉方式尋找雙聚類(lèi)是不現(xiàn)實(shí)的。原數(shù)據(jù)矩陣的子矩陣數(shù)量通常都異常龐大，所以采用窮舉策略尋找雙聚類(lèi)算法，多數(shù)為窮舉小的子矩陣然后合并這些子矩陣的過(guò)程。WANG[7]等人提出的δ-Pcluster算法先找到所有基因?qū)蜅l件對(duì)中滿(mǎn)足一定條件的雙聚類(lèi)，然后根據(jù)條件對(duì)的聚類(lèi)結(jié)果對(duì)基因?qū)Φ木垲?lèi)結(jié)果進(jìn)行剪枝，以基因?qū)l件上的聚類(lèi)結(jié)果剪枝，得到較少的小雙聚類(lèi)構(gòu)建前綴樹(shù)，通過(guò)后序遍歷尋找雙聚類(lèi)。δ-Pcluster算法只為加法模型定義了收斂函數(shù)，所以只能限制在加法模型的雙聚類(lèi)上。LIU[8]等人改進(jìn)了δ-Pcluster算法，采用多個(gè)閾值對(duì)應(yīng)多種雙聚類(lèi)模式，可以通過(guò)定義多種分組函數(shù)，構(gòu)建了一個(gè)OPC樹(shù)將雙聚類(lèi)的子結(jié)果添加入OPC樹(shù)，通過(guò)一次深度優(yōu)先遍歷即可尋找到不同雙聚類(lèi)模式。SAMBA算法[9]是另一個(gè)比較重要的基于窮舉的雙聚類(lèi)算法，該算法使用統(tǒng)計(jì)模型將雙聚類(lèi)問(wèn)題轉(zhuǎn)化為一個(gè)完全平衡二分圖搜索問(wèn)題，再尋找基因表達(dá)譜模式，即尋找具有波動(dòng)一致性的子矩陣問(wèn)題轉(zhuǎn)化為在二分圖中找稠密子圖問(wèn)題。然而，這一算法的重要意義在于：對(duì)于基因表達(dá)譜進(jìn)行雙聚類(lèi)分析，實(shí)質(zhì)上是一個(gè)NP-hard問(wèn)題。所以，使用窮舉策略的雙聚類(lèi)算法雖然能夠找到較優(yōu)的雙聚類(lèi)，但算法的時(shí)間復(fù)雜度會(huì)隨矩陣規(guī)模的增大而呈指數(shù)增長(zhǎng)。因此必須限制雙聚類(lèi)矩陣的大小，同時(shí)利用算法技巧優(yōu)化窮舉過(guò)程，才能保證算法的效率。

2.4 數(shù)學(xué)模型方法

利用數(shù)學(xué)中較成熟的理論或通過(guò)建立模型尋找雙聚類(lèi)，一直是研究的熱點(diǎn)，也是近年來(lái)雙聚類(lèi)發(fā)展中的一個(gè)趨勢(shì)。由于雙聚類(lèi)問(wèn)題的特殊性，即在矩陣中尋找有規(guī)律的子矩陣，所以可以較容易地轉(zhuǎn)換成數(shù)學(xué)模型問(wèn)題。這類(lèi)算法中較重要的有LAURA[10]提出的格子模型（Gibbs sampling），它將整個(gè)數(shù)據(jù)集建模為基于聚類(lèi)表達(dá)模式的疊加。也就是說(shuō)，假如一個(gè)突出值屬于多個(gè)簇，則它等價(jià)于這些簇的所有背景值、行影響、列影響的疊加。格子模型更適合確定那些重疊簇，但是這個(gè)模型所使用的貪心算法的固有性質(zhì)卻阻礙了這一目標(biāo)的實(shí)現(xiàn)。假設(shè)某一值是由多個(gè)簇疊加產(chǎn)生的，當(dāng)確定第一個(gè)簇時(shí)，實(shí)際上這個(gè)值受到了所有疊加簇的影響，這意味著這個(gè)值將極大地偏離第一個(gè)簇的模型。這將導(dǎo)致它被排除到簇外，而實(shí)際上它本來(lái)是應(yīng)該在這個(gè)簇內(nèi)的。GU等[11]在Gibbs sampling的基礎(chǔ)上提出了貝葉斯雙聚類(lèi)模型(BBC)，這種是完全基于模型的一種方法，所以不需要任何閾值參數(shù)就能尋找到重疊的雙聚類(lèi)。Kluger[12]等提出的Spectral Biclustering應(yīng)用線(xiàn)性代數(shù)技術(shù)尋找數(shù)據(jù)中的雙聚類(lèi)結(jié)構(gòu)，將在一個(gè)條件集上波動(dòng)一致的基因集看做一種隱藏的棋盤(pán)模式，使用特征向量計(jì)算尋找這種模式。這類(lèi)算法的共同之處在于將雙聚類(lèi)問(wèn)題轉(zhuǎn)化成數(shù)學(xué)或其他模型，應(yīng)用各種方法尋找這些模型。數(shù)學(xué)模型方法尋找雙聚類(lèi)的缺陷也很明顯，就是一種數(shù)學(xué)模型只對(duì)應(yīng)一種或少數(shù)的雙聚類(lèi)類(lèi)型。表1是對(duì)以上四種類(lèi)型優(yōu)缺點(diǎn)的總結(jié)。

2.5 其他雙聚類(lèi)方法

另外的一些較重要方法還有采用分治策略尋找雙聚類(lèi)。其思想是，先將矩陣劃分成若干子矩陣，然后對(duì)子矩陣進(jìn)行雙聚類(lèi)，最后合并小的聚類(lèi)而得到最終結(jié)果。這類(lèi)算法的優(yōu)點(diǎn)是執(zhí)行速度較快，但是缺點(diǎn)是算法可能錯(cuò)過(guò)一些好的雙聚類(lèi)，因?yàn)樵诎l(fā)現(xiàn)它們之前，這些雙聚類(lèi)可能己經(jīng)被分割。模仿生物現(xiàn)象或自然的進(jìn)化算法越來(lái)越普遍，這些方法在數(shù)據(jù)挖掘和雙聚類(lèi)中有著廣泛的應(yīng)用。如DIVINA等[13]將多目標(biāo)進(jìn)化算法應(yīng)用于雙聚類(lèi)，同時(shí)優(yōu)化多個(gè)目標(biāo)，來(lái)發(fā)現(xiàn)全局最優(yōu)解。BRYAN等[14]應(yīng)用模擬退火模型尋找雙聚類(lèi)，都得到了較好的效果。

3 雙聚類(lèi)結(jié)果度量

目前雙聚類(lèi)實(shí)驗(yàn)公認(rèn)的兩個(gè)數(shù)據(jù)集分別是：啤酒酵母細(xì)胞周期表達(dá)值[15]和人類(lèi)B細(xì)胞表達(dá)值[16]。雙聚類(lèi)結(jié)果質(zhì)量評(píng)價(jià)標(biāo)準(zhǔn)有可視化和非可視化標(biāo)準(zhǔn)。雙聚類(lèi)的可視化主要有通過(guò)明暗度觀察矩陣結(jié)構(gòu)的熱圖、通過(guò)點(diǎn)線(xiàn)連接觀察波動(dòng)性的坐標(biāo)圖、通過(guò)基因節(jié)點(diǎn)的帶有方向性的連接的表達(dá)譜圖。BARKOW等人[17]開(kāi)發(fā)了一個(gè)著名的雙聚類(lèi)算法平臺(tái)，使用其中的熱度圖可以較直觀地看到數(shù)據(jù)矩陣的規(guī)模，通過(guò)明暗度大致了解基因表達(dá)的強(qiáng)度。其中也實(shí)現(xiàn)了坐標(biāo)圖，這是目前廣泛使用的雙聚類(lèi)可視化方式，可直觀地看到基因曲線(xiàn)波動(dòng)的一致性。

非可視化標(biāo)準(zhǔn)往往結(jié)合可視化共同度量雙聚類(lèi)算法或雙聚類(lèi)結(jié)果的好壞。不同的雙聚類(lèi)策略在時(shí)間花費(fèi)上相差很大，又由于雙聚類(lèi)是NP-hard問(wèn)題，所以運(yùn)行時(shí)間是度量雙聚類(lèi)算法好壞的一個(gè)重要因素。至于雙聚類(lèi)個(gè)體的質(zhì)量，往往會(huì)看它是否接近四種基本模型。平均平方殘基H是度量結(jié)果是否接近模型的較好方式，也是現(xiàn)階段通常采用的度量手段。雙聚類(lèi)的大小S即包含元素個(gè)數(shù)也是判斷雙聚類(lèi)質(zhì)量的標(biāo)準(zhǔn)，所以有了許多H的演變形式，例如H/S的形式可有效度量結(jié)果，其值越小聚類(lèi)結(jié)果越好。在整個(gè)矩陣上找到多個(gè)雙聚類(lèi)，所以覆蓋矩陣元素的全面性和雙聚類(lèi)結(jié)果的重疊性也是重要的質(zhì)量評(píng)價(jià)標(biāo)準(zhǔn)。能否找到可重疊的雙聚類(lèi)是設(shè)計(jì)雙聚類(lèi)算法要考慮的，而結(jié)果是否能有效地覆蓋矩陣中所有元素也是重要的。另外還有其他的雙聚類(lèi)度量方式，例如在同一雙聚類(lèi)結(jié)果上發(fā)現(xiàn)了更多屬于這個(gè)雙聚類(lèi)的基因，而這些基因沒(méi)有被其他方法發(fā)現(xiàn)。

雙聚類(lèi)是個(gè)較為年輕的研究領(lǐng)域，近十幾年的研究提出了很多有效算法，應(yīng)用這些算法分析生物芯片數(shù)據(jù)的過(guò)程中也發(fā)現(xiàn)了許多有意義的生物學(xué)結(jié)果。如今雙聚類(lèi)領(lǐng)域雖然主要應(yīng)用于基因表達(dá)數(shù)據(jù)，但隨著研究的發(fā)展也將會(huì)應(yīng)用于電子商務(wù)等多種領(lǐng)域。由于雙聚類(lèi)問(wèn)題本身的復(fù)雜性，今后依然是個(gè)有挑戰(zhàn)性的研究課題。

參考文獻(xiàn)

[1] CHENG Y, CHURCH G M. Biclustering of expression data[C]. Proc. Eighth Int’l Conf. Intelligent Systems for Molecular Biology (ISMB’00), 2000:93-103.

[2] GETZ G, LEVINE E, DOMANY E. Coupled two-way clustering analysis of gene microarray data[C]. In Proceed ings of the Natural Academy of Sciences USA, 2000:12079-12084.

[3] Qu Jinbin, MICHAEL N, Chen Luonan. Constrained subspace clustering for time series gene expression data[C]. In 4th International Conference on Computational Systems Biology, 2010:9-11.

[4] BHATTACHARYA A, DE R K. Bi-correlation clustering algorithm for determining a set of co-regulated genes[J]. Bioinformatics, 2009, 25(21): 2795-2801.

[5] Yang Jiong, Wang Wei. Enhanced biclustering on gene expression data[C]. In Proceedings of the 3rd IEEE Conference on Bioinformatics and Bioengineering, 2003:321-327.

[6] BLEULER S, PRELIC A, ZITZLER E. An EA framwork for biclustering of gene expression data[C]. Evolutionary Computation, 2004:166-173.

[7] Wang Haixun, Wang Wei, Yang Jiong, et al. Clustering by pattern similarity in large data sets[C]. Proc. The ACM SIGMOD International Conference on Management of Data, 2002:394-405.

[8] Liu Jinze, Wang Wei. Op-cluster: clustering by tendency in high dimensional space[C]. In Proceedings of the 3rd IEEE International Conference on Data Mining, 2003:19-22.

[9] TANAY A, SHARAN R, et al. Revealing modularity and organization in the yeast molecular network by integrated analysis of highly heterogeneous genomewide data[C]. ProcNatl Acad Sic U S A.,2004: 2981-6.

[10] LAZZERONI L, QWEN A. Plaid models for gene expression data[J]. Statistica Sinica, 2002 (12):61-86.

[11] Gu Jiajun, LEE J S. Bayesian biclustering of gene expression data[C]. International Conference on Bioinformatics and Computational Biology, 2007: 25-28.

[12] KLUGER Y, BASRI R, ChANG J T, et al. Spectral biclustering of microarray data：coclustering genes and conditions[J]. Genome Res, 2003,13(4):703-16.

[13] DIVINA F, AGUILAR,RUIZ J S. A multi-objective approach to discover biclusters in microarray data[C]. Proceedings of the 9th annual conference on Genetic and evolutionary computation, 2007: 385-392.

[14] BRYAN K, CUNNINGHAM P, BOLSHAKOVA N. Biclustering of Expression Data Using Simulated Annealing[C].18th IEEE Symposium, 2005: 383-388.

[15] CHO R J, CAMPBELL M J, WINZELER E A, et al. A genome-wide transcriptional analysis of the mitotic cell cycle[J]. Molecular Cell, 1998, 2(1): 65-73.

[16] ALIZADEH A A, Eisen M B, Davis R E, et al. Distinct types of diffuse large B-cell lymphoma identified by gene expression profiling[J]. Nature, 2000(403):503-511.

[17] BARKOW S, BLEULER S, PRELIC A, et al. BicAT:biclustering analysis toolbox[J]. Bioinformatics, 2006,22(10):1282-1283.

更多醫(yī)療電子信息請(qǐng)關(guān)注：21ic醫(yī)療電子頻道