基因表達數據中的局部模式挖掘研究綜述

姜 濤 李戰懷

1(河南財經政法大學計算機與信息工程學院 鄭州 450046) 2(西北工業大學計算機學院 西安 710129) (jiangtaoxxx@126.com)

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

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

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

1 問題定義

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

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

Table 1 Example of Gene Expression Data Matrix表1 基因表達數據矩陣舉例

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

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

近年來出現了一種稱為雙聚類[1]的方法，其將標準聚類(單向聚類)算法的挖掘結果從整體模式轉變為局部模式.在雙聚類中，部分行在部分列下具有相同的行為或趨勢，或者部分列在部分行下展現出相似的行為或趨勢如圖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中一個|I|×|J|的子矩陣，有時也將其稱為保序子矩陣(order-preserving submatrix， OPSM)[4].

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

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.

標準聚類(單向聚類)與雙聚類(雙向聚類)的差異主要體現在3個方面：

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

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

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

單向聚類與雙聚類的優劣主要體現在3個方面：

1) 雙聚類利用了聚類的二元性.單向聚類從行或列中的一個維度進行數據的劃分，但不能同時從行與列這2個維度進行數據的劃分；而雙聚類可以同時從行與列這2個維度對數據進行劃分.這樣，雙聚類解決了摘要中指出的“標準聚類只能發現少量的知識的問題”.

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

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

2 局部模式類型與標準

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

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

恒值雙聚類和相干雙聚類各自的特點如表3所示.

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

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

根據雙聚類間的關系，一組雙聚類可分為如下類型[5]，如圖3所示.

1) 單獨的雙聚類，如圖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 研究現狀

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

近年來，基因表達數據挖掘得到生物醫學與學術界的重點關注，取得一定的研究成果[5,15-18].本節主要從基于定量測度的雙聚類、基于定性測度的雙聚類、基于查詢的雙聚類和約束型雙聚類等方面對基因表達數據中局部模式的挖掘方法的研究現狀進行梳理和介紹.

3.1 基于定量測度的雙聚類

主要從噪聲與缺失值問題、雙聚類算法、雙聚類理論研究、現有方法的比較、相關系統與工具等方面介紹基于定量測度的雙聚類.

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

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

Table 4 Quantitative Measures of Biclusters表4 雙聚類的定量測度

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

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

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

Table 5 Systems or Tools of Biclusters Based on Quantitative Measures表5 基于定量測度的雙聚類系統或工具

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 基于定性測度的雙聚類

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

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

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

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

Table 6 Qualitative Measures of Biclusters表6 雙聚類的定性測度

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

4) 對現有算法進行全方位比較的工作.文獻[5,15-18]從相關算法所挖掘模式的生物學意義及其難點、各種算法的優缺點、相關應用等方面進行了詳細的歸納、比較、總結，同時對進一步可以研究的方向進行了展望.

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

Table 7 Systems or Tools of Biclusters Based on Qualitative Measures表7 基于定性測度的雙聚類系統或工具

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

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

① 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 約束型雙聚類

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

3.5 存在的問題

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

1) 隨著數據密集型計算平臺的出現，如何在分布式并行環境下快速挖掘基因表達數據中的局部模式.

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

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

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

4 未來研究方向

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

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

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

3) 現有局部模式挖掘方法沒有做到領域知識的抽取與有效利用.文獻中存在大量來自不同專家的領域知識，其若被有效地提取出來，將從本質上改變缺乏先驗知識的現狀.另外，現有的爬蟲技術與知識抽取方法并不一定適用于本研究，所以還需要進一步的優化與擴充.從分析中可以看出，有必要研究新的數據挖掘與管理方法來對基因之間相互作用的情況進行研究，進一步為生物醫學探索提供關鍵的引導性知識.

隨著高通量測序技術的大規模應用推廣、大數據應用的興起和數據密集型等大規模計算平臺的普及，局部模式的挖掘、索引與查詢方法的研究必將得到更為廣泛的關注，同時也將面臨新的未知挑戰，需要科研工作者結合業界的動態不斷地探索與解決.

5 總 結

基因微陣列技術使得基因表達數據的產生速度加快和數量的增大.雙聚類技術又將挖掘結果的類型從單向聚類的整體模式轉換為局部模式.因為雙聚類在基因表達數據分析方面的成果同樣可以移植或轉化到商品推薦、直銷與選舉分析等領域，所以很有必要對現階段雙聚類的研究成果加以整理與總結.本文從局部模式定義、局部模式類型與標準、研究現狀、未來的研究方向等方面梳理了基因表達數據中的局部模式挖掘技術.同時指出雖然局部模式的研究已經開展了很多年，也涌現出大量的重要研究成果，但是隨著大數據技術與系統的產生與發展，現有局部模式挖掘方法并不一定完全適用于新形勢與新情況.本文針對局部模式挖掘的綜述研究希望能夠為關注大數據中局部模式挖掘理論與應用的研究者與實踐領域專家提供借鑒.