基于Charm算法挖掘基因表達保序子序列

廖旭紅，江 華，廖 莎，李志杰

（湖南理工學院信息科學與工程學院，岳陽 414006）

0 引言

誕生于上世紀90 年代的分子生物學微陣列實驗技術，通過生物芯片同時測定成千上萬基因在不同實驗條件下的表達量，產生了海量的基因表達數據［1］。挖掘基因表達數據中基因活動模式信息，在生物醫藥等領域有廣泛用途。聚類是一種重要的無監督機器學習和數據挖掘技術，基因表達數據傳統聚類僅在基因或實驗條件單一方向上聚類。

然而，一個生物基因不可能在所有的實驗條件下展示共表達特性，也不可能在所有的實驗條件下展示相同的水平，卻常常參與多種遺傳通路。這些特性意味著基因表達數據存在許多潛在的局部模式，只有對基因（行）和實驗條件（列）兩個方向同時聚類，才可能挖掘出大量有價值的局部模式。

基因表達數據雙聚類主要有基于定量測度和基于定性測度的方法。Cheng 等［2］引入元素殘差與子矩陣均方殘差（mean square residue，MSR）的概念，以MSR 為評價函數貪婪求解約束優化問題，這種CC 算法是典型的基于定量測度的雙聚類方法。

多數雙聚類方法通過不同基因表達樣本相似性度量發現局部模式。Wang 等［3］為了指導相似模式聚類，定義了一種新的最近鄰測度方法。Liu 等［4］以基因表達值排序的順序而不是歐氏距離作為判斷兩個基因相似的標準，提出一種靈活有效的保序雙聚類模型。保序子序列（order-preserving subsequence，OPSS）是部分行在部分列下具有相同的趨勢，實質上是一種排序后的保序子序列挖掘問題。Ben-Dor 等［5-6］證明OPSS是NP難題。

本文提出基于Charm［7］的基因表達數據保序子序列挖掘算法Charm_Seq。Charm 是離線挖掘頻繁閉合項集的最高效算法［8］。Charm_Seq 將Charm由頻繁閉合項集挖掘改造為頻繁閉合序列挖掘，實驗驗證了算法的有效性。

1 相關工作

1.1 基因表達數據保序子序列

基因表達數據可表示為一個n×m的數值矩陣A，其中元素aij表示第i個基因（g）i在第j個實驗條件（t）j下的表達實數值。A可形式化表示為A=(G,C)，其中，G={g1,g2,…,gi,gi+1,…,gn}表示基因行集合，C={c1,c2,…,cj,cj+1,…,cm}表示實驗條件列集合。表1是一個基因表達數據序列示例。

表1 基因表達數據序列示例

在DNA 微陣列分析中，密切相關的基因的表達值可能會隨一組實驗樣本相應地同步上升和下降。盡管這些基因的強度表達水平可能不接近，但它們所呈現的模式卻非常相似，這種模式即是雙聚類局部模式。圖1展示從GDS2267酵母菌數據集挖掘的兩個局部模式示例，每個模式在條件列集上具有一致遞減趨勢。

圖1 酵母菌兩個雙聚類模式示例

假設I?G，J?C，AIJ=(I,J)表示部分行I在部分列J下具有相似行為或趨勢，AIJ也稱之為保序子序列。OPSS 是矩陣A的一種雙聚類局部模式，挖掘OPSS 是要從給定的基因表達序列A中發現具有相似行為或趨勢的子序列AIJ=(I,J)的集合。

1.2 頻繁項集與Charm算法

項集挖掘以事務型數據為挖掘對象，是數據挖掘領域很活躍的研究方向。Charm算法挖掘事務型數據的頻繁閉合項集，是最有效的離線頻繁項集挖掘算法。

定義1事務型數據。事務型數據是由事務組成的集合，每個事務是項的集合，稱為事務項集。設事務數據的屬性集A={a1,a2,…,an}，項為屬性的整型取值。每個屬性在一個事務中最多一個項，因此，一個事務項集的長度不大于屬性集長度。

定義2頻繁項集。一個項集X在事務型數據的所有事務中出現的次數稱為項集的支持度σ（X）。假設事務數據集的最小支持度閾值為min_sup，如果σ（X）≥min_sup，則稱項集X為頻繁項集。

定義3頻繁閉合項集。假設X是頻繁項集，Y表示項集X的任一超項集。如果?Y，σ（Y）<σ（X）均成立，則稱X為頻繁閉合項集。

離線和在線頻繁模式挖掘典型算法［9-10］有Apriori、Charm、IncMine、Moment 等。其中Charm是頻繁閉合項集離線挖掘最有效算法，其優越性能主要通過構建<項集×事務集>鍵值對搜索樹，并且鍵值對表示采用Bitset 編碼技術。另外，算法采用差集技術減少中間計算節點的內存占用空間，使用基于hash 的方法加速清除非閉合的項集等。實驗顯示［9］，使用Charm 作為批處理挖掘器的IncMine 算法，比Moment 快幾個數據級，且使用更少的內存。

Charm 的數據結構是一種Itemset-Tidse（tIT）前綴搜索樹。樹中每個節點為IT 對，頻繁閉合項集為ITSearchTree 的葉子節點。該算法首先掃描事務數據庫得到頻繁項組成的集合I，然后對每個頻繁項Xi∈I的節點Pi向下深度擴展。

2 基于Charm的頻繁閉合序列挖掘

與Charm 挖掘頻繁閉合項集不同，保序子序列OPSS 是挖掘頻繁閉合序列，即保序子序列。挖掘頻繁閉合項集與挖掘頻繁閉合序列的區別如下：

（1）頻繁閉合項集首先搜索頻繁項，而頻繁閉合序列挖掘首先搜索的是長度為2 頻繁原子序列；

（2）頻繁閉合項集搜索樹下層節點由當前節點與兄弟節點連接生成，而頻繁閉合序列增長由當前序列與長度為2頻繁原子序列連接實現；

（3）長度為2 頻繁序列是基本的原子序列，也是所有序列增長的連接對象。

然而，Charm有高效的Itemset-Tidset前綴搜索樹數據結構，這是Apriori 等沒有的。Charm_Seq 通過改造Charm 算法實現基因表達數據頻繁閉合序列挖掘。

基于Charm 的保序子序列方法挖掘頻繁閉合序列過程有如下三個步驟：

（1）每個基因的所有表達值按大小排序；

（2）各個基因表達值分別替換為相應列標簽；

例如表1數據，經步驟（1）和（2）處理后將變成如表2所示的基因表達列序列。

表2 基因表達列序列

表3 實驗相關的七個數據集參數

（3）挖掘列標簽序列集的頻繁閉合序列。

為了挖掘表2 中g1～g6的頻繁閉合序列，可以改造Charm 算法為Charm_Seq算法，把挖掘目標由頻繁閉合項集轉變為頻繁閉合序列。在Charm_Seq 算法中，設［P］表示以P為父節點的所有子節點，Pi∈［P］，則Pi向下深度擴展即是［Pi］不斷取代［P］的循環過程。Charm_Seq 偽代碼如算法1所示。

算法1Charm_Seq（A,min_sup,C=?）

輸入：基因表達數據矩陣A，最小支持度閾值min_sup

輸出：頻繁閉合序列集合C

以表2 中的｛g1，g2，g3，g4，g5，g6｝六個基因為例，圖2 說明Charm_Seq 算法挖掘列標簽頻繁閉合序列的過程。

圖2 g1～g6的列標簽子序列×Gidset搜索樹構建過程

3 實驗結果與分析

本文使用GEO 微陣列基因表達數據集、基于基因表達數據的腫瘤或非腫瘤分類數據集，以及人工數據集對算法的性能進行評價。比較算法包括Charm_Seq、OPSS、CC、Charm、Apriori等。算法用Java 語言實現。實驗在2.60 GHz、Intel（R）Core（TM）i7-6700HQ CPU、內存16 GB、操作系統Windows 10的計算機上進行。

3.1 數據集

GDS2267 微陣列基因表達數據集來自GEO網站：http://www.ncbi.nlm.nih.gov/geo，是GEO公共資源網上關于酵母菌（Saccharomyces cerevisiae）微陣列基因表達數據，數據集名稱是Metabolic cycle:time course。該數據集以12～25 分鐘的間隔對營養有限的連續培養細胞進行三個周期的分析。在這種條件下，生長的細胞以呼吸爆發的形式表現出強健的周期性。數據集對應實驗的結果提供了對控制代謝振蕩的分子機制的洞察。

四個基準數據集leukemia、colon-cancer、breast-cancer、unbalanced 是基于基因表達數據的腫瘤或非腫瘤分類數據集。其中，leukemia和colon-cancer 可從網站下載獲得：http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/。breastcancer和unbalanced 則是Weka 數據分析工具的兩個自帶數據集。

T10I4D100K 和T40I10D100K 是兩個人工產生項集模式的事務數據集，使用Zaki’s IBM Datagen software 標準符號。該人工數據集句法規則為TxIyDz［Pu］［Cv］，其中x是平均事務長度，y為項集大小（單位為k），z表示所產生事務的數量（單位為k）。

3.2 算法性能分析

3.2.1 Charm挖掘頻繁閉合項集

實驗以人工事務數據集T10I4D100K（T10）和T40I10D100K（T40）為對象，說明Charm 挖掘頻繁閉合項集FCIs的有效性和高效性。

（1）模式挖掘頻繁閉合項集數與長度分布。

T10I4D100K 和 T40I10D100K 數據集的Charm算法模式挖掘結果如表4所示。

表4 模式挖掘結果

（2）時間性能。

圖3 和圖4 是Charm 和Apriori 算法時間性能對比，它們都是典型的離線挖掘頻繁模式算法。實驗充分顯示了Charm算法的高效性。

圖3 T40I10D100K上時間性能對比

圖4 T10I4D100K上時間性能對比

Charm_Seq 和Charm 算法的數據結構相同，挖掘目標的改動并不會影響算法的時間性能。因此，Charm_Seq和Charm算法一樣具有高效特性。

3.2.2 Charm_Seq算法性能分析

（1）擴展性能。

Charm_Seq算法行和列的擴展性能如圖5。

圖5 Charm_Seq算法行和列的擴展性能

圖5（a）、（b）、（c）、（d）分別是Charm_Seq 算法在leukemia、colon-cancer、breast-cancer、unbalanced數據集上關于行和列的擴展性能圖。從圖5顯示的趨勢看，行擴展曲線與列擴展曲線有一定的對稱性。

（2）保序子序列挖掘示例。

表5 顯示Charm_Seq 算法從酵母GDS2267 數據集挖掘的五個雙聚類相關信息。

表5 算法挖掘的酵母五個聚類示例

圖6 進一步比較Charm_Seq、CC、OPSS 算法的GO 功能類別富集程度，使用的數據集為GDS2267。

圖6 在GO功能方面比較雙聚類算法

從圖6 可以看出，在GDS2267 數據集上，Charm_Seq 雙聚類算法的平均GO 功能富集屬性數與OPSS 大致相當，比定量測度雙聚類方法CC 高，說明Charm_Seq 所得雙聚類有較好的生物學意義。

4 結語

與傳統的相似測度基于歐氏距離或余弦距離不同，保序子序列基因相似標準是表達水平在相同條件下同升同降。針對NP-難的OPSS 模型不適用于大規模基因表達數據分析，本文利用Charm 的高效Itemset-Tidset 前綴搜索樹用于頻繁閉合序列挖掘，為求解OPSS 問題提供了一種新的嘗試。