李美航，黃英仁

（廣東省華南師范大學(xué)，廣東廣州510006）

雙聚類算法研究

李美航，黃英仁

（廣東省華南師范大學(xué)，廣東廣州510006）

雙聚類算法的出現(xiàn)促進(jìn)了生物基因分析領(lǐng)域的發(fā)展，簡單介紹雙聚類算法的起源、概念、目的及主要模型，對現(xiàn)有主要模型的優(yōu)勢與不足進(jìn)行分析，并對常用雙聚類算法的實(shí)驗(yàn)方法進(jìn)行概括。

雙聚類；基因表達(dá)數(shù)據(jù)；CC算法；OPSM

0　引言

基因芯片與DNA微陣列技術(shù)的發(fā)展給生物領(lǐng)域帶來了大量的基因表達(dá)數(shù)據(jù)，如何從這些數(shù)據(jù)中找出有用的信息成為眾多研究人員研究的熱點(diǎn)。這些數(shù)據(jù)通常都以矩陣的形式存儲(chǔ)，在基因表達(dá)數(shù)據(jù)矩陣中，行代表基因，列代表實(shí)驗(yàn)條件，每個(gè)元素代表某個(gè)基因在給定實(shí)驗(yàn)條件下的表達(dá)水平。

為了有效的分析這些數(shù)據(jù)，聚類分析最早被應(yīng)用于其中。但傳統(tǒng)聚類分析有一個(gè)明顯的缺陷，就是只能對一個(gè)維度上的數(shù)據(jù)進(jìn)行全局聚類。大量的生物實(shí)驗(yàn)已經(jīng)證明，參與細(xì)胞功能運(yùn)作的可能只是部分基因。不同于傳統(tǒng)聚類，雙聚類可以對數(shù)據(jù)矩陣的行和列同時(shí)聚類，它可以找到數(shù)據(jù)矩陣中的局部模式，這些局部模式可以很好的體現(xiàn)出部分基因在部分實(shí)驗(yàn)條件下的異同。

1　雙聚類模型

雖然傳統(tǒng)的聚類算法在分析基因表達(dá)數(shù)據(jù)時(shí)展現(xiàn)出一定的效果，但是面對加速膨脹的數(shù)據(jù)規(guī)模，其在解決高維度，高噪聲數(shù)據(jù)時(shí)暴露出的疲軟及不適合尋找矩陣中的局部模式缺陷，雙聚類算法慢慢得到青睞。在學(xué)術(shù)上，雙聚類算法主要分為四種模型：①常數(shù)型雙聚類；②行常量或列常量雙聚類；③數(shù)值一致表達(dá)型雙聚類；④一致演化型雙聚類。

1.1常數(shù)型雙聚類

Hartigan［1］為了找到常數(shù)型的雙聚類，采用了一種直接劃分的塊聚類方法。這種塊聚類算法把原始的數(shù)據(jù)分成一系列小矩陣，然后用方差評估每一個(gè)小矩陣。雖然Hartigan的目的是為了尋找常數(shù)型雙聚類，同時(shí)他也提出了尋找行常量和列常量雙聚類的可能性，他提到只要我們選擇合適的評價(jià)函數(shù)去評價(jià)分塊后的小矩陣，那么我們將有可能找到行列常量甚至數(shù)值一致表達(dá)型雙聚類。

1.2行常量或列常量雙聚類

在尋找行列常量雙聚類時(shí)，除了上述提到的選擇合適的評價(jià)函數(shù)的方法。另外一個(gè)簡單的思想是把矩陣中的數(shù)值依照行或列進(jìn)行數(shù)據(jù)的標(biāo)準(zhǔn)化處理，這樣便可以把尋找行列常量的雙聚類轉(zhuǎn)化為尋找常數(shù)型的雙聚類。Getz等［2］便是用這種思想提出了CTWC算法。

1.3數(shù)值一致表達(dá)型雙聚類

相對于以上簡單的常量型雙聚類，大多數(shù)算法對于更為復(fù)雜的數(shù)值一致表達(dá)型雙聚類稍顯無措。Cheng and Church［3］在CC算法中提出了雙聚類這個(gè)概念，創(chuàng)造性地用均方殘基去衡量子矩陣中表達(dá)水平的一致性，它可以有效的找出數(shù)值一致表達(dá)型雙聚類，并給出了相應(yīng)的函數(shù)。函數(shù)定義如下：

其中dij是當(dāng)前元素值，dij表示第i行的行均值，dij表示第j列的列均值，dIJ=表示該子矩陣的總均值。

1.4一致演化型雙聚類

隨著雙聚類算法研究的深入，越來越多算法聚焦于數(shù)據(jù)中的模式而非具體的數(shù)據(jù)元素值也就是一致演化型雙聚類，它實(shí)際上是對數(shù)值一致表達(dá)型雙聚類的一種放寬條件。最早由Bendor等［4］提出保序子矩陣模型（OPSM），它只關(guān)注元素值的相對大小而不理會(huì)實(shí)際值。OPSM雙聚類模型本質(zhì)上是一個(gè)基于模式的子矩陣，它的行在某種列置換情況下可以展示出嚴(yán)格的遞增模式。一旦找到這樣一種模式的雙聚類，在生物基因?qū)W上可能揭示出某些共調(diào)控的基因在某些實(shí)驗(yàn)條件下有升降一致的體現(xiàn)，這對于研究基因在功能上的表現(xiàn)有很大的幫助。Bendor等人證明了尋找OPSM是NP-hard問題，并提出了一種貪心啟發(fā)式算法用于挖掘具有統(tǒng)計(jì)學(xué)意義的OPSM。該算法從一些小的OPSMs出發(fā)，通過不斷迭代去擴(kuò)展這些OPSMs直到不能擴(kuò)展為止。該算法能挖掘具有較大支持度閾值的OPSMs，但是它不能保證找到所有的OPSMs，并且需要較多的計(jì)算資源。

2　實(shí)驗(yàn)分析方法

雙聚類算法已經(jīng)廣泛應(yīng)用于基因表達(dá)數(shù)據(jù)，但如何去評估這些算法的優(yōu)劣是一項(xiàng)具有挑戰(zhàn)性的任務(wù)。目前主要從三個(gè)方面對算法性能進(jìn)行綜合評估：①雙聚類結(jié)果的優(yōu)劣；②算法對噪聲數(shù)據(jù)的魯棒性以及能否找到重疊的雙聚類；③算法的可擴(kuò)展性。目前所用的實(shí)驗(yàn)數(shù)據(jù)集主要來源于兩方面，即真實(shí)數(shù)據(jù)集與人工合成數(shù)據(jù)集。

2.1真實(shí)數(shù)據(jù)集

在對雙聚類結(jié)果的優(yōu)劣進(jìn)行評估時(shí)，我們會(huì)使用真實(shí)的數(shù)據(jù)集，目前雙聚類實(shí)驗(yàn)中公認(rèn)的幾個(gè)真實(shí)數(shù)據(jù)集有：①酵母菌數(shù)據(jù)集［3］，包含2884個(gè)基因和17個(gè)條件；②人類B細(xì)胞表達(dá)數(shù)據(jù)［5］，包含4026個(gè)基因和96個(gè)條件；③乳腺腫瘤數(shù)據(jù)集［6］，包含3226個(gè)基因和22個(gè)實(shí)驗(yàn)條件。算法在這些基因數(shù)據(jù)集上找到雙聚類結(jié)果后，將對結(jié)果進(jìn)行g(shù)ene ontology(GO)(http://go. princeton.edu/cgi-bin/GOTermFinder)分析。GO分析被用來檢驗(yàn)算法找到的雙聚類的生物學(xué)意義，對產(chǎn)生的雙聚類結(jié)果作真實(shí)性的驗(yàn)證。當(dāng)某個(gè)結(jié)果在GO分析中有較小的P-value值，則說明該簇基因在某些細(xì)胞功能中有特別的生物意義。

2.2人工合成數(shù)據(jù)集

人工合成數(shù)據(jù)集由實(shí)驗(yàn)人員隨機(jī)生成一個(gè)數(shù)據(jù)矩陣，再往該數(shù)據(jù)矩陣中嵌入不同的雙聚類模型，不同噪聲等級(jí)的雙聚類，不同數(shù)量的雙聚類或不同重疊度的雙聚類。當(dāng)用該合成數(shù)據(jù)運(yùn)行算法得出結(jié)果后，可以對雙聚類結(jié)果進(jìn)行匹配分?jǐn)?shù)計(jì)算［7］，該匹配分?jǐn)?shù)用來計(jì)算算法找到的雙聚類結(jié)果與人工嵌入雙聚類的匹配度，以此來衡量算法的性能。一般而言，算法的擴(kuò)展性能評估由合成數(shù)據(jù)集測試，Gao等［8］在不斷增加合成數(shù)據(jù)行、列和閾值數(shù)量的情況下，記錄算法的運(yùn)行時(shí)間，由此來評估該算法效率。

3　總結(jié)

雙聚類是一個(gè)較為年輕的學(xué)術(shù)領(lǐng)域，在如今各種數(shù)據(jù)規(guī)模呈指數(shù)級(jí)別增長的年代，對它的研究有著重要的意義。本文主要介紹了雙聚類在生物基因分析領(lǐng)域中的發(fā)展歷程，許多其它新興的領(lǐng)域（如數(shù)據(jù)挖掘，文本挖掘，推薦系統(tǒng)，電子商務(wù)等）都需要我們?nèi)ヌ剿髋c研究。

［1］Hartigan J A.Direct clustering of a data matrix.[J].Journal of the American Statistical Association,1972,67:123-129.

［2］Getz G,Levine E,Domany E.Coupled two-way clustering analysis of gene microarray data.[J].Proceedings of the national academy of sciences of the united states of america,2000:12079-12084.

［3］Cheng Y,Church G M.Biclustering of expression data.[J].In proceedings of the 8th International Conference on Intelligent Systems for Molecular Biology,2000:75-85.

［4］Ben-Dor A,Chor B,Karp R et al.Discovering local structure in gene expression data:the order-preserving submatrix problem.[J].In proceedings of the 6th international conference on computacional biology, 2002:49-57.

［5］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.

［6］Hedenfalk I,Duggan D,Chen Y et al.Gene-expression profiles in hereditary breast cancer.[J].New England Journal of Medicine, 2001,344(8):539-548.

［7］Preli?A,Bleuler S,Zimmermann P et al.A systematic comparison and evaluation of biclustering methods for gene expression data.[J].Bioinformatics,2006,22(9):1122-1129.

［8］Byron J G,Griffith O L,Ester M et al.On the deep Order-Preserving submatrix problem:a best effort approach.[J].Journal of IEEE Transactions on Knowledge and Data,2012,24(2):309-325.

李美航（1990-），男，碩士，研究方向?yàn)閿?shù)據(jù)挖掘、雙聚類分析；黃英仁（1992-），男，本科，研究方向?yàn)閿?shù)據(jù)挖掘。