基于Charm算法挖掘基因表達(dá)保序子序列

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

（湖南理工學(xué)院信息科學(xué)與工程學(xué)院，岳陽(yáng) 414006）

0 引言

誕生于上世紀(jì)90 年代的分子生物學(xué)微陣列實(shí)驗(yàn)技術(shù)，通過(guò)生物芯片同時(shí)測(cè)定成千上萬(wàn)基因在不同實(shí)驗(yàn)條件下的表達(dá)量，產(chǎn)生了海量的基因表達(dá)數(shù)據(jù)［1］。挖掘基因表達(dá)數(shù)據(jù)中基因活動(dòng)模式信息，在生物醫(yī)藥等領(lǐng)域有廣泛用途。聚類(lèi)是一種重要的無(wú)監(jiān)督機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘技術(shù)，基因表達(dá)數(shù)據(jù)傳統(tǒng)聚類(lèi)僅在基因或?qū)嶒?yàn)條件單一方向上聚類(lèi)。

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

基因表達(dá)數(shù)據(jù)雙聚類(lèi)主要有基于定量測(cè)度和基于定性測(cè)度的方法。Cheng 等［2］引入元素殘差與子矩陣均方殘差（mean square residue，MSR）的概念，以MSR 為評(píng)價(jià)函數(shù)貪婪求解約束優(yōu)化問(wèn)題，這種CC 算法是典型的基于定量測(cè)度的雙聚類(lèi)方法。

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

本文提出基于Charm［7］的基因表達(dá)數(shù)據(jù)保序子序列挖掘算法Charm_Seq。Charm 是離線挖掘頻繁閉合項(xiàng)集的最高效算法［8］。Charm_Seq 將Charm由頻繁閉合項(xiàng)集挖掘改造為頻繁閉合序列挖掘，實(shí)驗(yàn)驗(yàn)證了算法的有效性。

1 相關(guān)工作

1.1 基因表達(dá)數(shù)據(jù)保序子序列

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

表1 基因表達(dá)數(shù)據(jù)序列示例

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

圖1 酵母菌兩個(gè)雙聚類(lèi)模式示例

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

1.2 頻繁項(xiàng)集與Charm算法

項(xiàng)集挖掘以事務(wù)型數(shù)據(jù)為挖掘?qū)ο螅菙?shù)據(jù)挖掘領(lǐng)域很活躍的研究方向。Charm算法挖掘事務(wù)型數(shù)據(jù)的頻繁閉合項(xiàng)集，是最有效的離線頻繁項(xiàng)集挖掘算法。

定義1事務(wù)型數(shù)據(jù)。事務(wù)型數(shù)據(jù)是由事務(wù)組成的集合，每個(gè)事務(wù)是項(xiàng)的集合，稱為事務(wù)項(xiàng)集。設(shè)事務(wù)數(shù)據(jù)的屬性集A={a1,a2,…,an}，項(xiàng)為屬性的整型取值。每個(gè)屬性在一個(gè)事務(wù)中最多一個(gè)項(xiàng)，因此，一個(gè)事務(wù)項(xiàng)集的長(zhǎng)度不大于屬性集長(zhǎng)度。

定義2頻繁項(xiàng)集。一個(gè)項(xiàng)集X在事務(wù)型數(shù)據(jù)的所有事務(wù)中出現(xiàn)的次數(shù)稱為項(xiàng)集的支持度σ（X）。假設(shè)事務(wù)數(shù)據(jù)集的最小支持度閾值為min_sup，如果σ（X）≥min_sup，則稱項(xiàng)集X為頻繁項(xiàng)集。

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

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

Charm 的數(shù)據(jù)結(jié)構(gòu)是一種Itemset-Tidse（tIT）前綴搜索樹(shù)。樹(shù)中每個(gè)節(jié)點(diǎn)為IT 對(duì)，頻繁閉合項(xiàng)集為ITSearchTree 的葉子節(jié)點(diǎn)。該算法首先掃描事務(wù)數(shù)據(jù)庫(kù)得到頻繁項(xiàng)組成的集合I，然后對(duì)每個(gè)頻繁項(xiàng)Xi∈I的節(jié)點(diǎn)Pi向下深度擴(kuò)展。

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

與Charm 挖掘頻繁閉合項(xiàng)集不同，保序子序列OPSS 是挖掘頻繁閉合序列，即保序子序列。挖掘頻繁閉合項(xiàng)集與挖掘頻繁閉合序列的區(qū)別如下：

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

（2）頻繁閉合項(xiàng)集搜索樹(shù)下層節(jié)點(diǎn)由當(dāng)前節(jié)點(diǎn)與兄弟節(jié)點(diǎn)連接生成，而頻繁閉合序列增長(zhǎng)由當(dāng)前序列與長(zhǎng)度為2頻繁原子序列連接實(shí)現(xiàn)；

（3）長(zhǎng)度為2 頻繁序列是基本的原子序列，也是所有序列增長(zhǎng)的連接對(duì)象。

然而，Charm有高效的Itemset-Tidset前綴搜索樹(shù)數(shù)據(jù)結(jié)構(gòu)，這是Apriori 等沒(méi)有的。Charm_Seq 通過(guò)改造Charm 算法實(shí)現(xiàn)基因表達(dá)數(shù)據(jù)頻繁閉合序列挖掘。

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

（1）每個(gè)基因的所有表達(dá)值按大小排序；

（2）各個(gè)基因表達(dá)值分別替換為相應(yīng)列標(biāo)簽；

例如表1數(shù)據(jù)，經(jīng)步驟（1）和（2）處理后將變成如表2所示的基因表達(dá)列序列。

表2 基因表達(dá)列序列

表3 實(shí)驗(yàn)相關(guān)的七個(gè)數(shù)據(jù)集參數(shù)

（3）挖掘列標(biāo)簽序列集的頻繁閉合序列。

為了挖掘表2 中g(shù)1～g6的頻繁閉合序列，可以改造Charm 算法為Charm_Seq算法，把挖掘目標(biāo)由頻繁閉合項(xiàng)集轉(zhuǎn)變?yōu)轭l繁閉合序列。在Charm_Seq 算法中，設(shè)［P］表示以P為父節(jié)點(diǎn)的所有子節(jié)點(diǎn)，Pi∈［P］，則Pi向下深度擴(kuò)展即是［Pi］不斷取代［P］的循環(huán)過(guò)程。Charm_Seq 偽代碼如算法1所示。

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

輸入：基因表達(dá)數(shù)據(jù)矩陣A，最小支持度閾值min_sup

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

以表2 中的｛g1，g2，g3，g4，g5，g6｝六個(gè)基因?yàn)槔?，圖2 說(shuō)明Charm_Seq 算法挖掘列標(biāo)簽頻繁閉合序列的過(guò)程。

圖2 g1～g6的列標(biāo)簽子序列×Gidset搜索樹(shù)構(gòu)建過(guò)程

3 實(shí)驗(yàn)結(jié)果與分析

本文使用GEO 微陣列基因表達(dá)數(shù)據(jù)集、基于基因表達(dá)數(shù)據(jù)的腫瘤或非腫瘤分類(lèi)數(shù)據(jù)集，以及人工數(shù)據(jù)集對(duì)算法的性能進(jìn)行評(píng)價(jià)。比較算法包括Charm_Seq、OPSS、CC、Charm、Apriori等。算法用Java 語(yǔ)言實(shí)現(xiàn)。實(shí)驗(yàn)在2.60 GHz、Intel（R）Core（TM）i7-6700HQ CPU、內(nèi)存16 GB、操作系統(tǒng)Windows 10的計(jì)算機(jī)上進(jìn)行。

3.1 數(shù)據(jù)集

GDS2267 微陣列基因表達(dá)數(shù)據(jù)集來(lái)自GEO網(wǎng)站：http://www.ncbi.nlm.nih.gov/geo，是GEO公共資源網(wǎng)上關(guān)于酵母菌（Saccharomyces cerevisiae）微陣列基因表達(dá)數(shù)據(jù)，數(shù)據(jù)集名稱是Metabolic cycle:time course。該數(shù)據(jù)集以12～25 分鐘的間隔對(duì)營(yíng)養(yǎng)有限的連續(xù)培養(yǎng)細(xì)胞進(jìn)行三個(gè)周期的分析。在這種條件下，生長(zhǎng)的細(xì)胞以呼吸爆發(fā)的形式表現(xiàn)出強(qiáng)健的周期性。數(shù)據(jù)集對(duì)應(yīng)實(shí)驗(yàn)的結(jié)果提供了對(duì)控制代謝振蕩的分子機(jī)制的洞察。

四個(gè)基準(zhǔn)數(shù)據(jù)集leukemia、colon-cancer、breast-cancer、unbalanced 是基于基因表達(dá)數(shù)據(jù)的腫瘤或非腫瘤分類(lèi)數(shù)據(jù)集。其中，leukemia和colon-cancer 可從網(wǎng)站下載獲得：http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/。breastcancer和unbalanced 則是Weka 數(shù)據(jù)分析工具的兩個(gè)自帶數(shù)據(jù)集。

T10I4D100K 和T40I10D100K 是兩個(gè)人工產(chǎn)生項(xiàng)集模式的事務(wù)數(shù)據(jù)集，使用Zaki’s IBM Datagen software 標(biāo)準(zhǔn)符號(hào)。該人工數(shù)據(jù)集句法規(guī)則為T(mén)xIyDz［Pu］［Cv］，其中x是平均事務(wù)長(zhǎng)度，y為項(xiàng)集大?。▎挝粸閗），z表示所產(chǎn)生事務(wù)的數(shù)量（單位為k）。

3.2 算法性能分析

3.2.1 Charm挖掘頻繁閉合項(xiàng)集

實(shí)驗(yàn)以人工事務(wù)數(shù)據(jù)集T10I4D100K（T10）和T40I10D100K（T40）為對(duì)象，說(shuō)明Charm 挖掘頻繁閉合項(xiàng)集FCIs的有效性和高效性。

（1）模式挖掘頻繁閉合項(xiàng)集數(shù)與長(zhǎng)度分布。

T10I4D100K 和 T40I10D100K 數(shù)據(jù)集的Charm算法模式挖掘結(jié)果如表4所示。

表4 模式挖掘結(jié)果

（2）時(shí)間性能。

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

圖3 T40I10D100K上時(shí)間性能對(duì)比

圖4 T10I4D100K上時(shí)間性能對(duì)比

Charm_Seq 和Charm 算法的數(shù)據(jù)結(jié)構(gòu)相同，挖掘目標(biāo)的改動(dòng)并不會(huì)影響算法的時(shí)間性能。因此，Charm_Seq和Charm算法一樣具有高效特性。

3.2.2 Charm_Seq算法性能分析

（1）擴(kuò)展性能。

Charm_Seq算法行和列的擴(kuò)展性能如圖5。

圖5 Charm_Seq算法行和列的擴(kuò)展性能

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

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

表5 顯示Charm_Seq 算法從酵母GDS2267 數(shù)據(jù)集挖掘的五個(gè)雙聚類(lèi)相關(guān)信息。

表5 算法挖掘的酵母五個(gè)聚類(lèi)示例

圖6 進(jìn)一步比較Charm_Seq、CC、OPSS 算法的GO 功能類(lèi)別富集程度，使用的數(shù)據(jù)集為GDS2267。

圖6 在GO功能方面比較雙聚類(lèi)算法

從圖6 可以看出，在GDS2267 數(shù)據(jù)集上，Charm_Seq 雙聚類(lèi)算法的平均GO 功能富集屬性數(shù)與OPSS 大致相當(dāng)，比定量測(cè)度雙聚類(lèi)方法CC 高，說(shuō)明Charm_Seq 所得雙聚類(lèi)有較好的生物學(xué)意義。

4 結(jié)語(yǔ)

與傳統(tǒng)的相似測(cè)度基于歐氏距離或余弦距離不同，保序子序列基因相似標(biāo)準(zhǔn)是表達(dá)水平在相同條件下同升同降。針對(duì)NP-難的OPSS 模型不適用于大規(guī)模基因表達(dá)數(shù)據(jù)分析，本文利用Charm 的高效Itemset-Tidset 前綴搜索樹(shù)用于頻繁閉合序列挖掘，為求解OPSS 問(wèn)題提供了一種新的嘗試。