一種基于改進的遺傳算法的癌癥特征基因選擇方法

范方云， 孫 俊， 王夢梅

(江南大學物聯網工程學院，江蘇無錫214122)

隨著基因表達譜技術的推廣，利用DNA芯片可以在一次實驗中同時獲得成千上萬個基因的表達水平［1］。依據基因表達譜建立分類模型，實現對癌癥類型的識別與判斷，對癌癥的診斷與治療具有重要意義［2-3］。然而，基因表達譜數據維度高，樣本量很少，且分布不均勻，只有少量的基因真正具有分類信息。在進行癌癥分類時，大量冗余特征會嚴重影響分類效果，而且增加了計算時的復雜度。所以，如何選擇出對分類具有積極作用的基因是建立有效分類模型的關鍵所在。國內外學者在這方面已經進行了大量研究［4-6］。張靖等［7］利用信噪比指標過濾無關基因，采用迭代Lasso方法進行冗余基因的剔除，結合SVM分類器在數據Leukemia，Prostate，Colon 上分別獲得了 98．61%，96．08%，90．32% 的分類正確率;張煥萍等［8］提出了離散粒子群和支持向量機封裝模式的BPSO-SVM特征基因選擇方法，在數據集Colon上用34個特征基因子集獲得了89．67% 的平均正確率。目前，多種特征選擇方法的使用已經取得了較好的分類效果，但存在的問題依然很明顯，即如何在提高分類正確率的同時降低基因子集的規模，換言之，如何用最少的基因得出最好的分類效果。

文中提出了基于改進的遺傳算法的癌癥特征基因選擇方法。通過改進遺傳算法的交叉和變異操作，使得遺傳算法在搜索分類基因時具有更強的全局搜索能力，并且避免了局部收斂。同時根據基因子集的特點，增加了最優個體變異策略，提高算法找到最優解的可能性。此外，將分類正確率和基因個數同時考慮，進行多目標優化，使用SVM分類器進行留一法交叉驗證。同時，實驗使用基本遺傳算法進行特征選擇，將兩種遺傳算法的表現進行比較。結果表明，改進的遺傳算法相比于基本的遺傳算法明顯具有更優的分類正確率和更小的基因子集。

1 遺傳算法的基本原理

遺傳算法(Genetic Algorithm，GA)是一個經典的隨機搜索與優化算法，是建立在Darwin的進化論和Mendel的遺傳學說基礎上的。1975年，密執安大學的教授Holland與其學生創建了該算法［9］。從此，對遺傳算法的研究引起了國內外諸多學者的關注。

與傳統的搜索算法不同，遺傳算法是從一組隨機產生的初始解開始搜索過程的。這組初始解被稱為群體，初始解的個數就是群體的大小。群體中的每個個體都是目標問題的一個解，稱為染色體。這些染色體在后續過程中不斷進化迭代，這個過程稱為遺傳。遺傳算法的進化過程主要是通過3種操作實現，分別為選擇、交叉、變異。選擇、交叉或者變異運算產生的下一代染色體，稱為后代。染色體的好壞用適應值進行衡量。每個染色體都可以計算適應值，計算適應值的函數稱為適應值函數。根據適應值的大小從上一代中選擇個體，再通過交叉和變異，得到后代;再繼續進化，經過若干代之后，算法收斂于最好的染色體。

利用遺傳算法解決某個實際問題通常從初始化一個種群開始。所以解決某個實際問題，首先就是根據這個實際問題進行個體編碼，然后生成初始種群，再對染色體進行選擇、交叉以及變異操作。

2 遺傳算法的改進

為了增加遺傳算法的全局搜索能力和局部搜索能力，文中提出了3種改進策略:均勻交叉策略、變異概率的非線性遞增策略和最優個體變異策略。均勻交叉策略是指兩個配對個體的每一位都以相同的概率進行交換，從而形成兩個新的個體;變異概率的非線性遞增策略是變異概率隨著種群進化代數的增加而非線性的增加;最優個體變異策略是對每次迭代的最優個體進行變異，增加算法找到全局最優解的可能。實驗結果表明，3種改進策略的提出有效地提高了基本遺傳算法在選擇特征基因的能力。

2．1 均勻交叉策略

在改進的遺傳算法中，使用均勻交叉，而不是傳統的單點交叉。均勻交叉是指兩個配對個體的每一位都以相同的概率進行交換，從而形成兩個新的個體。具體的操作如下:首先隨機生成一個與個體長度相等的二進制串，稱為掩碼。掩碼的第i位與個體的第i位相對應。對于個體A和B，當掩碼的第i位為1時，不交換A和B的第i位。當掩碼的第i位為0時，交換A和B的第i位。具體如圖1所示。

圖1 個體A和個體B進行均勻交叉產生個體X和YFig．1 Individual A and individual B produce individual X and Y by uniform crossover

2．2 變異概率的非線性遞增策略

變異概率是遺傳算法中一個重要的參數，它直接影響到搜索算法的收斂性和算法搜索的性能。變異概率大，會使得算法不斷搜索新的空間，增加解的多樣性。但是，較大的變異概率會影響算法的收斂性。因此，在解決實際問題中，取變異概率為一個較小的值，一般在0．001～0．05之間。

在改進的遺傳算法中，提出了一種變異概率的非線性遞增策略，即變異概率隨著種群進化代數的增加而非線性增加。具體表示為

式中:g為當前進化代數;gmax為最大進化代數。

非線性遞增變異概率曲線如圖2所示。

圖2 非線性遞增變異概率曲線Fig．2 Probability curve of the nonlinearity increasing mutation

由圖2可以看出，在種群進化初期，變異概率較小，為0．05，加速算法向最優解靠攏;隨著進化代數的增大，變異概率逐漸增大。改進后，算法易搜索到新解，有利于算法擺脫局部最優，在一定程度上抑制了早熟收斂。

2．3 最優個體變異策略

最優個體是指對環境適應能力最強，能夠得到最好適應值的個體。最優個體就是搜索空間中的最好位置。在本課題中，癌癥特征基因提取的目標是選擇出一個最優特征基因子集，這個特征基因子集具有最強的分類信息，即用該特征基因子集進行癌癥數據集的分類能得到最好的分類效果。與其他尋優問題不同的是，最優特征基因子集與次優特征基因子集之間往往具有很大的重疊，在整個搜索空間中的位置是十分接近的，兩者之間可能有少數幾個基因存在差別。因此，充分利用每次迭代后得到的最優個體，在最優個體上進行隨機位置變異，能夠增大尋找到全局最優個體的可能性。做法是，隨機選擇每次迭代后的最優個體中的某些位置進行變異，如果變異后的新個體確實具有更好的適應值，則代替原最優個體。否則，不做改變。具體操作如下:

1)獲取本次迭代的最優個體gbest;

2)隨機選擇gbest的1個或者2個位置進行變異，得到newgbest;

3)如果 newgbest的適應值大于 gbest，則用newgbest替換gbest，否則不做任何操作。

3 實驗設計

為了證明改進后的遺傳算法具有更好的性能，實驗中同時使用基本遺傳算法進行特征基因的選擇。因為兩個算法在同樣的軟硬件環境中進行，而且使用相同的參數、數據集、預處理和適應值函數，所以結果具有可比性。鑒于隨機算法的隨機特點，實驗對兩種算法用每一個癌癥數據集進行25次獨立實驗，以便比較算法的性能。

3．1 參數設置

改進的GA和基本的GA中使用的參數見表1。這些參數都是經過多次測試，能夠保證得到較好的分類結果。

表1 算法參數Tab．1 Parameters of the algorithm

3．2 實驗數據集

大量公開的癌癥基因表達研究實驗已經提供了許多DNA微陣列數據集。文中使用了其中5個癌癥基因表達譜數據集，分別為白血病數據集(Leukemia)，前列腺癌數據集(Prostate)，結腸癌數據集(Colon)，肺癌數據集(Lung)和淋巴癌數據集(Lymphoma)。所有這5個數據集都可以從如下網址獲得:http://linus．nci．nih．gov/ ～ brb/DataArchive_New．html。表2給出了這5個數據集的詳細信息。其中，類別1和類別2中括號中的數字是該類樣本的個數。

表2 實驗數據集描述Tab．2 Description for the experimental datasets

3．3 預處理

由于原始的癌癥數據集中有幾千甚至幾萬個基因，這些基因中含有大量的冗余基因，這些冗余基因將嚴重影響特征選擇的效果，所以在選擇特征基因之前，先對數據集進行初步篩選。首先對數據進行標準化處理，消除量綱對分類的影響。采用T檢驗進行初步篩選。根據T檢驗的P值對基因進行排序，選擇P值最小的100個基因作為遺傳算法的全局搜索空間。至此，已經去除了數據集中大量的冗余基因。

3．4 適應值函數

在遺傳算法中，適應值用于評價個體的優劣，利用適應值函數計算個體的適應值。在本方法中，粒子Xi是一個表示基因子集的二進制串，SVM分類器使用每個粒子表示的基因子集進行留一交叉驗證(Leave-one-out Cross Validation，LOOCV)。文中設適應值函數為

其中，accuracy為LOOCV正確率;feature_number為基因子集中基因的個數;α和β為權重參數，本方法中分別將 α 設為0．6，β 設為0．4。因為，相比于基因子集的規模，數據集的分類正確率是該實驗研究更加關注的內容，所以設置α值為0．6大于β值0．4，這樣可以更好地控制數據集分類正確率在評價基因子集中的主要地位。因為適應值越大，基因子集越優，所以該適應值函數利于最大化分類正確率和最小化特征基因的規模。

3．5 改進的遺傳算法選擇基因

T檢驗進行初步篩選之后，已經排除了原始數據中大部分無關基因。下面利用改進的遺傳算法對數據集進行進一步的篩選，選擇出真正具有分類信息的基因。

利用改進后的遺傳算法作為特征選擇的全局搜索引擎，SVM作為特征基因子集的評價分類器。設種群中的個體數為20，使用改進的遺傳算法對種群進行選擇交叉變異操作，設置最多進化代數為100。當滿足結束條件時，結束迭代。在本算法中設置結束條件為:①LOOCV分類正確率≥99．99% 且選擇的基因個數≤10時;②達到最多進化代數。滿足兩個條件中的任何一個，即可結束迭代過程。迭代結束后，輸出最終選擇的基因，至此一次實驗結束。因為遺傳算法的隨機性，為了得到更加可靠的結果，對每一個數據集進行25次獨立實驗。算法流程如圖3所示。

圖3 算法流程Fig．3 Flowchart of the algorithm

4 結果分析

4．1 LOOCV正確率分析

表3給出了改進的GA+SVM與基本GA+SVM對癌癥數據分類正確率的比較。其中最優為25次獨立實驗中的最優LOOCV正確率，平均為25次獨立實驗LOOCV正確率的平均值。

表3 改進的GA+SVM與基本的GA+SVM對癌癥數據LOOCV正確率比較Tab．3 Comparison of LOOCV accuracy for each dataset between the improved GA+SVM and the basic GA+SVM 單位:%

由表3中可以看出，改進的GA+SVM在所有的5個數據集上都比基本的GA+SVM得到了更好的結果。

圖4給出了最終選擇出的基因子集中基因的個數。其中選擇基因個數為相應癌癥數據集25次獨立實驗所得到基因子集的平均個數。

圖4 改進的GA+SVM與基本的GA+SVM對癌癥數據選擇基因個數比較Fig．4 Number of the selected genes for each dataset between the improved GA+SVM and the basic GA+SVM

由圖4中可以看出，改進后的GA+SVM在5個數據集上都比基本的GA+SVM得到了更小的基因子集規模。

4．2 魯棒性分析

除了算法的性能，算法在獨立執行多次產生相同或相近結果的能力即魯棒性也是衡量算法的一個重要指標。包括實驗所研究的遺傳算法在內的元啟發式方法更是如此。表4給出了改進的GA+SVM與基本的GA+SVM魯棒性的比較。其中，標準差是25次獨立實驗的LOOCV正確率的標準差。

表4 改進的GA+SVM與基本的GA+SVM魯棒性比較Tab．4 Robustness between the improved GA+SVMand the basic GA+SVM

由表4可以看出，在數據集Leukemia，Colon中，改進的GA+SVM算法魯棒性明顯比基本GA+SVM好;兩個算法在Lung數據集上都得到了25次100%的正確率;對于Prostate和Lymphoma數據集，雖然改進的GA+SVM得到的標準差比基本GA+SVM更大，但是前者找到了更好的基因子集，由此得到了更好的平均正確率。

4．3 生物意義分析

將所有基因子集中的基因進行統計，列出每個數據集出現頻率最高的5個基因和相應的基因描述。表5給出了Colon和Lung數據集的基因子集中出現頻率最高的5個基因及其基因描述。

表5 Colon和Lung數據集的基因子集中出現頻率最高的5個基因Tab．5 Top 5 genes with the highest selection frequency of the Colon and the Lung

圖5和圖6給出了表5中的10個基因的基因表達在熱點圖中的表現。由圖5和圖6可以明顯看出，對于Colon和Lung數據集，5個基因在兩個類別間有明顯的表達差異，即用改進的遺傳算法選擇出的這5個基因具有明顯的分類信息。

5 結語

對基本遺傳算法的交叉和變異操作進行改進，將改進后的遺傳算法和基本遺傳算法用于對5個癌癥數據集進行基因選擇和分類。對比兩種算法，實驗結果充分證明了改進后的遺傳算法在搜索性能、魯棒性上都有明顯的優勢，且選擇出的基因的確具有明顯的分類信息。

圖5 Colon數據集選出的基因的熱點圖Fig．5 Heat map of the genes selected from the Colon dataset

圖6 Lung數據集選出的基因的熱點圖Fig．6 Heat map of the genes selected from the Lung dataset

［1］Lander E S．Array of hope［J］．Nature Genetics，1999，21:3-4．

［2］Ramaswamy S，Golub T R．DNA microarrays in clinical oncology［J］．Journal of Clinical Oncology，2002，20(7):1932-1941．

［3］DeRisi J，Penland L，Brown P O，et al．Use of a cDNA microarray to analyse gene expression patterns in human cancer［J］．Nature Genetics，1996，14(4):457-460．

［4］劉金勇，鄭恩輝，陸慧娟．基于聚類和微粒群優化的基因選擇方法［J］．數據采集與處理，2014，29(1):83-89．LIU Jinyong，ZHENG Enhui，LU Huijuan．Gene selection based on clustering method and particle swarm optimization［J］．Journal of Data Acquisition and Processing，2014，29(1):83-89．(in Chinese)

［5］于彬，張巖．基于 GA-SVM方法的結腸癌基因表達譜數據分析［J］．青島科技大學學報:自然科學版，2013，33(6):587-592．YU Bin，ZHANG Yan．Analysis of colon cancer gene expression profiles based on GA-SVM method［J］．Journal of Qingdao University of Science and Technology:Natural Science Edition，2013，33(6):587-592．(in Chinese)

［6］徐久成，徐天賀，孫林，等．基于鄰域粗糙集和粒子群優化的腫瘤分類特征基因選?。跩］．小型微型計算機系統，2014(11):31．XU Jiucheng，XU Tianhe，SUN Lin，et al．Feature selection for cancer classification based on neighborhood rough set and particle swarm optimization［J］．Mini-Micro Sysitms，2014(11):31．(in Chinese)

［7］張靖，胡學鋼，李培培，等．基于迭代 Lasso的腫瘤分類信息基因選擇方法研究［J］．模式識別與人工智能，2014，27(1):49-59．ZHANG Jing，HU Xuegang，LI Peipei，et al．Informative gene selection for tumor classification based on iterative lasso［J］．Pattern Recognition and Artificial Intelligence，2014，27(1):49-59．(in Chinese)

［8］張煥萍，宋曉峰，王惠南．基于離散粒子群和支持向量機的特征基因選擇算法［J］．計算機與應用化學，2007，24(9):1159-1162．ZHANG Huanping，SONG Xiaofeng，WANG Huinan．Feature gene selection based on binary particle swarm optimization and support vector machine［J］．Computers and Applied Chemistry，2007，24(9):1159-1162．(in Chinese)

［9］Holland J H．Adaptation in Natural and Artificial Systems:An Introductory Analysis with Applications to Biology［M］．Ann Arbor:University Michigan Press，1975．