微陣列腫瘤分類混合基因選擇算法

蕭秋蘭， 鄭 虹

(1.長春工業(yè)大學 計算機科學與工程學院， 吉林 長春 130012;2.閩南科技學院 計算機信息學院， 福建 泉州 362000)

0 引 言

近年來，隨著高通量技術的發(fā)展，在分子研究領域中引入微陣列等序列，探索基因表達失調(diào)在疾病表現(xiàn)方面的影響。利用基因選擇算法在微陣列基因表達數(shù)據(jù)中尋找與癌癥相關的特征基因,進而提高診療水平，是癌癥系統(tǒng)生物學研究的重要部分。遺傳算法(Genetic algorithm， GA)是一種受自然進化啟發(fā)的優(yōu)化方法，具有較強的魯棒性和通用優(yōu)化能力。但其有突出的全局搜索性能和收斂速度之間的矛盾，針對此特性，Yang等[1]在改進遺傳算法的基礎上提出了兩種混合算法，即基于多目標學習的啟發(fā)式遺傳算法的GA-MTL和基于改進GA-MTL的E-GA-MTL。還有BPSOGA算法[2]進行啟發(fā)式搜索。

針對現(xiàn)有方法存在的問題，文中提出了一種基于自適應遺傳算法與學習自動機相結合的混合元啟發(fā)式搜索算法(Adaptive Genetic Algorithm and Learning Automata， AGALA)。學習自動機從動作集中選擇一個動作并應用到環(huán)境中，環(huán)境評估所選操作并生成正確的答案。基因在染色體中的位置是無序的，遺傳算法從種群中選擇最優(yōu)的染色體個體。如果在染色體中選擇一個更好的基因位置，就有可能在更少的進化代數(shù)中找到最優(yōu)解。文中提出的算法在保留遺傳算法優(yōu)點前提下，控制交叉概率和變異概率的自適應性，減少進化代數(shù)，加快收斂速度找到最優(yōu)解，并將該算法應用于3個不同的癌癥微陣列數(shù)據(jù)集與近來提出的基因選擇方法相比，結果表明， AGALA算法具有更好的性能。

1 基于自適應遺傳算法的混合AGALA算法

遺傳算法是借鑒生物界的進化規(guī)律演變出的隨機化搜索方法[3]。遺傳算法首先形成染色體種群，通過交叉、變異和選擇操作進行有組織但又隨機的信息交換，尋找具有最大適應度函數(shù)值最好的染色體個體。遺傳算法的性能取決于初始種群數(shù)、交叉算子、變異算子和適應度函數(shù)等多種操作。傳統(tǒng)遺傳算法采用固定的控制參數(shù)，致使全局搜索能力較差。

學習自動機從動作集中選擇一個動作，然后將其應用于評價所述動作[4]的環(huán)境。環(huán)境使用升壓信號返回操作的結果。學習自動機接收到增強信號后會改變自身的處境，然后選擇下一個動作。將環(huán)境設置為一個子集

E={α,β,c}，

輸入子集

α={α1，α2，…，αr},

輸出子集

β={β1，β2，…，βr},

獎懲概率值的子集

c={c1,c2,…,cr}。

LA方法的概念模型如圖1所示。

AGALA結合AGA和LA的優(yōu)點，使用遺傳算法的適應度函數(shù)為染色體分配一個分數(shù)，而染色體上每個基因位置是絕對隨機。使用LA獎懲操作為染色體上的基因位置打分，就能尋找出較優(yōu)良染色體個體。每個染色體相當于LA中的每個自動機，每個基因相當于每個動作，基因位置由獎勵和懲罰操作決定。AGALA算法流程如圖2所示。

圖1 學習自動機與環(huán)境的關系

圖2 AGALA算法流程

1.1 種群初始化

采用實數(shù)編碼之后，種群由許多隨機產(chǎn)生的染色體組成。每條染色體上有許多基因，染色體上的基因索引號與數(shù)據(jù)集的屬性號相對應。初始化前，對數(shù)據(jù)進行標準化處理，消除量綱對分類的影響，將樣本向量和特征向量數(shù)據(jù)各自轉化為均值為0，方差為1的數(shù)據(jù)。運用下式處理數(shù)據(jù)。

(1)

式中:x′——表換后的表達值；

x——輸入樣本數(shù)據(jù);

X_avg——樣本數(shù)據(jù)均值；

X_std——樣本數(shù)據(jù)方差。

1.2 適應度函數(shù)

個體是帶有隨機基因子集串，運用支持向量機以這些基因作為特征基因集合進行癌癥分類，據(jù)此計算適應度函數(shù)的值，進行5折交叉驗證(5-fold cross-validation)以評價特征子集的優(yōu)劣性。先將數(shù)據(jù)集平均分成五個等分，再選擇其中一份作為測試集，其余部分作為訓練集，采用SVM進行分類計算測試集的準確度。然后再選取原本為訓練集中的其中一份作為測試集，將原本的測試集變?yōu)橛柧毤绱酥貜?次，求得5個測試集的分類精度，而適應度值等于每次重復獲得的測試集的分類精度的平均值。適應度函數(shù)運算

(2)

1.3 選擇算子

選擇算子對較優(yōu)個體和平庸個體采用兩種處理方式，直接選擇了適應度值最好的10%個體傳遞給下一代，剩余的90%個體通過輪盤賭方法(roulette wheel model)[5]進行選擇。設種群大小為N,參與輪盤賭計算的種群N′為N的90%，個體的適應度為fi，個體i被選擇的概率為Psi，Psi概率和為1，

(3)

1.4 交叉和變異算子

受Srinvas[6]自適應遺傳算法思想啟發(fā)，讓交叉概率Pc和變異概率Pm適應種群個體適應度值的變化，當種群個體適應度值低于種群平均適應度值時，此時個體性能較差，就適當提高交叉概率Pc和變異概率Pm，加大個體被淘汰的概率；而當種群個體適應度值高于種群平均適應度值時，此時個體性能優(yōu)良，就適當調(diào)低Pc和Pm的取值，使優(yōu)良個體保存至下一代。同時為避免適應度較大個體在進化前期就被過多保留，而致使算法搜索過程緩慢陷入局部最優(yōu)，交叉概率和變異概率的值不為零。因此，這樣的Pc和Pm取值方案能夠為某個解提供最佳的Pc和Pm取值對，并且能有效加快遺傳算法收斂，提高遺傳算法的優(yōu)化能力。

計算交叉概率和變異概率如下：

(4)

(5)

式中:fmax——當代種群中個體的最大適應度值;

fmin——當代種群中個體的最小適應度值;

favg——當代種群個體的平均適應度值;

f′——要變異個體或要交叉?zhèn)€體的適應度值。

0

對式(4)和式(5)分析可得適應度值與交叉概率和變異概率呈線性映射關系，Pc和Pm分別如圖3和圖4所示。

對種群最大適應度值個體的交叉率和變異率分別取Pc,min和Pm,min，這就相應地提高了群體中表現(xiàn)優(yōu)良的個體的交叉率和變異率，使得它們不會處于一種近似停滯不變的狀態(tài)。為了保證每一代中的優(yōu)良個體不被破壞，用最佳個體保留方法，將它們直接復制到下一代中。

圖3 自適應的交叉率取值

圖4 自適應的變異率取值

交叉操作根據(jù)交叉概率Pc對個體采用單點交叉法(one-point crossover)，在個體串中隨機選定一個交叉點，互換兩個個體在該點前或后的部分，以此產(chǎn)生新的個體，實現(xiàn)算法的全局搜索能力。變異操作根據(jù)變異概率Pm隨機選擇染色體個體的某些基因進行改變。

1.5 獎懲算子

對于自動機的每個動作，都設定了一個memory值去記錄動作的獎懲情況。起初所有的memory值設置為零。每個動作memory值大小代表它的重要性，動作越重要，其memory值相應的越大，但為避免過多選擇一個動作，設置一個Mem值為3，memory值的最大值。獎勵和懲罰操作的計算方法如下：

1)將一段染色體設為一個自動機;

2)計算所選自動機的適應度值(假設為x);

3)從當前自動機中隨機選擇一個動作，并為其設置一個隨機值;

4)計算改變后自動機的適應度值(假設為y);

5)如果x≥y獎勵自動機，如果x

6)獎勵：memory=memory+1，如果memory=Mem，不改變動作memory值;

7)懲罰：如果memory>0，memory=memory-1；如果memory=0，不改變動作memory值，并隨機改變一個動作。

1.6 AGALA算法的復雜度

在Windows PyCharm平臺下，IntelR○CoreTMi5-4590S CPU和8 G內(nèi)存的系統(tǒng)上實現(xiàn)AGALA算法。為了計算適應度值而使用支持向量機分類器，使用sklearn.svm.svc包。支持向量機分類器的核函數(shù)采用徑向基函數(shù)，SVM驗證采用5折交叉驗證方法。

為了評估算法性能，計算并分析了算法的時間復雜度。在計算時間復雜度之前，假設以下SVM參數(shù)的時間復雜度是O(n3),其中n是數(shù)據(jù)集樣本的數(shù)量，G為進化代數(shù)。因此，AGALA算法的總時間復雜度為

G·[N·n3+N2+N·(Pm+Pc+n3)]。

考慮到每個染色體適應度計算是使用SVM進行訓練，所以染色體適應度值的時間復雜度是O(n3)，上式O(N·n3)是一代所有染色體適應度值的時間復雜度。之后根據(jù)適應度值進行排序，此時的時間代價是N2。變異算子和交叉算子的代價是N·Pm和N·Pc，獎勵和懲罰的時間復雜度是O(n3)，因為實施懲罰和獎勵行為之前和之后都會計算染色體適應度值。因此，AGALA算法的時間復雜度可表示為

G·[N·n3+N2+N·n3]∈O(G·N·n3)。

2 實 驗

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

大量公開的癌癥基因表達研究實驗已經(jīng)提供了許多DNA微陣列數(shù)據(jù)集。文中使用了其中3個癌癥基因表達譜數(shù)據(jù)集，為白血病數(shù)據(jù)集(Leukemia)、混合譜系白血病數(shù)據(jù)集(MLL)和結腸癌數(shù)據(jù)集(Colon)來評價算法的性能，并與其他研究人員提出的基因選擇算法進行對比。所用數(shù)據(jù)可從如下網(wǎng)址獲得：leukemia：http://portals.broadinstitute.org/cgi-bin/cancer/publications/view/43；MLL_：http://mldata.org/repository/data/viewslug/leukemia-mll/；Conlon：http://genomics-pubs.princeton.edu/oncology/affydata/index.html。這3個數(shù)據(jù)集的詳細信息見表1。

表1 癌癥數(shù)據(jù)集描述

注：1.急性髓細胞白血病；2.急性淋巴細胞白血病；3.混合譜系白血病；4.病變；5.正常。

2.2 實驗結果

使用GALA算法對三種二元多類微陣列癌癥數(shù)據(jù)集進行基因選擇，并與近來提出的其他算法的性能進行對比評價。為了評價我們提出的算法，使用了準確率、召回率、特異度和平均運行時間四個指標。使用AGALA在數(shù)據(jù)集上獨立運行40次的均值和標準差結果見表2。

相應的收斂精確度趨勢如圖5～圖7所示。

表2 使用AGALA在數(shù)據(jù)集上獨立運行40次結果

圖5 Colon數(shù)據(jù)集8、9、10個基因數(shù)準確率

圖6 ALL_AML數(shù)據(jù)集2個基因數(shù)準確率

圖7 MLL數(shù)據(jù)集3個基因數(shù)準確率

圖5～圖7為AGALA作用在表1所列數(shù)據(jù)集的平均收斂情況。圖5顯示AGALA用8、9、10個特征基因在結腸數(shù)據(jù)集的平均收斂情況，圖6顯示AGALA用2個特征基因在ALL_AML數(shù)據(jù)集的平均收斂情況，圖7顯示AGALA用3個特征基因在MLL基因數(shù)據(jù)集的平均收斂情況。上述所有數(shù)據(jù)集的AGALA結果與近來提出的算法比較結果分別見表3～表5。

表3 不同算法在Colon數(shù)據(jù)集運行結果

表4 不同算法在ALL_AML數(shù)據(jù)集運行結果

由表3可見，Li[7]等將GA和SVM分類器結合起來，在結腸數(shù)據(jù)集上選取15個基因獲得93.6%的準確率，純GA算法選取12個基因只獲得93.55%的準確率。由表4可見，AGALA在ALL_AML數(shù)據(jù)集上用2個基因獲得98.44%準確率，Mohamad MS[12]等改進PSO算法使用2個和4個基因分別在ALL_AML和MLL數(shù)據(jù)集的準確率都達到100%。

表5 不同算法在MLL數(shù)據(jù)集運行結果

實驗數(shù)據(jù)表明，AGA與學習自動機的結合有效提高了算法的收斂能力，提高了分類精度。

三個實驗數(shù)據(jù)中的候選子集得到較好分類結果，各個數(shù)據(jù)集的較好候選子集見表6。

3 結 語

將自適應遺傳算法與學習自動機相結合，提出了一種用于癌癥微陣列數(shù)據(jù)集基因選擇問題的遺傳算法AGALA。該算法采用自適應遺傳算法和學習自動機相結合的方法，用于識別在表達數(shù)據(jù)中的特征基因以提高分類精確度。該算法采用支持向量機分類器作為分類模型。在大多數(shù)情況下，利用GALA在3個癌癥基因表達數(shù)據(jù)集上實現(xiàn)所得到的結果與其他算法相比是顯著的。AGALA在Colon結腸癌數(shù)據(jù)集選擇出了8個基因，準確率達到98.18%，在ALL_AML Leukemia急性白血病數(shù)據(jù)集中選擇出2個基因，準確率達到98.44%，在MLL混合譜系白血病數(shù)據(jù)集中選擇出3個基因，準確率達到99.33%，與其他算法相比，AGALA能篩選出精度較高的基因子集，且算法運行時間處于較少范圍，該算法適用于特征選擇問題和分類問題。

表6 AGALA算法在數(shù)據(jù)集得到最好結果的所選基因索引