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

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

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

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

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

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

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

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

1粗糙集理論

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

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

1．2粗糙信息熵

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

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

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

2基因分析與選擇算法

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

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

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

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

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

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

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

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

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

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

根據(jù)上述定義與文獻(xiàn)研究內(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個集合元素的基因組。

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

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

即在n個基因中求出前r個條件熵相對最小的基因

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

上述r個條件熵最小的基因構(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個基因gene=(gene1，gene2，…，genen)，m個決策類D=(D1，D2，…，Dm)。

輸出：基因子集集合S=(gene1，gene2，…，gener)，r為預(yù)先設(shè)定取得基因個數(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實驗與分析

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

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

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

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

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

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

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

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

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

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

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

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

4結(jié)束語

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

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

參考文獻(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]王加陽，陳松喬，羅安. 粗集動態(tài)約簡研究[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集理論的屬性約簡啟發(fā)式算法[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é)報:自然科學(xué)版， 2002，25(3)：281－284.

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

[11]朱紅. 基于粗集的ID3算法研究[J]. 湘潭大學(xué)自然科學(xué)學(xué)報，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)的粗糙集屬性約簡啟發(fā)式算法[J]. 上海交通大學(xué)學(xué)報，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)容請以PDF格式閱讀原文