基于粗糙信息熵的基因分析與選擇研究

摘要：基于粗糙集理論中的屬性重要性與粗糙信息熵概念，定義了基因選擇度量標(biāo)準(zhǔn)，分析了基因作為條件屬性對(duì)疾病樣本分類的不確定信息在集合中的影響，提出了一種RMSME算法。該算法依據(jù)預(yù)先定義的基因選擇度量標(biāo)準(zhǔn)，分析了與疾病分類關(guān)聯(lián)性最大的基因，最終選擇出與疾病分類關(guān)聯(lián)最大的基因。最后在實(shí)際數(shù)據(jù)集中對(duì)算法的有效性進(jìn)行了實(shí)驗(yàn)仿真。

關(guān)鍵詞：粗糙集； 生物信息學(xué)； 基因表達(dá)； 信息熵； 數(shù)據(jù)挖掘

中圖分類號(hào)：TP18文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2008)06－1713－04

隨著人類基因組計(jì)劃的完成，新的基因組研究思路是基于已獲得生物序列結(jié)構(gòu)和功能特性的知識(shí)，利用計(jì)算機(jī)數(shù)據(jù)處理能力來(lái)模擬和分析、預(yù)測(cè)新的信息或提供相關(guān)的輔助信息。在生物信息學(xué)領(lǐng)域中，通過(guò)高通量的基因表達(dá)分析平臺(tái)可以在一次實(shí)驗(yàn)中同時(shí)獲得成千上萬(wàn)個(gè)基因的表達(dá)數(shù)據(jù)。因此，越來(lái)越多的科研工作者更關(guān)注于如何選用合適的理論方法對(duì)這些基因數(shù)據(jù)集進(jìn)行分析，尋求與疾病關(guān)聯(lián)的最重要的基因組。

粗糙集理論[1，2]作為一種研究現(xiàn)實(shí)中各種獲得信息的數(shù)學(xué)理論，主要是以集合的整體直接逼近的方式完成對(duì)不完整不確定信息前提下的知識(shí)推理過(guò)程。針對(duì)數(shù)據(jù)海量現(xiàn)狀也有基于粗糙集理論的知識(shí)約簡(jiǎn)研究[3]與特征選擇研究[4，5]。

本文的主要貢獻(xiàn)是針對(duì)基因數(shù)據(jù)高維度、特征屬性數(shù)量遠(yuǎn)大于樣本個(gè)數(shù)的特點(diǎn)，基于粗糙集理論提出了一種對(duì)基因數(shù)據(jù)集進(jìn)行分析的新思路，對(duì)基因研究的數(shù)據(jù)進(jìn)行了預(yù)處理。

1粗糙集理論

1．1屬性重要度與屬性依賴性

在粗糙集理論體系中，可以這樣通俗理解屬性重要度：在一個(gè)信息系統(tǒng)IS=(U，A)中，XA是一屬性子集。如果xA，在X中增加屬性x之后，信息系統(tǒng)提高了對(duì)對(duì)象進(jìn)行分辨的能力，這種能力的提高程度就是屬性重要度。提高程度越大，可以認(rèn)為x對(duì)于X越重要。

1．2粗糙信息熵

由于現(xiàn)實(shí)生活中存在著知識(shí)不確定性，需要定量地表征這些知識(shí)的不確定程度。熵的概念源于物理學(xué)，表征知識(shí)的平均信息量，它反映了在考慮多個(gè)知識(shí)時(shí)信息的不確定程度。學(xué)者Shannon在信息論中引入了信息熵的概念[7]，對(duì)不確定性知識(shí)進(jìn)行了基本度量的定義；文獻(xiàn)[8，9]對(duì)信息熵和條件熵概念進(jìn)行了介紹。

令U是論域，X1，X2，…，Xn是U的一個(gè)劃分，其上有概率分布，則稱信息源X的信息熵為

該粗糙信息熵的定義基于粗糙集理論中上下近似的概念，研究粗糙集方法與傳統(tǒng)概率統(tǒng)計(jì)方法之間的信息熵聯(lián)系，并提出滿足一定條件下的粗集信息熵與傳統(tǒng)信息熵是等價(jià)的。此方法只要通過(guò)簡(jiǎn)單的上下近似集合運(yùn)算，便可合理地選擇分支屬性節(jié)點(diǎn)以提供給決策樹。它比傳統(tǒng)的基于概率統(tǒng)計(jì)的信息熵計(jì)算方法簡(jiǎn)單。

2基因分析與選擇算法

在基因分析與選擇的前期研究中，主要應(yīng)用了統(tǒng)計(jì)和信息論等方法[12，13]?；虮磉_(dá)序列數(shù)據(jù)是研究人員主要的數(shù)據(jù)來(lái)源，它可以以矩陣的形式表現(xiàn)。其中，行是基因編號(hào)，列是實(shí)驗(yàn)樣本。一般的基因特征選擇方法可以分成兩類，即過(guò)濾和打包[14，15]。過(guò)濾類型的特征選擇方法是最基本的數(shù)據(jù)預(yù)處理和數(shù)據(jù)濾除方法，主要基于數(shù)據(jù)關(guān)聯(lián)與分類區(qū)分的特點(diǎn)。過(guò)濾類型方法可以比較容易計(jì)算和高效地運(yùn)行，并且與分類器在數(shù)據(jù)特征選擇的學(xué)習(xí)方法上沒有關(guān)聯(lián)。打包類型的特征選擇是與某種學(xué)習(xí)方法相關(guān)聯(lián)的。學(xué)習(xí)方法的預(yù)計(jì)準(zhǔn)確率可以直接判斷一個(gè)特征的效用，從而得到一個(gè)數(shù)量較小的具有較高預(yù)測(cè)率的非冗余特征子集。但打包類型方法需要較高的計(jì)算量以尋找出最優(yōu)的特征集。

在文獻(xiàn)[16]中研究者基于粗糙集理論中的屬性依賴度概念，提出了一個(gè)粗糙最大相關(guān)度—最大相互作用度（RMIMR） 算法作為訓(xùn)練分類器的前期數(shù)據(jù)集冗余處理技術(shù)。通過(guò)定義基因相關(guān)度與基因相互作用度兩個(gè)概念，以量化的方式分析了由基因與樣本構(gòu)成的信息系統(tǒng)中的冗余基因，并把約簡(jiǎn)后的數(shù)據(jù)集提供給SVM分類器和naive－Bayes分類器作為訓(xùn)練集，最后在四個(gè)不同的癌癥數(shù)據(jù)集上應(yīng)用結(jié)果驗(yàn)證了該方法的有效性。

基于上述研究成果，本文結(jié)合屬性重要度和信息熵思想，定義粗糙信息熵，提出一個(gè)RMSME算法，并以實(shí)際的數(shù)據(jù)集進(jìn)行算法的有效性驗(yàn)證。

2．1基因選擇標(biāo)準(zhǔn)

基因的分析與選擇，最基本的思想是選擇那些與疾病關(guān)聯(lián)性最大的或者對(duì)基因表達(dá)序列的基因信息量進(jìn)行排序，選擇出滿足某種疾病評(píng)判標(biāo)準(zhǔn)的基因。然而前期研究而得到的各種醫(yī)學(xué)數(shù)據(jù)中，基因往往是幾千的個(gè)數(shù)。目前基因分析與選擇的研究重點(diǎn)是如何在眾多的基因數(shù)據(jù)中去除冗余基因，只留下或選擇出與疾病分類相關(guān)性最大的基因子集。本文將粗糙集理論的屬性重要性結(jié)合信息論的條件熵，對(duì)與疾病分類相關(guān)的重要基因進(jìn)行重要性度量，約簡(jiǎn)了冗余的基因，得到了最重要的基因子集。

在以基因表達(dá)數(shù)據(jù)組成的矩陣中，計(jì)算每個(gè)基因在整個(gè)論域中的重要性，可以定量地區(qū)分出重要的基因，并進(jìn)行下一步的基因分析與研究。在粗糙集理論中，屬性重要性表征了信息系統(tǒng)中屬性與決策分類的關(guān)系，屬性的重要性越大，其與樣本分類的關(guān)系最為密切，這也是約簡(jiǎn)過(guò)程最重要的冗余屬性去除標(biāo)準(zhǔn)之一。

定義2基因表達(dá)數(shù)據(jù)包含有n個(gè)基因gene=(gene1，gene2，…，genen)，m個(gè)樣本分類的集合D=(D1，D2，…，Dm)。genei是基因集合gene中第i(i=1，2，…，n)個(gè)基因，Di是樣本分類集合D的第j(j=1，2，…，m)個(gè)分類。對(duì)于已知genei基因時(shí)樣本分類D的條件熵H(D｜gene)為

其中：P(Dj｜{genei})=｜Dj∪{genei}｜/｜{genei}｜。H(D｜gene)表征了根據(jù)基因genei可以得到樣本分類集合D的條件熵，即不確定性信息量大小。當(dāng)U/{genei}對(duì)樣本等價(jià)類劃分的集合與樣本分類中的分類D集合交集為空時(shí)，H(D｜gene)在第i個(gè)基因?yàn)闂l件屬性下的條件熵值為最小條件熵值：min H(D｜gene)=0；當(dāng)U/{genei}對(duì)樣本等價(jià)類劃分的集合為全體樣本作為集合惟一元素時(shí)，H(D｜gene)是在第i個(gè)基因的條件熵為最大條件熵值：max H(D｜gene)=｜{U}｜/｜U｜∑mj=1（｜{Um}｜/｜{U}｜) log (｜{Um}｜/｜{U}｜)。由上述粗糙條件熵最大（?。┲悼梢缘玫奖碚鲗傩詆enei與D的信息依賴性的條件熵H(D｜gene)標(biāo)準(zhǔn)化公式：

從規(guī)則化后的條件熵可知，當(dāng)HS(D｜gene)越趨近于零時(shí)，得到的不確定信息量越小，即確定的信息越大，說(shuō)明genei與D之間的信息依賴性就越強(qiáng)。

文獻(xiàn)[17]證明了現(xiàn)有的基于屬性依賴度的定義和基于信息熵的定義的不完備性，提出了一種加權(quán)平均的屬性重要度定義，并構(gòu)造了兩種啟發(fā)式算法對(duì)屬性進(jìn)行了啟發(fā)式約簡(jiǎn)。

根據(jù)上述定義與文獻(xiàn)研究?jī)?nèi)容，本文定義基因分析與選擇度量標(biāo)準(zhǔn)參數(shù)：粗糙信息熵RE（rough entropy）。該參數(shù)以系統(tǒng)中加權(quán)的相應(yīng)屬性重要度最大的基因與相應(yīng)條件熵最小的和值為衡量標(biāo)準(zhǔn)，選擇基因構(gòu)成包含r個(gè)集合元素的基因組。

定義3在以基因表達(dá)數(shù)據(jù)信息系統(tǒng)中，基因集合gene=(gene1，gene2，…，genen)(i=1，2，…，n) ，關(guān)于基因的樣本分類集合為D=(D1，D2，…，Dm)的基因粗糙信息熵為

RE(genei)=(1-α)Sgene(genei)+αHS(D｜gene)（4）

當(dāng)特征屬性個(gè)數(shù)遠(yuǎn)大于樣本個(gè)數(shù)時(shí)，由屬性重要性去衡量區(qū)分基因與樣本分類難以到達(dá)理想的目標(biāo)，而條件熵可以作為主要判斷依據(jù)，即HS(D｜gene)作為主要的判斷依據(jù)，Sgene(genei)作為輔助的判斷依據(jù)，所以可以對(duì)α取值：0.9≤α≤1。上述定義在基因表達(dá)數(shù)據(jù)眾多基因中選擇出綜合考慮屬性重要性與條件熵的基因，構(gòu)成關(guān)聯(lián)疾病的基因組。因此，在基因組n個(gè)基因中求出前r（0≤r≤n）個(gè)相對(duì)最大粗糙信息熵的基因：

{max RE(genei)，…，max RE(gener)}（5）

即在n個(gè)基因中求出前r個(gè)條件熵相對(duì)最小的基因

{H1(D｜gene)，…，Hr(D｜gene)}（6）

上述r個(gè)條件熵最小的基因構(gòu)成具有與樣本分類關(guān)聯(lián)最大關(guān)系的基因集合S=(gene1，gene2，…，gener)。

2．2基因選擇算法

根據(jù)上述定義，本文提出一種基于屬性重要性與粗糙信息熵的RMSME（rough max SIG－min entropy）算法。該算法選取滿足最大屬性重要度與最小條件熵條件的基因，構(gòu)成基因集合S。RMSME算法如下所示：

輸入：基因表達(dá)數(shù)據(jù)包含有n個(gè)基因gene=(gene1，gene2，…，genen)，m個(gè)決策類D=(D1，D2，…，Dm)。

輸出：基因子集集合S=(gene1，gene2，…，gener)，r為預(yù)先設(shè)定取得基因個(gè)數(shù)的閾值。

a)S←；

b)for i=1to n do

Calculate Sgene(genei) according to 式（1）；

c)rankS1={Sgene(gene1)，…，Sgene(genei) } by decreasing order；

d)choose genes from S1 fromthe top one to the last one and calculate HS(D｜gene) according to 式（2）（3）；

e)rank the n numbers ofH(D｜gene) n by S2 increasing order；

f)while ｜S｜≤r do

for i=1 to n do

if selected Sgene(genei)from S1 and H(D｜gene) from S2 satisfy式（6）；

then S←S+{genei} ；

gene←gene-{genei}；

｜S｜←｜S｜+1 

3實(shí)驗(yàn)與分析

3．1數(shù)據(jù)集

為了評(píng)估RMSME算法的有效性，本文在Leukemia基因表達(dá)數(shù)據(jù)集[18]上進(jìn)行了算法驗(yàn)證。Leukemia基因表達(dá)數(shù)據(jù)集是目前眾多基因選擇分析與研究廣泛采用的數(shù)據(jù)集。其具體參數(shù)如表1所示。

在傳統(tǒng)的信息表中，列是條件屬性與決策屬性集合元素，行是對(duì)象（樣本）信息。鑒于Leukemia數(shù)據(jù)集樣本個(gè)數(shù)（72例）與基因個(gè)數(shù)（7 129個(gè)）相差比較大，可以將以上數(shù)據(jù)集用行列代表內(nèi)容互換的信息表形式表示出來(lái)，如表2所示。

上述信息表中列代表樣本，行代表基因，樣本與基因之間的關(guān)系可以通過(guò)三種離散化狀態(tài)A、P和M表示。其中，A(abenst)、P(present)、M(marginal)分別代表該基因在樣本中“未表達(dá)”“表達(dá)”和“不能判定表達(dá)與否”。最后一行class代表樣本S相應(yīng)的疾病子集分類。

3．2結(jié)果分析

基于SQL語(yǔ)言執(zhí)行RMSME算法，集合S1中的基因?qū)傩灾匾葹榱悖醇蟂1為

此結(jié)果表明在數(shù)據(jù)集樣本數(shù)與基因個(gè)數(shù)差距較大的情況下，對(duì)于樣本分類集合與基于基因作為條件屬性區(qū)分樣本的集合，兩者交集結(jié)果取值等于或接近整個(gè)論域集合個(gè)數(shù)時(shí)，僅僅依靠屬性重要度的代數(shù)計(jì)算方法是不能得到期望的基因與疾病分類的關(guān)系結(jié)果。導(dǎo)致此結(jié)果的主要原因是屬性重要度代數(shù)方法由于不考慮邊界域情況的因素，即不考慮集合中不確定情況，最終導(dǎo)致了基因與疾病分類關(guān)系區(qū)別能力等于零的結(jié)論。

基于SQL查詢分析器環(huán)境下編輯的查詢代碼，繼續(xù)對(duì)算法中的S2集合元素進(jìn)行計(jì)算，即計(jì)算每個(gè)基因的粗糙信息熵，結(jié)果如圖1所示。

由圖1（a)(b)可知：7 129個(gè)基因的粗糙信息熵小部分處于0．08~0．2，大部分的基因粗糙信息熵都大于0．2。這就意味著只有少數(shù)基因才具有對(duì)樣本分類起到確定性信息作用，說(shuō)明這部分少數(shù)基因才與樣本的分類最具有相關(guān)性。這與大部分基因組在疾病發(fā)病機(jī)理中起到的作用尚未清楚的現(xiàn)實(shí)經(jīng)驗(yàn)是一致的。圖1(c)進(jìn)一步表明了在前50個(gè)基因的元素集合中，前20個(gè)基因?qū)颖痉诸惖牟淮_定信息量最少。因此可以通過(guò)尋找前20個(gè)基因，并將它們的基因表達(dá)數(shù)據(jù)信息作為訓(xùn)練數(shù)據(jù)，訓(xùn)練好分類器，再進(jìn)行樣本分類，由最終分類準(zhǔn)確率確定與樣本（疾病）分類最具關(guān)聯(lián)性的基因子集集合。本文采用LibSVM分類器[29]進(jìn)行樣本分類器模型的訓(xùn)練與預(yù)測(cè)。圖2所示為通過(guò)LibSVM分類器進(jìn)行模型訓(xùn)練后，對(duì)Leukemia數(shù)據(jù)集中的independent數(shù)據(jù)集進(jìn)行樣本預(yù)測(cè)分類的結(jié)果。

由圖2可以得知，針對(duì)independent數(shù)據(jù)集34例疾病樣本的分類預(yù)測(cè)準(zhǔn)確率在不同基因個(gè)數(shù)的前提條件下，準(zhǔn)確率為67．647 1%~94．117 6%。具體情況如表3所示。

對(duì)比Golub研究結(jié)果，在前20個(gè)粗糙信息熵最小的基因中，存在5個(gè)基因與現(xiàn)有研究結(jié)果一致。具體基因信息如表4所示。

以上結(jié)果表明在粗糙信息熵理論中，粗糙條件信息熵考慮了邊界域情況中不確定性因素。當(dāng)邊界域中不確定的信息量越小時(shí)，根據(jù)條件知識(shí)（基因）可以推得結(jié)果（疾?。┓诸惖拇_定信息量越大，這就是本文研究基因與疾病分類的最基本出發(fā)點(diǎn)。

4結(jié)束語(yǔ)

緊隨人類基因組計(jì)劃而來(lái)的是后基因組研究時(shí)代，其研究重點(diǎn)是利用各種計(jì)算方法對(duì)基因表達(dá)譜進(jìn)行分析與研究，結(jié)合各領(lǐng)域理論知識(shí)構(gòu)建生物信息學(xué)體系下的新的理論研究框架。

本文基于粗糙集理論，針對(duì)基因表達(dá)數(shù)據(jù)的高維特點(diǎn)，提出了一種在基因表達(dá)矩陣信息中進(jìn)行知識(shí)發(fā)現(xiàn)的RMSME方法，挖掘出與疾病關(guān)聯(lián)性最大的重要基因，可為后繼研究工作提供更有價(jià)值的基因數(shù)據(jù)。此方法是后基因組研究方法上的一種嘗試，但必須明確的是，各種生物學(xué)知識(shí)必然要回歸到樣本數(shù)據(jù)及生物學(xué)實(shí)驗(yàn)中進(jìn)行最終的驗(yàn)證，不能脫離具體的生物學(xué)實(shí)驗(yàn)環(huán)境而獨(dú)立研究。

參考文獻(xiàn)：

［1］PAWLAK Z. Rough sets[J].International Journal of Computer and Information Sciences，1982，11（5）:341－356.

[2]PAWLAK Z.Rough sets：theoretical aspects of reasoning about data[M]. Boston：Kluwer Academic Publishers，1991.

[3]王加陽(yáng)，陳松喬，羅安. 粗集動(dòng)態(tài)約簡(jiǎn)研究[J]. 小型微型計(jì)算機(jī)系統(tǒng)，2006，27(11):2056－2060.

[4]QUAFAFOU M，BOUSSOUF M. Generalized rough sets based feature selection[J]. Intelligent Data Analysis，2000，4（1）：3－17.

[5]HAN Jian－chao，HU Xiao－h(huán)ua，LIN T Y . Feature subset selection based on relative dependency of attributes[C]//Proc of the 4th International Conference on Rough Sets and Current Trends in Computing. Berlin:Springer，2004：176－185.

[6]何明.一種基于Rough集理論的屬性約簡(jiǎn)啟發(fā)式算法[J]. 小型微型計(jì)算機(jī)，2005，26(3)：356－359.

[7]SHANNON C E. A mathematical theory of communication[J]. The Bell System Technical Journal，1948，27(3)：379－423.

[8]張文修， 吳偉志. 粗糙集理論與方法[M].北京: 科學(xué)出版社， 2001.

[9]梁吉業(yè)，孟曉偉. 信息熵在粗糙集理論中的應(yīng)用[J]．山西大學(xué)學(xué)報(bào):自然科學(xué)版， 2002，25(3)：281－284.

[10]李玉榕，喬斌，蔣靜坪. 粗糙集理論中不確定性的粗糙信息熵表示[J]. 計(jì)算機(jī)科學(xué)，2002，29(5)：101－103.

[11]朱紅. 基于粗集的ID3算法研究[J]. 湘潭大學(xué)自然科學(xué)學(xué)報(bào)，2006，28(1)：33－36.

[12]DING C，PENG Han－chuan. Minimum redundancy feature selection from microarray gene expression data[C]//Proc of IEEE Computer Society Bioinformatics Conference. Washington DC:IEEE Computer Society 2003：523－529.

[13]NGUYEN D V，ROCKE D M.Multi－class cancer classification via partial least squares with gene expression profiles[J].Bioinformatics，2002，18(9):1216－1226.

[14]KOHAVI R，JOHN G. Wrapper for feature subset selection[J]. Artificial Intelligence，1997，97(1－2)：273－324.

[15]LANGLEY P. Selection of relevant features in machine learning[C]//Proc of AAAI Fall Symposium on Relevance.New Orleans:AAAI Press，1994.

[16]LI Ding－fang，ZHANG Wen. Gene selection using rough set theory[C]//Proc of International Conference on Rough Sets and Knowledge Technology.Berlin:Springer，2006:778－785.

[17]石峰，婁臻亮，張永清. 一種改進(jìn)的粗糙集屬性約簡(jiǎn)啟發(fā)式算法[J]. 上海交通大學(xué)學(xué)報(bào)，2002，36(4)： 478－481.

[18]GOLUB T R，SLONIM D K， TAMAYO P， et al.Molecular classification of cancer：class discovery and class prediction by gene expression monitoring[J].Science，1999，286(5439)：531－537.

[19]CHANG C C，LIN C J. LIBSVM：a library for support vector machines[EB/OL].（2001）. http://www.csie.ntu.edu.tw/~cjlin/libsvm.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文