基因表達(dá)數(shù)據(jù)中的局部模式挖掘研究綜述

姜 濤 李戰(zhàn)懷

1(河南財(cái)經(jīng)政法大學(xué)計(jì)算機(jī)與信息工程學(xué)院 鄭州 450046) 2(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 西安 710129) (jiangtaoxxx@126.com)

基因微陣列(DNA microarray)技術(shù)是DNA重組與聚合酶鏈?zhǔn)椒磻?yīng)(polymerase chain reaction, PCR)擴(kuò)增這兩大技術(shù)出現(xiàn)之后產(chǎn)生的一項(xiàng)重大生物技術(shù)[1].通過微陣列實(shí)驗(yàn)，生物學(xué)家能夠同一時(shí)間內(nèi)監(jiān)測(cè)大量基因在特定生理過程中的動(dòng)態(tài)表達(dá)水平，進(jìn)而將基因的活動(dòng)狀態(tài)相對(duì)全面地展示出來.同以往的單基因表達(dá)研究模式相比，基因微陣列技術(shù)使得人們能夠在基因組層面上以全局的、系統(tǒng)的視角來解釋生命現(xiàn)象與本質(zhì).自從其發(fā)明以來，該技術(shù)已經(jīng)應(yīng)用到生物和醫(yī)學(xué)研究等許多應(yīng)用中.例如，在癌癥研究中，它的出現(xiàn)使得人們能夠更好地理解腫瘤發(fā)生的生物學(xué)機(jī)制，進(jìn)而發(fā)現(xiàn)新的目標(biāo)和新的藥物，并制定可以裁剪的個(gè)性化治療方案.然而，基因在某一生理過程中的表達(dá)數(shù)據(jù)只是某一狀態(tài)下的表型數(shù)據(jù)，如何揭示大量基因表型數(shù)據(jù)背后的基因功能及其生命現(xiàn)象的本質(zhì)才是設(shè)計(jì)微陣列實(shí)驗(yàn)的初衷.因?yàn)閿?shù)據(jù)挖掘技術(shù)能夠從大量的數(shù)據(jù)中發(fā)現(xiàn)不易覺察的信息，或者挖掘出某些潛在的有價(jià)值的模式，所以在生物醫(yī)學(xué)等領(lǐng)域的探索中有著廣泛的應(yīng)用.

基因表達(dá)數(shù)據(jù)反映的是直接或間接測(cè)量得到的基因轉(zhuǎn)錄產(chǎn)物mRNA在細(xì)胞中的豐度[2].檢測(cè)細(xì)胞中 mRNA 豐度的方法主要有4種：cDNA 微陣列、寡核苷酸芯片、基因表達(dá)系列分析(serial analysis of gene expression， SAGE)、反轉(zhuǎn)錄PCR(reverse transcription-PCR， RT-PCR).由于生物體中的細(xì)胞種類繁多且基因表達(dá)隨著時(shí)空的改變而變化，與其他數(shù)據(jù)相比，基因表達(dá)數(shù)據(jù)要更為復(fù)雜、數(shù)據(jù)量要更大、數(shù)據(jù)的增長(zhǎng)速度也要更快.基因微陣列之上的基因表達(dá)數(shù)據(jù)可以看作n×m的矩陣，其中n為基因數(shù)目(行數(shù))、m為實(shí)驗(yàn)條件個(gè)數(shù)(列數(shù))、矩陣中的每個(gè)屬性值代表某個(gè)基因在某個(gè)實(shí)驗(yàn)條件下的表達(dá)水平.基因表達(dá)數(shù)據(jù)中蘊(yùn)藏著基因活動(dòng)的信息，如細(xì)胞處于何種狀態(tài)(正常、惡化等)、藥物對(duì)癌細(xì)胞的作用是否見效，能夠從很大程度上反映細(xì)胞的當(dāng)前生理狀態(tài).通過對(duì)基因表達(dá)數(shù)據(jù)的分析能夠達(dá)到預(yù)測(cè)基因功能與獲取基因表達(dá)調(diào)控網(wǎng)絡(luò)等信息的目的，這也是基因微陣列在生物醫(yī)學(xué)等領(lǐng)域廣泛應(yīng)用的關(guān)鍵因素之一.

自從Hartigan[3]發(fā)表重要研究成果，即將矩陣分為若干個(gè)含有近似值的子矩陣之后，雙聚類方法得到巨大的發(fā)展.在基因表達(dá)數(shù)據(jù)分析應(yīng)用中，其旨在從中找出在若干實(shí)驗(yàn)條件下展示出同樣趨勢(shì)的若干基因所組成的鍵值對(duì)(鍵為基因，值為實(shí)驗(yàn)條件).之前，層次聚類和K均值等傳統(tǒng)方法通過“最大程度上增大組間的差異，同時(shí)最大程度上減小組內(nèi)的差異”的標(biāo)準(zhǔn)，來鑒別在所有實(shí)驗(yàn)條件下具有相似表達(dá)水平的基因組合.然而，基因不可能在所有實(shí)驗(yàn)條件下共表達(dá)，也不大可能展示出相同的表達(dá)水平，但是可能參與多種表達(dá)通路.在這種情況下，雙聚類方法應(yīng)運(yùn)而生.之后，出現(xiàn)了大量的用于基因表達(dá)數(shù)據(jù)分析的模型、算法與軟件.然而，國(guó)內(nèi)鮮有關(guān)于基因表達(dá)數(shù)據(jù)中局部模式挖掘方法的系統(tǒng)闡述.本文主要從局部模式的定義、局部模式類型與標(biāo)準(zhǔn)、局部模式的挖掘與查詢等方面，介紹了基因表達(dá)數(shù)據(jù)中局部模式挖掘當(dāng)前的研究現(xiàn)狀與進(jìn)展，詳細(xì)總結(jié)了基于定量和定性的局部模式挖掘標(biāo)準(zhǔn)以及相關(guān)的挖掘系統(tǒng)與工具，分析了存在的問題，并深入探討了未來的研究方向.

1 問題定義

挖掘局部模式所需要的源數(shù)據(jù)是一個(gè)n×m的矩陣A，其中元素ai j為實(shí)數(shù)，ai j表示基因i在實(shí)驗(yàn)條件j下的表達(dá)值.表1給出了一個(gè)基因表達(dá)數(shù)據(jù)矩陣.

本文用A表示一個(gè)基因表達(dá)數(shù)據(jù)矩陣，其中基因的集合用行集合X={x1,x2,…,xi,xi+1,…,xn}表示，實(shí)驗(yàn)條件的集合用列集合Y={y1,y2,…,yj,yj+1,…,ym}表示，ai j表示行i(或xi)和列j(或yj)之間的關(guān)系值.這樣，矩陣A的另一種表示方法就是(X,Y).假設(shè)I?X，J?Y，I與J分別表示部分行與部分列.于是AIJ=(I,J)表示A中的子矩陣，其中只包含矩陣A中的部分ai j元素.

Table 1 Example of Gene Expression Data Matrix表1 基因表達(dá)數(shù)據(jù)矩陣舉例

現(xiàn)有大部分聚類算法主要挖掘行聚類與列聚類，本文將行或列聚類稱為整體模式(單向聚類).行聚類是部分行在所有列下具有相似行為或趨勢(shì)，如圖1(a)所示，表示為AIY=(I,Y)，其中I={x1,x2,…,xp}(I?X，|I|<|X|=n)，即行模式為|I|×m的矩陣.列聚類是部分列在所有行下展現(xiàn)出相同的行為或趨勢(shì)，如圖1(b)所示，表示為AXJ=(X,J)，其中J={y1,y2,…,yq}(J?Y，|J|<|Y|=m)，即列模式為n×|J|的矩陣.

Fig. 1 Diagram of clustering and biclustering圖1 單向聚類與雙聚類示意圖

近年來出現(xiàn)了一種稱為雙聚類[1]的方法，其將標(biāo)準(zhǔn)聚類(單向聚類)算法的挖掘結(jié)果從整體模式轉(zhuǎn)變?yōu)榫植磕Ｊ?在雙聚類中，部分行在部分列下具有相同的行為或趨勢(shì)，或者部分列在部分行下展現(xiàn)出相似的行為或趨勢(shì)如圖1(c)所示.因此，雙聚類AIJ=(I,J)，包含了矩陣A中的部分行I和部分列J，其中I={x1,x2,…,xp}(I?X，|I|<|X|=n)，J={y1,y2,…,yq}(J?Y，|J|<|Y|=m).這樣，雙聚類AIJ=(I,J)定義為矩陣A中一個(gè)|I|×|J|的子矩陣，有時(shí)也將其稱為保序子矩陣(order-preserving submatrix， OPSM)[4].

本文重點(diǎn)關(guān)注的雙聚類問題的定義如下：給定矩陣A，發(fā)現(xiàn)符合某些共同特點(diǎn)的子矩陣的集合.但是，關(guān)于共同特點(diǎn)，不同的方法具有不同的定義，將在第2節(jié)中進(jìn)行總結(jié).下面以O(shè)PSM[4]為例進(jìn)行介紹.其輸入為基因表達(dá)數(shù)據(jù)，如表1所示；輸出為多個(gè)局部模式OPSM，如表2所示；運(yùn)算過程為先將每個(gè)基因的表達(dá)值按大小排序，接著替換為列標(biāo)簽，最后尋找列標(biāo)簽序列的最長(zhǎng)公共子序列(頻繁模式).表2為從表1中挖掘出來的2個(gè)局部模式OPSM，將其記為由基因和實(shí)驗(yàn)條件序列所組成的鍵值對(duì).

Table 2 Example of Local Pattern表2 局部模式舉例

Notes： Index lables ofg0,g1,g2andg3after permutation aret4t1t3t0, and the OPSM isg0g1g2g3:t4t1t3t0. Similarly, index lables ofg5,g6,g7andg8after permutation aret0t3t1t4, and the OPSM isg5g6g7g8:t0t3t1t4.

標(biāo)準(zhǔn)聚類(單向聚類)與雙聚類(雙向聚類)的差異主要體現(xiàn)在3個(gè)方面：

1) 聚類方向不同.單向聚類僅在數(shù)據(jù)矩陣的單一方向(行或列)上聚類；雙聚類則可對(duì)數(shù)據(jù)的對(duì)象(行)與屬性(列)同時(shí)聚類，如圖1所示.這樣，雙聚類解決了摘要中指出的“基因不可能在所有實(shí)驗(yàn)條件下共表達(dá)”的問題.

2) 聚類結(jié)果相關(guān)度不同.單向聚類結(jié)果可能存在屬性(列)與某些對(duì)象(行)不相關(guān)的情況；而雙聚類結(jié)果中的屬性(列)與該聚類所屬對(duì)象(行)一定相關(guān).

3) 聚類結(jié)果互異性不同.單向聚類分析所得到的結(jié)果是互異的，即一個(gè)對(duì)象(行)存在且僅存在于一個(gè)類中；雙聚類分析所得到的結(jié)果具有相容性，即一個(gè)對(duì)象(行)可以存在于多個(gè)類中，也可以不存在于任何一個(gè)類中.這樣，雙聚類解決了摘要中指出的“基因可能參與多種遺傳通路”的問題.

單向聚類與雙聚類的優(yōu)劣主要體現(xiàn)在3個(gè)方面：

1) 雙聚類利用了聚類的二元性.單向聚類從行或列中的一個(gè)維度進(jìn)行數(shù)據(jù)的劃分，但不能同時(shí)從行與列這2個(gè)維度進(jìn)行數(shù)據(jù)的劃分；而雙聚類可以同時(shí)從行與列這2個(gè)維度對(duì)數(shù)據(jù)進(jìn)行劃分.這樣，雙聚類解決了摘要中指出的“標(biāo)準(zhǔn)聚類只能發(fā)現(xiàn)少量的知識(shí)的問題”.

2) 雙聚類可發(fā)現(xiàn)隱藏的潛在模式.單向聚類將所有的行或列劃分成若干類，即發(fā)現(xiàn)整體模式，該特性使得其隱藏了若干潛在模式；而雙聚類從行與列這2個(gè)維度進(jìn)行數(shù)據(jù)劃分的特性，使得行或列不必屬于同一類，即發(fā)現(xiàn)局部模式，那么就可以發(fā)現(xiàn)不明顯的潛在模式.這樣，雙聚類解決了摘要中指出的“標(biāo)準(zhǔn)聚類只能發(fā)現(xiàn)少量的知識(shí)的問題”.

3) 雙聚類可降低數(shù)據(jù)的維度.單向聚類只在單軸方向(行或列)上降低數(shù)據(jù)的維度；雙聚類則可同時(shí)降低雙軸方向上的維度.

2 局部模式類型與標(biāo)準(zhǔn)

現(xiàn)有的局部模式主要包括兩大類：恒值雙聚類(圖2中的A1，A2，A3)和相干雙聚類(圖2中的A4，A5，A6)[5].恒值雙聚類又可以細(xì)分為三小類：恒值雙聚類(圖2中的A1)、行恒值雙聚類(圖2中的A2)和列恒值雙聚類(圖2中的A3).相干雙聚類也可以細(xì)分為三小類：加性相干雙聚類(圖2中的A4)、乘性相干雙聚類(圖2中的A5)和相干演化雙聚類(圖2中的A6)[5].

Fig. 2 Examples of different types of biclusters圖2 雙聚類模式類型舉例

恒值雙聚類和相干雙聚類各自的特點(diǎn)如表3所示.

恒值雙聚類是一種特殊的雙聚類，其中的所有元素值都相同，即ai j=μ；行恒值雙聚類中的每一行元素值分別相同，行與行之間相差一個(gè)常數(shù)或者倍數(shù)，即ai j=μ+ai或ai j=μ×ai，其中ai表示行常數(shù)或倍數(shù)；列恒值雙聚類中的每一列元素值分別相同，列與列之間相差一個(gè)常數(shù)或者倍數(shù)，即ai j=μ+βj或ai j=μ×βj，其中βj表示列常數(shù)或倍數(shù).

相干雙聚類與恒值雙聚類有所不同.加性相干雙聚類中的每個(gè)元素值基本上不相同，每一行與列值是在一個(gè)基準(zhǔn)值μ的基礎(chǔ)上加上行常數(shù)ai和列常數(shù)βj，即ai j=μ+ai+βj；乘性相干雙聚類中的每個(gè)元素值基本上也不相同，每一行與列值是在一個(gè)基準(zhǔn)值μ的基礎(chǔ)上乘以行倍數(shù)ai和列倍數(shù)βj，即ai j=μ×ai×βj；相干演化雙聚類不太在意每個(gè)元素值，重在關(guān)注前后行或列之間的表達(dá)值的升降，如果2行或列具有相同和相反的趨勢(shì)，那么二者可以聚為一類.

根據(jù)雙聚類間的關(guān)系，一組雙聚類可分為如下類型[5]，如圖3所示.

1) 單獨(dú)的雙聚類，如圖3(a)所示；2)互斥行與列的雙聚類組，如圖3(b)所示；3)無重疊的棋盤型雙聚類組，如圖3(c)所示；4)互斥行的雙聚類組，如圖3(d)所示；5)互斥列的雙聚類組，如圖3(e)所示；6)無重疊的樹形雙聚類組，如圖3(f)所示；7)無重疊的非排它的雙聚類組，如圖3(g)所示；8)層次型重疊雙聚類組，如圖3(h)所示；9)任意位置重疊的雙聚類組，如圖3(i)所示.

Table 3 Types of Biclusters表3 雙聚類類型

Fig. 3 Group types of biclusters圖3 雙聚類組的類型

3 研究現(xiàn)狀

雙聚類的概念最初由Hartigan[3]提出，其作為對(duì)矩陣中的行與列同時(shí)聚類的一種方法，并將其命名為Direct聚類.Cheng和Church[1]提出了基因表達(dá)數(shù)據(jù)的雙聚類，并引入了元素殘差以及子矩陣的均方殘差(mean squared residue,MSR)[1]的概念.文獻(xiàn)[1]展示出MSR在發(fā)現(xiàn)行恒值雙聚類、列恒值雙聚類、加性相干雙聚類(shift biclusters)方面具有良好的性能.然而，其在發(fā)現(xiàn)乘性相干雙聚類(scale biclusters)方面的表現(xiàn)卻差強(qiáng)人意.該算法是一種貪婪方法.首先將整個(gè)數(shù)據(jù)矩陣作為初始化數(shù)據(jù)；接著刪除元素殘差或者均方殘差最大元素或者行列，依次遞歸下去直到剩余矩陣的MSR低于某個(gè)閾值；然后增加部分元素或者行列，保證所得矩陣的MSR也低于該閾值.該方法效率較低，因?yàn)橐淮沃荒芡诰蛞粋€(gè)雙聚類.Ben-Dor等人[4,6]介紹了一種特殊的雙聚類模型OPSM，并證明了其是NP難問題.OPSM與雙聚類的關(guān)系如下：本質(zhì)上OPSM屬于雙聚類，只是一個(gè)更特殊的雙聚類而已.大部分雙聚類主要是在實(shí)數(shù)數(shù)據(jù)上做恒值模式、行/列恒值模式、加性相干模式、乘性相干模式、相干演化模式等的挖掘工作.OPSM首先對(duì)每一行數(shù)據(jù)進(jìn)行從小到大的排列，再替換成相應(yīng)的列標(biāo)簽，這樣就將實(shí)數(shù)數(shù)據(jù)轉(zhuǎn)化序列數(shù)據(jù)，具體的序列操作有頻繁集挖掘、最長(zhǎng)公共子序列查找等.大部分的OPSM挖掘主要操作對(duì)象是序列數(shù)據(jù)，少部分OPSM挖掘工作的操作對(duì)象是未經(jīng)預(yù)處理的實(shí)數(shù)數(shù)據(jù).這種轉(zhuǎn)化可以從一定程度上減少噪聲數(shù)據(jù)的影響，同時(shí)也可以減少計(jì)算量.隨后，人們給出了基于定量測(cè)度和定性測(cè)度的雙聚類挖掘方法.定量測(cè)度包括均方殘差(MSR)[1]、方差和(sum of squares,SSQ)[3]、殘差均值(mean residue,MR)[7]、平方殘差和(sum squared residue,SSR)[8]、平均相關(guān)值(average correlation value,ACV)[9]、平均斯皮爾曼秩相關(guān)系數(shù)(average spearman’s rho,ASR)[10-11]、平均一致性相關(guān)指數(shù)(average corres-pondence similarity index,ACSI)[12]等.定性測(cè)度包括上升、下降、相似、相反、同步、異步、重疊、位置、冗余、對(duì)稱、非對(duì)稱、非線性等[13-14].

近年來，基因表達(dá)數(shù)據(jù)挖掘得到生物醫(yī)學(xué)與學(xué)術(shù)界的重點(diǎn)關(guān)注，取得一定的研究成果[5,15-18].本節(jié)主要從基于定量測(cè)度的雙聚類、基于定性測(cè)度的雙聚類、基于查詢的雙聚類和約束型雙聚類等方面對(duì)基因表達(dá)數(shù)據(jù)中局部模式的挖掘方法的研究現(xiàn)狀進(jìn)行梳理和介紹.

3.1 基于定量測(cè)度的雙聚類

主要從噪聲與缺失值問題、雙聚類算法、雙聚類理論研究、現(xiàn)有方法的比較、相關(guān)系統(tǒng)與工具等方面介紹基于定量測(cè)度的雙聚類.

1) 解決噪聲與缺失值問題的工作.由于基因表達(dá)數(shù)據(jù)的來源不同且數(shù)據(jù)是由基因微陣列圖像數(shù)據(jù)轉(zhuǎn)化而來的，其中不可避免地會(huì)產(chǎn)生噪聲，所以減少噪聲數(shù)據(jù)的影響也是一項(xiàng)有意義的研究工作[18].這方面也有一些研究成果.基于Cheng等人[1]提出的δ-bicluster模型，Yang等人[7]為減少數(shù)據(jù)缺失值的影響，給出一種δ-cluster模型來發(fā)現(xiàn)相干模式，繼而設(shè)計(jì)了柔性重疊聚類(flexible overlapped clustering, FLOC)算法來挖掘任意位置有重疊的雙聚類，其中用到殘差均值MR測(cè)度.Deodhar等人[19]提出一種魯棒的有重疊的雙聚類方法，將其命名為魯棒重疊雙聚類(robust overlapping co-clustering, ROCC)，能有效地從大量的含有噪聲的數(shù)據(jù)中挖掘出稠密的、任意位置的有重疊的雙聚類.Sun等人[20]為了減少基因表達(dá)數(shù)據(jù)中噪聲的影響，提出名為Auto-Decoder的模型，利用神經(jīng)網(wǎng)絡(luò)技術(shù)來發(fā)現(xiàn)隱藏在噪聲基因表達(dá)數(shù)據(jù)中的具有重疊的雙聚類.

2) 挖掘各種類型雙聚類的工作.對(duì)于一個(gè)局部模式而言，雙聚類的類型主要包括如表3所示的兩大類與六小類[5].而對(duì)于局部模式的組合來說，雙聚類組的類型又包括如圖3所示的9種情況[5].Cho[8]給出了數(shù)據(jù)轉(zhuǎn)換的方法來解決現(xiàn)有的平方殘差和SSR測(cè)度方法只能有效地挖掘出在數(shù)值上具有偏移的雙聚類(加性相干雙聚類)，卻不能很好地解決在數(shù)值上有縮放的雙聚類(乘性相干雙聚類)的問題.Ayadi等人[10]發(fā)現(xiàn)大多數(shù)現(xiàn)有方法主要關(guān)注正相關(guān)雙聚類，而研究表明負(fù)相關(guān)雙聚類也出現(xiàn)在具有重要生物學(xué)意義的雙聚類中.為了彌補(bǔ)現(xiàn)有算法的不足，給出文化基因雙聚類算法(memetic biclustering algorithm, MBA).Divina等人[21]給出一種基于進(jìn)化計(jì)算的雙聚類方法(sequential evolu-tionary biclustering, SEBI)，用來發(fā)現(xiàn)尺寸較大、重疊較少且MSR小于某閾值的雙聚類.Odibat等人[22]發(fā)現(xiàn)現(xiàn)有方法并不能有效地挖掘矩陣數(shù)據(jù)中任意位置有重疊的雙聚類，提出一種確定性雙聚類算法，稱之為基于正負(fù)相關(guān)的重疊雙聚類(positive and negative correlation based overlapping co-clustering, PONEOCC).該算法可以有效地發(fā)現(xiàn)正負(fù)相關(guān)的任意位置上有重疊的雙聚類.同樣，該算法也可以應(yīng)用于含有噪聲的基因表達(dá)數(shù)據(jù)分析.Truong等人[23]觀察到現(xiàn)有大多數(shù)方法要么挖掘無重疊的雙聚類，要么發(fā)現(xiàn)重疊區(qū)域比較大的雙聚類，而不允許用戶指定雙聚類之間的最大重疊比例.為此，提出一種可以產(chǎn)生K個(gè)重疊的雙聚類的算法，并且這些重疊的比例低于預(yù)設(shè)閾值.與現(xiàn)有算法產(chǎn)生所有雙聚類結(jié)果的方式不同，該算法每次發(fā)現(xiàn)一個(gè)與已產(chǎn)生的結(jié)果不同的并且?guī)в幸欢ㄖ丿B比例的雙聚類.實(shí)驗(yàn)也表明該算法可以返回許多大的高質(zhì)量的雙聚類.Chen等人[24]發(fā)現(xiàn)現(xiàn)有研究已為線性模式(即相干模式)提出若干種定量相干測(cè)度，但是其缺乏挖掘所有相干模式的能力且容易被噪聲所干擾.為此，提出一種通用的線性模式相干測(cè)度最小均方誤差(minimal mean squared error,MMSE).利用該測(cè)度，雙聚類算法可以發(fā)現(xiàn)所有類型的線性模式，包括偏移(加性相干模式)、縮放(乘性相干模式)、偏移與縮放聯(lián)合模式等.Wang等人[25]提出并設(shè)計(jì)基于pScore測(cè)度和pCluster模型的方法，發(fā)現(xiàn)具有相似升降趨勢(shì)的模式.Bhattacharya等人[26]介紹了一種基于雙相關(guān)系數(shù)的聚類算法(bi-correlation clustering algorithm, BCCA).其發(fā)現(xiàn)的模式不僅具有相似的表達(dá)趨勢(shì)，而且具有共同的轉(zhuǎn)錄因子結(jié)合位點(diǎn).這項(xiàng)工作之所以有意義，是因?yàn)楝F(xiàn)有工作只考慮了前者，而忽略了后者，即在相應(yīng)的啟動(dòng)子序列上擁有共同的轉(zhuǎn)錄因子結(jié)合位點(diǎn)是一項(xiàng)能證明這些基因共表達(dá)的證據(jù).Xiao等人[27]提出一種有效的投票算法從帶有任意背景的矩陣中發(fā)現(xiàn)加性相干雙聚類.Xie等人[28]提出一種有效的方法來不間斷地檢測(cè)數(shù)值數(shù)據(jù)流之間的相關(guān)性.該方法基于離散傅里葉轉(zhuǎn)換，能快速計(jì)算時(shí)滯(異步)相關(guān)模式.Murali等人[29]提出非確定性貪婪方法xMOTIFs來發(fā)現(xiàn)具有行恒定值的雙聚類.Bergmann等人[30]提出一種大規(guī)?；虮磉_(dá)數(shù)據(jù)分析的迭代簽名算法(iterative signature algorithm, ISA)，其通過多次迭代來發(fā)現(xiàn)具有重疊的轉(zhuǎn)錄模塊.Pandey等人[31]利用范圍支持框架(range support pattern, RAP)來挖掘恒值雙聚類和行恒值雙聚類.定量測(cè)度如表4所示:

Table 4 Quantitative Measures of Biclusters表4 雙聚類的定量測(cè)度

3) 主要進(jìn)行雙聚類理論研究的工作.Teng等人[9]提出一種測(cè)度方法ACV來發(fā)現(xiàn)同質(zhì)聚類.實(shí)驗(yàn)表明其更適用于加性與乘性相干模式的搜索.Ayadi等人[11]提出一種枚舉算法BiMine來挖掘基因表達(dá)數(shù)據(jù)中的雙聚類.其有3個(gè)新特點(diǎn)：①其依賴于ASR評(píng)價(jià)函數(shù)；②其利用雙聚類枚舉樹BET來索引挖掘出來的雙聚類；③設(shè)計(jì)了減少搜索空間的剪枝規(guī)則.Ayadi等人[12]利用平均一致性相關(guān)指數(shù)，ACSI來評(píng)估相干雙聚類，并利用有向無環(huán)圖組建這些雙聚類.Denitto等人[32]為了解決雙聚類與生俱來的高復(fù)雜度問題，提出一種新的二元因子圖方法.其將雙聚類問題轉(zhuǎn)化成序列搜索問題，每次挖掘一個(gè)雙聚類，同時(shí)利用Max Sum算法緩解以往方法的擴(kuò)展性問題.Lee等人[33]提出一種稀疏奇異值分解方法(sparse singular value decomposition, SSVD)，作為一種探索分析工具來發(fā)現(xiàn)髙維度數(shù)據(jù)矩陣中棋盤形狀的雙聚類.棋盤形狀的雙聚類如圖3(c)所示.Tanay等人[34]提出一種帶有統(tǒng)計(jì)模型的圖理論的方法——支持雙聚類分析的統(tǒng)計(jì)方法(statistical-algorithmic method for bicluster analysis, SAMBA)，來發(fā)現(xiàn)基因表達(dá)數(shù)據(jù)中具有重要意義的雙聚類.Sill等人[35]引入穩(wěn)定性選擇的因素來改善稀疏奇異值分解方法的性能，之后提出了基于抽樣的支持稀疏奇異值分解的穩(wěn)定性選擇方法(stability selection for sparse singular value de-composition, S4VD)來發(fā)現(xiàn)穩(wěn)定性雙聚類.Tchagang等人[36]受排序保序框架與最小均方殘留測(cè)度MSR的啟發(fā)，提出了基于階次保持的短時(shí)序列分析(analysis of short time-series using rank order preservation, ASTRO)與最小均方殘差(minimum mean squared residue, MiMeSR)方法，從短時(shí)間序列基因表達(dá)數(shù)據(jù)中挖掘具有生物學(xué)意義的模式.Tan等人[37]詳細(xì)給出了基因表達(dá)數(shù)據(jù)分析中3個(gè)聚類方法的算法，并分析了復(fù)雜度問題.Humrich等人[38]發(fā)現(xiàn)精確的雙聚類算法復(fù)雜度為指數(shù)級(jí)、多項(xiàng)式級(jí)的算法卻是非精確的.為了減少在尋找最大精確OPSM過程中得到精確結(jié)果、有理論保證、算法可擴(kuò)展、不受噪聲數(shù)據(jù)影響，提出一種新的精確算法，即固定參數(shù)可解整數(shù)規(guī)劃方法.Joung等人[39]為降低在發(fā)現(xiàn)基因表達(dá)數(shù)據(jù)中相干模式的計(jì)算復(fù)雜度，提出一種概率共同演化雙聚類算法(probabilistic coevolutionary biclustering algorithm, PCOBA).Cho等人[40]利用規(guī)范化、確定譜的初始化和增量本地搜索等策略，給出雙聚類軟件Co-clustering，解決前期提出的最小平方和殘差雙聚類(minimum sum-squared residue coclustering, MSSRCC)模型的局部極小化問題以及劃分聚類算法中的退化嚴(yán)重等問題.Cho等人[41]介紹了2種與MSR相似的平方殘差測(cè)度，同時(shí)提出2種有效的基于K均值的雙聚類算法.Yang等人[42]觀察到當(dāng)遇到大量的異質(zhì)數(shù)據(jù)時(shí)，現(xiàn)有的聚類方法往往得不到滿意的結(jié)果.為此，介紹了一種應(yīng)用范圍更為普遍的方法correlated雙聚類，來發(fā)現(xiàn)具有直觀生物學(xué)意義的聚類.其首先利用奇異值分解來鑒別相關(guān)聚類，接著將問題轉(zhuǎn)化為2種全局聚類問題，最后利用混合聚類算法與Lift算法來生成雙聚類δ-corBiclusters.Roy等人[43]提出雙聚類挖掘方法——共調(diào)控雙聚類(co-regulated biclustering, CoBi)，基于BiClust樹，其只需一次遍歷就可發(fā)現(xiàn)所有的正負(fù)相關(guān)的雙聚類.

4) 對(duì)現(xiàn)有算法進(jìn)行全方位比較的工作.Roy等人[44]介紹了可能從基因表達(dá)數(shù)據(jù)中觀察到的感興趣的模式，同時(shí)討論了檢測(cè)具有相似表達(dá)模式的基因功能組的雙聚類技術(shù).Eren等人[45]觀察到每種新提出的雙聚類方法在文獻(xiàn)中只和少量的現(xiàn)有方法作了比較，這樣對(duì)于不同的局部模式挖掘任務(wù)，往往不知道選用哪種雙聚類方法更合適.為評(píng)估現(xiàn)有方法的優(yōu)缺點(diǎn)，利用BiBench包比較了12種算法在不同實(shí)驗(yàn)條件、噪聲、重疊比例等指標(biāo)下的性能.Saber等人[46]給出微陣列數(shù)據(jù)分析方面的雙聚類方法的綜述.

5) 雙聚類挖掘系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)的工作.Barkow等人[47]設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)名為BicAT的工具，其中包括若干現(xiàn)有算法的實(shí)現(xiàn)，方便用戶比較并選用合適的算法.同時(shí)還提供了數(shù)據(jù)的預(yù)處理、聚類、數(shù)據(jù)的可視化、后期處理等步驟.其他相關(guān)系統(tǒng)的總結(jié)如表5所示:

Table 5 Systems or Tools of Biclusters Based on Quantitative Measures表5 基于定量測(cè)度的雙聚類系統(tǒng)或工具

Continued (Table 5)

① http://www.info.univ-angers.fr/pub/hao/BicFinder.html

② http://grafia.cs.ucsb.edu/autodecoder/

③ http://www.isical.ac.in/～rajat/

④ http://genomics10.bu.edu/murali/xmotif

⑤ http://www2.unil.ch/cbg/index.php?title=ISA

⑥ http://vk.cs.umn.edu/gaurav/rap/

⑦ http://www.unc.edu/?haipeng

⑧ http://www.cs.tau.ac.il/～rshamir/biclust.html, http://acgt.cs.tau.ac.il/expander/

⑨ http://s4vd.r-forge.r-project.org/,https://github.com/mwsill/s4vd

⑩ http://www.benoslab.pitt.edu/astro/

http://www.cs.utexas.edu/users/dml/Software/cocluster.html

https://sites.google.com/site/swarupnehu/publications/resources

http://www.tik.ee.ethz.ch/sop/bicat

3.2 基于定性測(cè)度的雙聚類

本節(jié)也從噪聲與缺失值問題、雙聚類算法、雙聚類理論研究、現(xiàn)有方法的比較、相關(guān)系統(tǒng)等方面來介紹基于定性測(cè)度的雙聚類.需要指出的是，該類方法解決了摘要中指出的“基因不可能展示出相同的表達(dá)水平”的問題.

1) 解決噪聲與缺失值問題的工作.Chui和Yip等人[13,48]試圖利用多份數(shù)據(jù)的保序子矩陣挖掘方法(OPSM-repeated measurements, OPSM-RM)來消除數(shù)據(jù)噪聲的影響.Fang等人[14]為了挖掘放松的OPSM，提出包含以行或列為中心的OPSM-Growth方法.Zhang等人[49]為減少數(shù)據(jù)中噪聲的影響，提出了一種近似保序聚類模型(approximate order preserving clusters, AOPC).隨后，F(xiàn)ang等人[50-51]基于桶和概率的方法，來發(fā)現(xiàn)非嚴(yán)格的聚類OPSM.Peng等人[52]設(shè)計(jì)實(shí)現(xiàn)了一個(gè)利用多份數(shù)據(jù)來挖掘基因表達(dá)數(shù)據(jù)的軟件包.其給出幾種轉(zhuǎn)換模型，支持不同種類的擴(kuò)展性非相似/距離測(cè)度，提供了一些K均值聚類方法的變種，介紹了3種流行的聚類質(zhì)量的評(píng)價(jià)方法.Abdullah等人[53]為了從含有噪聲的數(shù)據(jù)中發(fā)現(xiàn)非對(duì)稱重疊雙聚類，提出了基于交叉最小化與圖形繪制的雙聚類技術(shù).Henriques等人[54]提出一種基于序列模式挖掘的雙聚類(biclu-stering based on sequential pattern mining, BicSPAM)的方法，它是第1個(gè)試圖解決OPSM允許對(duì)稱并且能夠容忍不同級(jí)別噪聲的方法.Li等人[55]提出確定性算法——定性雙聚類(qualitative biclustering, QUBIC)，從含有噪聲的數(shù)據(jù)中高效地發(fā)現(xiàn)重疊的乘性相干雙聚類.

2) 挖掘各種類型雙聚類的工作.其主要挖掘具有同樣升降趨勢(shì)、反向趨勢(shì)、同步(無時(shí)間延遲)、異步(具有時(shí)間延遲)、重疊、對(duì)稱、非對(duì)稱、非線性等特性的局部模式.每個(gè)算法包含上述特性中的一個(gè)或多個(gè).Liu等人[56]發(fā)現(xiàn)現(xiàn)有的相似測(cè)度大多數(shù)基于歐氏距離或余弦距離，提出一種靈活有效的聚類模型，命名為保序雙聚類(order preserving cluster, OP-Cluster).該模型判斷2個(gè)對(duì)象相似的標(biāo)準(zhǔn)是不同實(shí)驗(yàn)條件下基因表達(dá)值排序的順序相同，也就是共調(diào)控的基因表達(dá)水平在同樣條件下同升同降.Wang等人[57]給出一種基于最近鄰(nearest neighbor, NN)的新的測(cè)度方法來指導(dǎo)相似模式聚類.Zhao等人[58]觀察到基于模式和趨勢(shì)的聚類方法不能直接應(yīng)用于同時(shí)具有正相關(guān)和負(fù)相關(guān)的共調(diào)控基因聚類.為此設(shè)計(jì)了一種編碼模式，其中有相同編碼的基因是正相關(guān)或負(fù)相關(guān)調(diào)控基因.在此基礎(chǔ)上提出共表達(dá)基因聚類(coregulated gene cluster, CO-GCLUSTER)算法，來發(fā)現(xiàn)最大共調(diào)控基因聚類的.Jiang等人[59]發(fā)現(xiàn)基于模式的聚類方法返回大量高重復(fù)度的聚類，使得用戶很難鑒別感興趣的模式，同時(shí)不同的模式或測(cè)度需要不同的算法，而沒有一個(gè)通用的基于模式的聚類模型.為此，提出一種通用的質(zhì)量驅(qū)動(dòng)的top-k模式挖掘模型Q-Clustering，來提升所發(fā)現(xiàn)的雙聚類的質(zhì)量.閆雷鳴等人[60]為挖掘非線性相關(guān)的模式，引入二次互信息的相似性度量，建立了一種時(shí)序數(shù)據(jù)非線性相關(guān)模型，提出基于互信息的時(shí)間序列雙聚類算法(mutual-information-based time series biclustering algorithm, MI-TSB).印瑩等人[61-62]提出一種從時(shí)序微陣列數(shù)據(jù)中挖掘同步和異步共調(diào)控基因聚類的方法Reg-Cluster.印瑩等人[63]發(fā)現(xiàn)現(xiàn)有方法只適用于相同列下的雙聚類，而非相同列下的聚類也具有重要意義.為此，提出異步(具有時(shí)間偏移)的共表達(dá)模式的挖掘方法——時(shí)間偏移聚類(time-shifting cluster, ts-Cluster).趙宇海等人[64-65]提出雙聚類方法g-Cluster來發(fā)現(xiàn)具有正負(fù)相關(guān)的共調(diào)控基因聚類.Wang等人[66]設(shè)計(jì)了發(fā)現(xiàn)縮放、偏移、反轉(zhuǎn)時(shí)滯表達(dá)模式的模型——時(shí)滯聚類(time-delayed cluster, td-Cluster)，并且很容易地從2維數(shù)據(jù)擴(kuò)展到3維數(shù)據(jù).Wang等人[67]給出具有恒定值的子矩陣，又稱局部保守聚類的方法(local conserved cluster, LC-Cluster)，其實(shí)際上是OPSM中的一種特殊情況.Ji等人[68]提出一種正負(fù)相關(guān)共調(diào)控基因聚類的模型(positive and negative co-regulated gene cluster, PNCGC).該模型可以鑒別關(guān)聯(lián)規(guī)則丟失的共調(diào)控聚類，減少了被Apriori模型引入的不相關(guān)聚類.Ji等人[69]發(fā)現(xiàn)現(xiàn)有雙聚類方法1次只能比較2個(gè)基因間的相似度，且相似度打分函數(shù)使得聚類方法丟失了許多重要信息.為此，提出了一種時(shí)滯共調(diào)控雙聚類的方法q-Cluster，其每次可以比較多個(gè)基因且可以產(chǎn)生完整的雙聚類.Ji等人[70]為了發(fā)現(xiàn)具有一致或者相似波動(dòng)趨勢(shì)的雙聚類，給出一種快速層次雙聚類算法(quick hierarchical biclustering, QHB).該算法不僅能生成雙聚類，而且能夠產(chǎn)生已發(fā)現(xiàn)的雙聚類間關(guān)系的層次圖.Chen等人[71]為了提高正負(fù)相關(guān)模式挖掘的性能，提出一種名為上下位模式(up-down bit pattern, UDB)，將挖掘算法的時(shí)間復(fù)雜度從指數(shù)級(jí)別減少到多項(xiàng)式等級(jí).姜濤等人[72]為了快速挖掘基因表達(dá)數(shù)據(jù)中的保序子矩陣(OPSM)，提出了基于蝶形網(wǎng)絡(luò)的基因表達(dá)數(shù)據(jù)的并行分割與挖掘方法.其擴(kuò)展了Hama BSP 框架，使得節(jié)點(diǎn)在每個(gè)超步中只需要與指定的某個(gè)節(jié)點(diǎn)通信即可，且最多使用lbN個(gè)超步，N為集群中計(jì)算節(jié)點(diǎn)數(shù)目.實(shí)驗(yàn)表明所提出方法彌補(bǔ)了Apache Hama系統(tǒng)的處理框架BSP 的不足，減少了信息傳遞量，加速了處理速度，同時(shí)從理論上證明了該方法能保證挖掘結(jié)果的完整性.

3) 主要進(jìn)行雙聚類理論研究的工作.Trapp等人[73]發(fā)現(xiàn)現(xiàn)有方法在解決NP難問題OPSM時(shí)都不能保證結(jié)果最優(yōu)，為此提出了基于線性規(guī)劃的確定性方法，同時(shí)討論了挖掘特定類型模式的計(jì)算復(fù)雜度問題.Kriegel等人[74]提出基于局部密度閾值的OPSM挖掘方法，試圖改變現(xiàn)有的基于全局密度閾值方法并不能適用于每種OPSM的現(xiàn)狀.安平[75]利用互信息和核密度進(jìn)行雙聚類挖掘.Zhang等人[76]發(fā)現(xiàn)現(xiàn)有的大多數(shù)方法假設(shè)基因表達(dá)數(shù)據(jù)是同質(zhì)的，并不適用于異質(zhì)數(shù)據(jù).為了挖掘異質(zhì)數(shù)據(jù)中的相干模式，提出稱為F-cluster的模型.Cho等人[77]給出一種基于壞字符規(guī)則的KMP算法(the Knuth-Morris-Pratt algorithm)，其試圖快速地匹配保序模式.Hochbaum等人[78]轉(zhuǎn)換了最大OPSM的挖掘思路，由原來的發(fā)現(xiàn)最多行列的雙聚類轉(zhuǎn)化成如何從源數(shù)據(jù)中減少行列的問題.設(shè)計(jì)了參數(shù)為5的OPSM挖掘方法MinOPSM，將雙聚類問題轉(zhuǎn)化為一個(gè)2次不可分離的集合覆蓋問題.接著，給出另一種結(jié)合原始對(duì)算法的公式化方法將近似系數(shù)提升為3.Yoon等人[79]為解決雙聚類的高時(shí)間復(fù)雜度問題，利用零抑制二元決策圖(zero-suppressed binary decision diagrams, ZBDDs)，從基因表達(dá)數(shù)據(jù)中發(fā)現(xiàn)相干雙聚類.Painsky等人[80-81]為了發(fā)現(xiàn)“每行只屬于一類，而每列可以屬于多個(gè)聚類”的雙聚類，如圖3(d)所示，介紹了基于最優(yōu)集合覆蓋的方法.Ji等人[82]為了解決密集數(shù)據(jù)中閉合模式的發(fā)現(xiàn)問題，提出了2種壓縮層次挖掘方法.該方法首先壓縮源挖掘空間，接著將整個(gè)挖掘任務(wù)層次化地分割成獨(dú)立的子任務(wù)，最后單獨(dú)挖掘每一個(gè)子任務(wù).薛云等人[83-84]發(fā)現(xiàn)現(xiàn)有方法在挖掘局部模式Deep OPSM的過程中計(jì)算代價(jià)較大，提出了基于所有公共子序列的方法，實(shí)驗(yàn)證明所提方法具有良好的有效性與高效性.Kuang等人[85]觀察得到大多數(shù)現(xiàn)有OPSM挖掘方法是基于貪婪策略或者Apriori原理，使得挖掘結(jié)果丟失了包括Deep OPSM在內(nèi)的一些有意義的OPSM.為此，提出了基于序列模式挖掘的精確OPSM搜索算法.同時(shí)，利用動(dòng)態(tài)規(guī)劃、后綴樹和分支界限規(guī)則來增強(qiáng)算法的性能.Kim等人[86]為解決數(shù)字字符串之上的保序匹配，定義了模式的前綴和最近鄰表示，提出了單模式與多模式匹配算法.前者在一般情況下的時(shí)間復(fù)雜度為O(nlogm)，經(jīng)過優(yōu)化后的時(shí)間復(fù)雜度為O(n+mlogm)，后者的時(shí)間復(fù)雜度為O(nlogm).Bruner等人[87]為了解決保序模式匹配的NP完全問題，提出固定參數(shù)算法，其在最壞情況下的時(shí)間復(fù)雜度為O(1.79run(T)nk).當(dāng)T具有少量的上升與下降趨勢(shì)時(shí)，該算法的時(shí)間復(fù)雜度為O(1.79nnk).Crochemore等人[88]為解決保序模式匹配問題，給出一種時(shí)間復(fù)雜度為O(nlog logn)的非完整保序后綴樹的創(chuàng)建方法.同時(shí)給出一種時(shí)間復(fù)雜度為O(nlogn/log logn)的完整保序后綴樹的創(chuàng)建方法.Chen等人[89]發(fā)現(xiàn)現(xiàn)有方法在鑒別具有恒定表達(dá)水平的雙聚類時(shí)表現(xiàn)不佳，提出了一種2階段雙聚類方法,其在二進(jìn)制數(shù)據(jù)與定性數(shù)據(jù)上具有良好的性能.對(duì)定性測(cè)度的總結(jié)如表6所示：

Table 6 Qualitative Measures of Biclusters表6 雙聚類的定性測(cè)度

Notes： “√” means yes; “NA” means unavailable.

4) 對(duì)現(xiàn)有算法進(jìn)行全方位比較的工作.文獻(xiàn)[5,15-18]從相關(guān)算法所挖掘模式的生物學(xué)意義及其難點(diǎn)、各種算法的優(yōu)缺點(diǎn)、相關(guān)應(yīng)用等方面進(jìn)行了詳細(xì)的歸納、比較、總結(jié)，同時(shí)對(duì)進(jìn)一步可以研究的方向進(jìn)行了展望.

5) 雙聚類挖掘系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)的工作.Gao等人[91-92]提出并實(shí)現(xiàn)了一種KiWi框架與系統(tǒng)工具，該方法利用k和w這2個(gè)參數(shù)來約束計(jì)算資源和搜索空間.Santamaría等人[93]設(shè)計(jì)并實(shí)現(xiàn)了一種基因表達(dá)數(shù)據(jù)中雙聚類的可視化工具BicOverlapper.其他相關(guān)系統(tǒng)的總結(jié)如表7所示：

Table 7 Systems or Tools of Biclusters Based on Qualitative Measures表7 基于定性測(cè)度的雙聚類系統(tǒng)或工具

① http://web.ist.utl.pt/rmch/software/bicspam

② http://csbl.bmb.uga.edu/～maqin/bicluster/, http://csbl.bmb.uga.edu/publications/materials/ffzhou/QServer/, http://csbl.bmb.uga.edu/～maqin/bicluster/web.html

③ http://akebono.stanford.edu/users/sryoon/tcbb05

④ http://people.ee.ethz.ch/～sop/bimax/

⑤ http://www.bcgsc.ca/platform/bioinfo/ge/kiwi/

⑥ http://vis.usal.es/bicoverlapper

3.3 基于查詢的雙聚類

基于查詢的雙聚類[94]來自生物信息領(lǐng)域[95-98]，應(yīng)用對(duì)象是基因表達(dá)數(shù)據(jù).首先由用戶根據(jù)經(jīng)驗(yàn)來提供功能相關(guān)或共表達(dá)的種子基因，接著利用該種子對(duì)搜索空間剪枝或者對(duì)雙聚類的挖掘與搜索進(jìn)行指導(dǎo).Hochreiter等人[99]設(shè)計(jì)了雙聚類獲取的因素分析框架(factor analysis for bicluster acquisition, FABIA).該框架是一種乘性相干值模型，衡量不同基因在相關(guān)實(shí)驗(yàn)條件下的線性相關(guān)性，并捕捉從數(shù)據(jù)中觀察到的重尾分布，還允許利用有充分依據(jù)的模型選擇方法和應(yīng)用貝葉斯技術(shù).Jiang等人[100]設(shè)計(jì)了一種基因模式搜索(gene pattern explorer, GPX)的可視化工具，其利用圖形化界面對(duì)OPSM數(shù)據(jù)進(jìn)行上鉆或者下翻，方便生物學(xué)家分析基因表達(dá)數(shù)據(jù).Dhollander等人[101]為使現(xiàn)有挖掘方法能利用先驗(yàn)知識(shí)并回答指定的問題，提出一種基于貝葉斯的查詢驅(qū)動(dòng)的雙聚類方法(query-driven biclustering, QDB).同時(shí)給出一種基于實(shí)驗(yàn)條件列表的聯(lián)合方法，來實(shí)現(xiàn)關(guān)鍵詞的多樣性并免除必須事先定義閾值等問題.隨后，Zhao等人[102]對(duì)QDB方法進(jìn)行了改進(jìn)，提出了ProBic方法.雖然二者在概念上相似，但是也有不同之處.QDB方法利用概率關(guān)系模型擴(kuò)展貝葉斯框架，并采用基于期望最大化的直接指定方法來學(xué)習(xí)該概率模型.Alqadah等人[103]提出一種利用低方差和形式概念分析優(yōu)勢(shì)組合的方法，命名為基于查詢的雙聚類算法(query based biclustering algorithm, QBBC)，來發(fā)現(xiàn)在部分實(shí)驗(yàn)條件下具有相同表達(dá)趨勢(shì)的基因.由用戶給出共表達(dá)或具有同樣功能的種子基因，來縮減搜索空間并指導(dǎo)雙聚類的挖掘.姜濤等人[104]觀察到保序子矩陣OPSM的快速檢索對(duì)生物學(xué)家尋找某種生理功能模塊起著重要作用，但現(xiàn)有大多數(shù)方法需要通過挖掘來實(shí)現(xiàn).為了避開挖掘而直接通過索引源數(shù)據(jù)來檢索OPSM，提出帶有行列表頭的前綴樹索引方法、基于行/列關(guān)鍵詞的精確/模糊查詢技術(shù)的OPSM查詢方法.姜濤等人[105]為了提升局部模式挖掘結(jié)果中檢索少量符合用戶要求的雙聚類OPSM查詢的相關(guān)性，提出了基于枚舉序列與多維索引的2種查詢方法.其利用自定義約束從提出的2種索引中搜索相關(guān)結(jié)果.在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明：與蠻力搜索方法相比，基于枚舉序列與多維索引的2種查詢方法能夠更準(zhǔn)確、更有效地檢索OPSM.姜濤等人[106]為進(jìn)一步減少文獻(xiàn)[105]的索引大小，提出了基于數(shù)字簽名與Trie的OPSM索引與查詢方法.實(shí)驗(yàn)結(jié)果證明了所提出查詢方法的有效性與準(zhǔn)確性.姜濤等人[107]設(shè)計(jì)和實(shí)現(xiàn)了基于蝶形網(wǎng)絡(luò)和帶有行與列表頭的前綴樹索引的OPSM挖掘、索引與檢索工具(order-preserving submatrix mining, indexing and search tool, OMEGA).姜濤等人[108]對(duì)文獻(xiàn)[104]的工作進(jìn)行了擴(kuò)展，將原來的正相關(guān)模式的搜索增加為正相關(guān)、負(fù)相關(guān)、時(shí)滯正負(fù)相關(guān)等模式的查詢.其他相關(guān)工具的總結(jié)如表8所示：

Table 8 Systems or Tools of Biclusters Based on Query表8 基于查詢的雙聚類系統(tǒng)或工具

① http://www.bioinf.jku.at/software/fabia/fabia.html

② http://www.cse.buffalo.edu//DBGROUP/bioinformatics/GPX/

③ http://homes.esat.kuleuven.be/tdhollan/Supplementary_Information_Dhollander_2007/index.html, http://homes.esat.kuleuven.be/?kmarchal

④ http://faris-alqadah.heroku.com

⑤ https://sites.google.com/site/jiangtaonwpu/

3.4 約束型雙聚類

目前，約束型雙聚類的相關(guān)研究相對(duì)較少，它是一種對(duì)基因表達(dá)數(shù)據(jù)挖掘與分析的新方法.Pensa等人[109-110]提出一種從局部到整體的方法來建立間隔約束的二分分區(qū)，該方法是通過擴(kuò)展從0/1數(shù)據(jù)集中提取出來的一些局部模式來實(shí)現(xiàn)的.基本思想是將間隔約束轉(zhuǎn)換成一個(gè)放松的局部模式，接著利用K均值算法來獲得一個(gè)局部模式的分區(qū)，最后對(duì)此分區(qū)做后續(xù)處理來確定數(shù)據(jù)之上的協(xié)同聚類結(jié)構(gòu).隨后，Pensa等人[111]對(duì)文獻(xiàn)[109-110]進(jìn)行了擴(kuò)展，主要的不同點(diǎn)有：1)作者同時(shí)在行列之上應(yīng)用目標(biāo)函數(shù)來評(píng)價(jià)雙聚類的好壞；2)文獻(xiàn)[111]將文獻(xiàn)[109-110]中的數(shù)據(jù)從0/1矩陣擴(kuò)展到了實(shí)數(shù)數(shù)據(jù)；3)提升must-link與cannot-link這2類約束在行列之上的處理性能.Tseng等人[112]發(fā)現(xiàn)現(xiàn)有約束聚類方法大多是類K均值方法，且只能解決基于距離的相似度問題，為此提出一種約束層次聚類方法，并將其命名為相關(guān)約束的完整鏈接(correlational-constrained complete link, C-CCL).該方法利用相關(guān)系數(shù)作為測(cè)度，相比現(xiàn)有算法具有較好的性能.

3.5 存在的問題

當(dāng)前關(guān)于基因表達(dá)數(shù)據(jù)挖掘與管理的研究取得了一定的進(jìn)展，但是還存在著一些問題.例如，基因表達(dá)數(shù)據(jù)中局部模式的快速挖掘、基因表達(dá)數(shù)據(jù)中局部模式的索引、基因表達(dá)數(shù)據(jù)中基于關(guān)鍵詞的局部模式查詢、基因表達(dá)數(shù)據(jù)中局部模式的約束型查詢.具體問題有4點(diǎn)：

1) 隨著數(shù)據(jù)密集型計(jì)算平臺(tái)的出現(xiàn)，如何在分布式并行環(huán)境下快速挖掘基因表達(dá)數(shù)據(jù)中的局部模式.

2) 隨著高通量測(cè)序技術(shù)的飛速發(fā)展，大量的基因表達(dá)數(shù)據(jù)以前所未有的速度增長(zhǎng).同時(shí)，由于基因表達(dá)數(shù)據(jù)分析代價(jià)不斷減小，大規(guī)模的局部模式分析結(jié)果也得到累積.如何為這2種數(shù)據(jù)集設(shè)計(jì)一個(gè)通用的索引結(jié)構(gòu)和查詢方法顯得尤為迫切.據(jù)我們所知，從基因表達(dá)數(shù)據(jù)中挖掘局部模式的耗時(shí)遠(yuǎn)遠(yuǎn)超過從局部模式數(shù)據(jù)中搜索局部模式，但是，局部模式的數(shù)據(jù)量遠(yuǎn)遠(yuǎn)大于基因表達(dá)數(shù)據(jù).如何保證索引能容納于內(nèi)存中、索引更新更高效、基于索引的查詢更快且具有可擴(kuò)展性是一項(xiàng)具有挑戰(zhàn)性的工作.

3) 雖然局部模式的檢索可以通過關(guān)鍵詞的查詢來處理，但是查詢結(jié)果大的相關(guān)性很難滿足.

4) 假如問題1～3都可以圓滿解決，如何設(shè)計(jì)同時(shí)滿足索引數(shù)據(jù)量小且查詢性能又較高的方法有待研究.

4 未來研究方向

盡管現(xiàn)有方法實(shí)現(xiàn)了一些研究突破，但是在一些方面仍需要進(jìn)一步思考和拓展.筆者認(rèn)為在局部模式的挖掘、索引與檢索領(lǐng)域，還有如下3個(gè)方面可以進(jìn)行嘗試與探索：

1) 現(xiàn)有的局部模式挖掘大多數(shù)是針對(duì)單機(jī)而設(shè)計(jì)的，且不管從挖掘結(jié)果的數(shù)量還是效率上都很難令人滿意.目前云計(jì)算等分布式并行計(jì)算環(huán)境正在如火如荼的發(fā)展中，為基因表達(dá)數(shù)據(jù)等生物信息挖掘提供了有利的平臺(tái).然而，現(xiàn)有方法還不能簡(jiǎn)單地移植到新的環(huán)境中，亟待設(shè)計(jì)與實(shí)現(xiàn)新的計(jì)算與通信框架來提高計(jì)算的效率與保證計(jì)算結(jié)果的完整性.

2) 現(xiàn)有的大多數(shù)方法關(guān)注的是局部模式的批量挖掘，且挖掘出的大量結(jié)果很難得到有效的利用.研究與實(shí)踐表明，基于索引與查詢等數(shù)據(jù)管理和檢索技術(shù)能夠從海量數(shù)據(jù)中有效地提取想要的信息，且能在很大程度上提高結(jié)果的利用效率以及檢索結(jié)果的相關(guān)度.

3) 現(xiàn)有局部模式挖掘方法沒有做到領(lǐng)域知識(shí)的抽取與有效利用.文獻(xiàn)中存在大量來自不同專家的領(lǐng)域知識(shí)，其若被有效地提取出來，將從本質(zhì)上改變?nèi)狈ο闰?yàn)知識(shí)的現(xiàn)狀.另外，現(xiàn)有的爬蟲技術(shù)與知識(shí)抽取方法并不一定適用于本研究，所以還需要進(jìn)一步的優(yōu)化與擴(kuò)充.從分析中可以看出，有必要研究新的數(shù)據(jù)挖掘與管理方法來對(duì)基因之間相互作用的情況進(jìn)行研究，進(jìn)一步為生物醫(yī)學(xué)探索提供關(guān)鍵的引導(dǎo)性知識(shí).

隨著高通量測(cè)序技術(shù)的大規(guī)模應(yīng)用推廣、大數(shù)據(jù)應(yīng)用的興起和數(shù)據(jù)密集型等大規(guī)模計(jì)算平臺(tái)的普及，局部模式的挖掘、索引與查詢方法的研究必將得到更為廣泛的關(guān)注，同時(shí)也將面臨新的未知挑戰(zhàn)，需要科研工作者結(jié)合業(yè)界的動(dòng)態(tài)不斷地探索與解決.

5 總 結(jié)

基因微陣列技術(shù)使得基因表達(dá)數(shù)據(jù)的產(chǎn)生速度加快和數(shù)量的增大.雙聚類技術(shù)又將挖掘結(jié)果的類型從單向聚類的整體模式轉(zhuǎn)換為局部模式.因?yàn)殡p聚類在基因表達(dá)數(shù)據(jù)分析方面的成果同樣可以移植或轉(zhuǎn)化到商品推薦、直銷與選舉分析等領(lǐng)域，所以很有必要對(duì)現(xiàn)階段雙聚類的研究成果加以整理與總結(jié).本文從局部模式定義、局部模式類型與標(biāo)準(zhǔn)、研究現(xiàn)狀、未來的研究方向等方面梳理了基因表達(dá)數(shù)據(jù)中的局部模式挖掘技術(shù).同時(shí)指出雖然局部模式的研究已經(jīng)開展了很多年，也涌現(xiàn)出大量的重要研究成果，但是隨著大數(shù)據(jù)技術(shù)與系統(tǒng)的產(chǎn)生與發(fā)展，現(xiàn)有局部模式挖掘方法并不一定完全適用于新形勢(shì)與新情況.本文針對(duì)局部模式挖掘的綜述研究希望能夠?yàn)殛P(guān)注大數(shù)據(jù)中局部模式挖掘理論與應(yīng)用的研究者與實(shí)踐領(lǐng)域?qū)＜姨峁┙梃b.