蔣智謀++姚唐龍

摘要：針對高維小樣本的特點的基因表達譜數(shù)據(jù)，提出一種基于子模性質(zhì)的特征基因提取算法。首先根據(jù)圖論知識將獨立的基因?qū)傩赞D(zhuǎn)換為具有結(jié)構(gòu)信息的鄰接圖，之后對表征基因關(guān)系的鄰接矩陣利用子模性質(zhì)的目標函數(shù)進行分析，事先設(shè)置特征基因子集的個數(shù)K，使用貪心算法通過迭代K個步驟，將每一次選取的特征基因加入到集合S中，作為最終選擇的特征基因子集；最后，使用SVM分類器進行分類實驗。通過幾組公開的基因表達譜數(shù)據(jù)集的實驗結(jié)果分析說明了該方法的有效性。

關(guān)鍵詞：基因表達譜；子模；鄰接矩陣；貪心算法

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2015）17-0194-03

Gene Expression Profiles Feature Extraction Based on Submodular

JIANG Zhi-mou1，2， YAO Tang-long2

（1.Anhui Lang Electronic Technology Co.， Ltd， Hefei 230039， China；2.School of Electronics and Information Engineering， Anhui University， Hefei 230039， China）

Abstract： The characteristics of high-dimensional gene expression data for small samples， this paper presents a characteristic gene-based Submodular the nature of the extraction algorithm. First， according to the knowledge of graph theory to separate genes properties into adjacent graph with structural information， the following relationship for the characterization of gene adjacency matrix using the sub-mode to analyze the nature of the objective function， through pre-set number of feature gene subset， using greedy algorithm iteration steps， each one gene is added to the selected feature set， as the final selection of a subset of genes characteristic； Finally， using the SVM classifier to classify experiments. Through several sets of experimental results published analysis of gene expression data sets illustrate the effectiveness of this method.

Key words： gene expression profiling； submodular； adjacency matrix； greedy algorithm

隨著新分子生物學(xué)技術(shù)和DNA微陣列技術(shù)的迅速發(fā)展，可以同時定量測量生物樣本中成千上萬的基因表達水平，這一技術(shù)產(chǎn)生的基因表達譜數(shù)據(jù)能夠揭開隱含的、以前未知的生物學(xué)知識。近幾年來，研究學(xué)者利用統(tǒng)計學(xué)和模式識別等知識對基因表達譜數(shù)據(jù)進行分析，對致病的腫瘤基因進行有效的挖掘，從而對腫瘤的類型作出準確的診斷和分類預(yù)測。

目前對高維小樣本的基因表達譜數(shù)據(jù)，特征基因的子集選擇有效解決了高維數(shù)據(jù)所面臨的“維數(shù)災(zāi)難”問題。自1999年Golub等[1]人第一次提出了以“信噪比”作為評價指標，采用加權(quán)投票法過濾冗余基因構(gòu)建分類模型之后，研究學(xué)者提出了許多新的特征基因挖掘方法。Mishra等[2]人提出一種改進的信噪比方法，Peng等[3]人提出使用互信息來度量特征之間的相關(guān)性程度選擇信息基因，Mukkamala等[4]采用[t]統(tǒng)計量的方法過濾冗余基因，張靖等[5]提出一種改進的Lasso方法迭代剔除冗余的基因，Xu等[6]提出一種基于標準差分布差異（SDED）選擇特征基因的方法，Hang等[7]人提出一種基于稀疏表示的腫瘤基因表達譜數(shù)據(jù)分類方法。

傳統(tǒng)特征基因選擇方法大部分是對基因進行獨立分析，沒有考慮基因之間的相關(guān)信息，因此，該文提出一種基于子模性質(zhì)的特征基因提取算法。首先將全部基因看作高維空間中的一組點集構(gòu)建鄰接圖，然后利用具有子模性質(zhì)的目標函數(shù)迭代的選取特征基因加入到基因子集中，得到最終的特征基因子集，最后利用SVM分類器進行分類。通過對公開的白血病和前列腺癌數(shù)據(jù)集的實驗結(jié)果分析，驗證了該文方法的可行性和有效性。

1 數(shù)據(jù)處理與算法分析

通常使用[G=g1，g2，...，gN]表示一個樣本中所有的基因構(gòu)成的集合，每一行表示一個樣本，每一列表示一個基因。其中[gi（1≤j≤N）]代表第[j]個基因，[N]表示基因的總個數(shù)。[S=si，s2，...，sM]表示[M]個樣本集合，[M]為樣本的個數(shù)，一般有[M≤N]。

[G=g1，1g1，2…g1，Ng2，1g，2…g2，N????gM，1gM，2…gM，N] （1）

其中：[gi，j]表示基因[gj]在樣本[si]中的表達值。

1.1 子模的性質(zhì)與選擇

考慮有限集合[V]和定義在其冪集[2E]的一個實函數(shù)[f：2V→R]，當且僅當對于任意的集合[S?V]，[T?V]滿足：

[f（S?T）+f（S?T）≤f（S）+f（T）] （2）

則稱函數(shù)[f（?）]為具有子模性質(zhì)的目標函數(shù)，稱之為子模函數(shù)（Submodular function）。子模具有凸面離散模擬的性質(zhì)，這種性質(zhì)使得一個連續(xù)函數(shù)能夠得到局部最優(yōu)解，近幾年來子模在組合優(yōu)化問題中求解[f]最大值問題起了至關(guān)重要的作用，且子模具有增益遞減的性質(zhì)，即對任意的[R?S?V]和[s?V]，有：

[f（S?s）-f（S）≤f（R?s）-f（R）] （3）

子模特征選取的最終目標是在整個集合[V]中選擇一個子集[S]使目標函數(shù)達到最大化，且使得子集[S]的大小不超過[K] （[K]為需要選取的特征子集的個數(shù)，在初始化時設(shè)置），這種約束方式對求[f]的最大值問題能夠達到較好的結(jié)果。該文使用算法一個給定約束為：

[S≤K] （4）

其中[S]為集合[S]的勢，即從所有特征集合[V]中選取的特征子集[S]的個數(shù)，[K]為初始時設(shè)定的目標值。綜上所述，子模的最大化問題可以描述為公式（5）所示：

[maxS?Vf（S）：S≤K] （5）

1.2 基于圖的子模特征提取

設(shè)[G=g1，g2，???，gN]表示一個樣本中所有基因構(gòu)成的集合，其中[gj（1≤j≤N）]表示第[j]個基因，[N]表示基因個數(shù)。根據(jù)圖論知識將基因表達譜數(shù)據(jù)中每一個基因映射為高維空中的一個節(jié)點，以基因點集通過構(gòu)建權(quán)重圖[G（V，E）]，其中[V=1，2，...N]為基因點集，[E]表示節(jié)點之間的邊集，使用非負的權(quán)值矩陣[wi，j] 來連接每一條邊[（i，j）]并賦權(quán)值，目標是在整個基因集[V]中找到一個最優(yōu)的子集[S]。為了利用子模的性質(zhì)，引入了式（6）作為子模目標函數(shù)：

[f（S）=i∈Vmaxj∈Swi，j] （6）

該目標函數(shù)為歸一化的子模目標函數(shù)，是經(jīng)典的無容量限制的設(shè)施選址（Uncapacitated Facility Location Problem）位置函數(shù)[8]。在式（6）中，由于[wi，j≥0] 恒成立，因此該目標函數(shù)滿足增益遞減的性質(zhì)，可以利用貪心算法[9]獲得該目標函數(shù)近似最優(yōu)解。對目標函數(shù)使用貪心算法求解特征子集的過程如圖1所示：

[貪心算法求解[f]的過程如下：＼&輸入：[G（V，E）]的邊[（i，j）]的權(quán)重值矩陣[wi，j]

[K]：選取的特征基因個數(shù)，即[S]

輸出：選取的特征基因子集[S]

1） 初始化[S=?]，[ρi=0，i=1，2，...，N]，其中[N=V]；

2） 當[S>K]時，執(zhí)行步驟3，否則執(zhí)行步驟4；

3） [k*=argmaxk∈V＼Si∈V，（i，k）∈E（maxρi，wi，k-ρi）]

[S=S?k*]

對所有的[i∈V]有：[ρi=max（ρi，wi，k*）]；

4） 當[S>K]時，結(jié)束。＼&]

圖1 子模函數(shù)提取特征子集算法

首先固定特征基因子集的大小[K]，[wi，j]是由基因表達譜經(jīng)過預(yù)處理之后的基因?qū)傩詷?gòu)成的鄰接矩陣，初始時[S=?]，然后根據(jù)子模態(tài)目標函數(shù)的性質(zhì)，利用貪心算法通過迭代[K]步，每經(jīng)過一次計算之后將一個新的元素加入到子集[S]中，最終得到特征子集[S]，且[S=K]。

1.3 算法步驟

該文通過將基因看作高維空間中的節(jié)點進行構(gòu)圖，然后利用子模性質(zhì)的目標函數(shù)選取特征基因，算法的主要步驟如下：

1） 對基因表達譜數(shù)據(jù)[G]進行無關(guān)基因的過濾，過濾之后的基因表達譜數(shù)據(jù)為[G']。

2） 對基因表達譜數(shù)據(jù)[G']按照（7）式構(gòu)造圖的鄰接矩陣，并進行高斯權(quán)賦值：

[W=（wi，j）=exp（-di-dj22σ2） ，i≠j0 ，i=j] （7）

該文中的實驗統(tǒng)一設(shè)置[σ]的值為[σ=mean（G'（：））]，即所有樣本基因的均值。

3） 根據(jù)圖1的算法從基因集合[V]中選取特征基因子集[S]，根據(jù)分類精度最終確定最優(yōu)的特征子集合的數(shù)目。

4） 使用10折的交叉驗證（10-fold cross-validation），輸入線性核SVM分類器進行分類，實驗運行5次，最終取5次的平均值作為分類精度。

2 實驗結(jié)果與分析

作者對急性白血病和前列腺癌兩類公開的基因表達譜數(shù)據(jù)集進行了實驗，其中白血病數(shù)據(jù)集含有52個樣本（24個為急性淋巴性白血病—ALL，28個為急性粒性白血病—AML），每個樣本有11225個基因；結(jié)腸癌數(shù)據(jù)集中含有102個樣本，其中有52例樣本為前列腺腫瘤（Prostate tumor）樣本，50例樣本為正常組織（normal tissues）樣本。每個樣本中包含10509個基因。

根據(jù)1.3節(jié)描述的算法步驟，對白血病和前列腺癌數(shù)據(jù)集進行實驗驗證，實驗結(jié)果如表1所示：

根據(jù)表1的結(jié)果可知實驗中白血病數(shù)據(jù)的平均分類準確率為100%，而選取的特征基因數(shù)只有7個特征基因，結(jié)腸癌數(shù)據(jù)的最高分類準確率為96.08%，最終的平均分類準確率達到94.90%，平均只選取19.6個基因，都取得了較好的實驗結(jié)果。在每一次實驗中，選取特征基因的數(shù)量差別不大，說明基于子模選取的特征基因子集具有一定的穩(wěn)定性和較好的區(qū)分腫瘤類型的能力。

按照同樣的實驗步驟，將該文的特征基因提取方法與以“信噪比”為指標的特征基因提取方法和文獻[10]中提出的CLUSTER_S2N特征基因提取方法進行實驗比較，采用線性核SVM分類器，使用平均正確率作為最終的實驗結(jié)果，實驗結(jié)果如表2所示：

由表2可知，在相同實驗條件下，根據(jù)最終的識別正確率來說，該文提出的方法相較于其他兩種特征基因提取方法正確率高，具有一定優(yōu)勢，表明基于子模的特征提取方法能夠過濾掉噪聲和無關(guān)基因，選取的特征基因子集為與腫瘤類型相關(guān)的基因，因此能夠得到較好的識別率。這是由于該文方法利用了基因之間的相關(guān)信息，CLUSTER_S2N方法雖然使用了聚類的思想，但選取的基因子集冗余度較高，而S2N方法每次只對單個的基因進行處理，忽略了基因之間的相關(guān)性，因此對前列腺癌數(shù)據(jù)識別正確率不高。

3 結(jié)束語

為了對基因表達譜數(shù)據(jù)的特征基因有效挖掘，許多特征基因提取方法相繼被提出。作者提出一種基于子模性質(zhì)的特征提取方法應(yīng)用在基因表達譜的特征基因提取中，實驗結(jié)果表明基于子模性質(zhì)提取的特征基因子集達到了較高的正確率，優(yōu)于傳統(tǒng)的特征提取方法，在以后的研究中可以通過優(yōu)化子模目標函數(shù)得到更高的識別率。

參考文獻：

[1] 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.

[2] Mishra D， Sahu B. Feature selection for cancer classification： A signal-to-noise ratio approach[J]. International Journal of Scientific & Engineering Research， 2011， 2（4）： 1-7.

[3] Peng H， Long F， Ding C. Feature selection based on mutual information criteria of max-dependency， max-relevance， and min-redundancy[J]. Pattern Analysis and Machine Intelligence， IEEE Transactions on， 2005， 27（8）： 1226-1238.

[4] Mukkamala S， Liu Q， Veeraghattam R， et al. Feature selection and ranking of key genes for tumor classification： using microarray gene expression data[M]//Artificial Intelligence and Soft Computing–ICAISC 2006. Springer Berlin Heidelberg， 2006： 951-961.

[5] 張靖，胡學(xué)鋼，李培培，等. 基于迭代Lasso的腫瘤分類信息基因選擇方法研究[J]. 模式識別與人工智能，2014，（1）.

[6] Xu W， Wang M， Zhang X， et al. SDED： A novel filter method for cancer-related gene selection[J]. Bioinformation， 2008， 2（7）： 301.

[7] Hang X， Wu F X. Sparse representation for classification of tumors using gene expression data[J]. BioMed Research International， 2009.

[8] Korupolu M R， Plaxton C G， Rajaraman R. Analysis of a local search heuristic for facility location problems[J]. Journal of algorithms， 2000， 37（1）： 146-188.

[9] Jain K， Mahdian M， Saberi A. A new greedy approach for facility location problems[C]//Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. ACM， 2002： 731-740.

[10] 阮曉鋼， 晁浩. 腫瘤識別過程中特征基因的選取[J]. 控制工程， 2007， 14（4）： 373-375.