基于蟻群優化算法的基因選擇

摘 要：將蟻群優化算法(ant colony optimization algorithm，ACO)引入基因選擇領域，并用基因與類別的相關性分析所得值來初始化最優化問題，縮短了找尋最優解的時間；以基因子集整體的樣本辨別能力與子集中基因之間的平均距離的線性表達作為目標函數，有利于在找到關鍵基因的同時消除冗余；同時，由于目標函數不采用分類準確度，大大降低了計算復雜度，提高了方法的靈活性和適應性。

關鍵詞：蟻群優化算法； 基因選擇； 相關性

中圖分類號：TP391 文獻標志碼：A

文章編號：10013695(2008)09275404

Gene selection based on ACO algorithm

CAI Lijuna，b， JIANG Linboa， YI Yeqingb



(a.School of Computer Communication， b.School of Software， Hunan University， Changsha 410082， China)

Abstract:This paper carried ant colony optimization(ACO) algorithm into the domain of gene selection， and used the relativity between genes and sample classes of initialize the problem to reduce the runtime. In addition， it regarded the linear expression of the ability of distinguishing the samples of genes and the average distance among genes in the gene subset as the target function， which was in favor of finding the key genes and avoiding redundancy. At the same time， computing the target function has a low complexity because of its own structure， and the whole method has better agility and adaptability.

Key words：ant colony optimization; gene selection; relativity

0 引言

對病變組織細胞的精確識別與分類是提高疾病診斷準確率并進一步提高疾病治愈率至關重要的一個環節，對整個人類社會具有重要意義。近些年發展起來的生物芯片技術可以同時測定不同樣本中成千上萬的基因表達水平，為本文進行相關研究提供了數據基礎。但這些數據經過處理形成的基因表達矩陣的最大特點是少量的樣本(一般不超過100)對應著相對很多的特征(幾千甚至上萬個基因)也給本文的研究帶來巨大挑戰。為了應對這個難題，在進行組織樣本分類之前必須進行基因選擇，這是一個在基因表達矩陣中，找到在不同組織類別中有顯著不同表達水平的基因的過程。它的目的在于：a)剔除與分類無關的基因，減小樣本向量維度，從而降低計算復雜度以及用于實際臨床診斷的費用；b)減少噪聲和冗余，提高分類的準確度和可靠性。

基因選擇實質上是生物領域中的特征選擇^[1]。近來關于它的算法研究得比較多，Yang Kun等人^[2]提出了一種適應性強的基于自由模型的基因選擇方法；Paul等人^[3]通過改進遺傳算法，成功地從一萬多個基因中選取了十個左右的基因并取得了較高的分類準確率；其他研究人員也在統計或信息熵分析的基礎上提出了各自的方法^[4~7]。意大利學者M.Dorigo受自然界中真實蟻群集體行為的啟發，于1991年提出基本的蟻群算法，后來的研究者對其進行了很多改進^[8]，并用來解決特征選擇^[9]、聚類^[10]、分類^[11]等問題。

1 相關方法

1.1 相關性分析

不同于在初始化時把每個基因被選概率設置為相同值的其他基因選擇方法，將可以體現單個基因類別區分能力的值作為初始化的依據，即類別區分能力越大的基因，在初始化中被選概率也越大，這樣不僅能加快算法的收斂速度，還能使選擇的特征更具生物學意義。這個值的計算方法有很多種，本文采用Dudoits等人提出的類別間與類別內平方和比率(BSS/WSS)值。具體做法是對于每個給定特征j，根據式(1)計算基因的相關性。

其中：uj表示特征j在所有樣本中的平均表達水平；ucj表示特征j在屬于樣本類別c中的平均表達水平；xcj表示基因j在第i個樣本中的表達水平；yi是當前樣本的類別；I(*)是一個辨別函數，用來判斷當前對應的樣本屬于哪個類別，當*邏輯表達式為真，則它的值為1，否則為0。sj的分子部分實質上計算了在給定基因的情況下，對應基因在樣本類別之間的表達差異；而分母部分計算了此基因在各類別內部的表達差異。很明顯，基因在類別間表達差異越大、類別內表達差異越小，對應sj就越大，即sj越大，說明對應的單個基因區分樣本類別的能力越強。這個計算方法的優點在于其可理解性好、可操作性強、準確性能高；同時還在于它不僅適合于樣本只有兩個類別的對象，而且還能不作任何修改直接用于多樣本類別的情況。

1.2 基本蟻群算法^[12]

蟻群算法最初是用來解決旅行商(TSP)問題的，n個城市的TSP問題就是尋找通過n個城市各一次且最后回到出發點的最短路徑，它是一個經典的NP難問題。設m是蟻群中螞蟻的數量，dij(i，j=1，2，…，n)表示城市i與j之間的距離，τij(t)表示在t時刻城市i與j之間的路徑上殘留的信息量，用來模擬螞蟻的外激素濃度。

在初始化時，m個螞蟻被任意投放在不同的城市節點上，且賦予每條邊上的信息量為τij(0)=c(c為一小常數)。列表tabuk記錄了螞蟻k當前走過的城市，當所有n座城市都加入到tabuk中時，螞蟻k便完成了一次周游，此時螞蟻k所走過的路徑便是TSP的一個可行解，每個螞蟻k的tabuk的初始集合為它被投放的城市。

用Pkij(t)表示在t時刻螞蟻k由城市i轉移到城市j的概率，它的計算方法如下：

其中：Jk(i)表示螞蟻k下一步允許走過的城市的集合，即Jk(i)等于城市節點全體減去tabuk，它隨螞蟻k的行進過程而動態改變；τij(t)表示所有螞蟻在城市i與城市j之間累計留下的外激素濃度；ηij(t)是一個啟發式因子，定義為螞蟻由城市i轉移到城市j的期望程度。一般來說，兩城市間距離越近，螞蟻走此線路的期望程度越高，它可以根據某種啟發算法而定，但一般定義為dij的倒數；α、β分別表示螞蟻在運動過程中所積累的信息量及啟發式因子在螞蟻選擇路徑中所起的不同作用而確定的權重，一般由用戶定義其大小；另外，為了模擬螞蟻分泌的外激素在自然環境下會不斷揮發的效果，信息量τij(t)也會隨時間的推移而逐漸衰減，用1-ρ表示其衰減速度。

經過n個時刻，螞蟻k走完所有的城市，完成一次循環。此時，要根據式（3）對各路徑上的信息量作更新。

τkij表示第k只螞蟻在本次循環中在城市i與城市j之間所留下的信息量。顯然，后項表示所有m只螞蟻本次循環中在城市i與城市j之間所留下的信息總量，它的計算方法根據具體的計算模型而定。在最常用的模型中，一般的計算方法為

Δτkij=Q/Lk，若螞蟻k在本次周游中經過邊ij0，否則（4）

其中：Q為正常數；Lk表示第k只螞蟻在本次周游中所走過路徑的長度。因為每只螞蟻的周游路線都是一個可行解，式(4)表明了螞蟻k經過的總路程越短，則此螞蟻對信息量的修改貢獻越大。而此后的循環螞蟻選擇路徑根據路段信息量而定，這樣就保證了所有螞蟻所求得的可行解逐漸地朝最優解收斂，即使得算法最終解為盡可能短的周游路線。

2 基于蟻群算法的基因選擇

2.1 模型說明

本文模型的基本思想是：一次循環中，在基因全集上放m只螞蟻，讓每只螞蟻路過所有基因，并以一個給定概率拾起當前的基因，當m只螞蟻在全集里各自遍歷一次后，就得到了m個基因子集(這些子集作為螞蟻走過的痕跡，上面有螞蟻留下的外激素)，這些基因子集構成了當前的全體可行解。本文使用每個子集整體的類別區分能力和它們所含基因間平均距離的線性方程作為評價標準去確定其優劣，記下當前的最優解，并依此決定每只螞蟻在其上留下的外激素濃度，然后進一步根據定義的概率修改式去更新每個基因所擁有的概率，以進行下一輪循環。在當前最優解達到所要求的滿意度或循環總次數達到指定最大值時結束循環，并輸出循環所得的目前最優解，此解即為模型的最終解。

這個模型中有幾個關鍵問題需要解決：每個基因被選概率值的初始化問題；基因外激素濃度更新規則的確定；每次循環中基因被選概率計算方法的確定；目標函數的計算方法。一旦這些方法被確定，模型也就基本具體化了。

優化算法對初始值比較敏感，一個好的初始化能使其性能大大提高。這里用基因與類別的相關性來初始化概率值：先依照式(1)計算每個基因與類別相關值的大小si；然后計算每個基因所得權值ωi=si/∑jsj(稱之為偏見度)。設第t次循環前第i個基因被選概率為P(i，t)，則對任意i有P(i，1)=ε×ωi。其中：ε是一個常量，它的大小在很大程度上決定了每只螞蟻所選特征的初始規模，即被選基因子集的大小。每個基因所擁有的外激素的初始值均為零，但以后會隨著螞蟻經過的情況而改變。

設Dtj是第t次循環中第j只螞蟻所選擇的特征子集，根據式(5)可計算每個子集的優越性Gtj：

此值越大則對應特征子集的優越性越強；α是一個在區間(0，1)上的參數，由于更注重子集的分類能力，一般設置α＞（1-α)；A(Dtj)表示子集Dtj上樣本類別間的距離，B(Dtj)是子集Dtj上樣本類別內的距離，兩者構成的表達式(5)的前項體現了基因子集Dtj區分樣本類別的能力，其越大說明子集區分類別能力越強；而后項C(Dtj)是子集所有基因間的平均距離，體現了當前子集的冗余程度，其越大說明子集的冗余程度越低。它們的計算公式如下:

A(Dtj)=∑j(u0j-u1j)2/｜Dtj｜(6)

B(Dtj)=∑j∑i∑cI(yi=c)(ucj-xij)2/｜Dtj｜×n(7)

C(Dtj)=∑j∑i｜xij-ui｜；i=0，1，…，n;j=0，1，…，｜Dtj｜-1(8)

其中：u0j、u1j分別表示基因j在兩類別中的平均表達值，當樣本類別不止兩類時，可以通過計算每兩類別間的基因表達值計算；yi是當前樣本的類別；I(*)是一個辨別函數，用來判斷當前對應的樣本屬于哪個類別，當*邏輯表達式為真，則其值為1，否則為0；｜Dtj｜表示子集所含基因個數；n為數據矩陣中的樣本數量；ui表示基因子集在樣本i中的平均表達水平；xij表示基因j在第i個樣本中的表達水平。在第t次循環后，取優越性比較強的前m/2個特征子集，舍去其他的子集并記下最優的那個子集Dt，給定外激素更新規則為

ξ(i，t+1)=ξ(i，t)+m×ki/2×∑j｜Dtj｜；j=1，2，…，m/2(9)

其中：ξ(i，t)即為第t次循環前第i個基因所擁有的外激素濃度(對任意i有ξ(i，1)=0)；ki是第i個基因在這m/2個子集中出現的次數，它為0則意味著對應基因的外激素不會改變；∑j｜Dtj｜則為m/2個基因子集的個數之和。

知道了每個基因的外激素的濃度，就可以在此基礎上計算第t+1次循環中第i個基因被選擇的概率P(i，t+1)：

P(i，t+1)=β×P(i，t)+(1-β)×ε×

ξ（i，t+1)/∑jξ(j，t+1)(10)

其中：β是指定的區間(0，1)上的常量；ξ(i，t+1)/∑jξ(j，t+1)是第t+1次循環前基因i擁有的外激素在目前所有激素中所占比例；ε是計算初始概率時給定的常量。

利用以上模型進行循環，能使與分類相關的基因被選擇的概率越來越大，有利于分類準確度的提高。隨著循環次數的增加，m只螞蟻所得的可行解的優劣程度會越來越接近，當前最優解也會越來越趨于穩定，即越來越接近全局最優解。同時，由于把子集基因間距離參數引入其中，該模型舍去了冗余度太大的基因子集，能夠在一定程度上有效減少解中的數據冗余。2.2 算法描述

對于一個基因表達數據矩陣y×n(y表示樣本數，n為基因數)，根據具體情況確定ε(影響解的規模)、α(1/2＜α＜1)和β(0＜β＜1)三個參數，選定螞蟻只數m(一般選擇5~40只)： a)在根據式(1)進行相關性分析si的基礎上計算每個基因i的偏見度ωi=si/∑jsj并確定初始概率P(i，1)；

b)當t小于給定循環次數時，則開始第t次循環；

c)m只螞蟻經過全體基因并按概率產生各自的基因子集Dtj；

d)根據目標函數式(5)計算每個子集的優越性Gtj，記下最優解Dt，并根據優越性對各解進行先優后劣的排序，然后取出前面m/2個解作為后續計算數據；

e)如果最優基因子集Dt滿足預定要求，則轉j)輸出Dt，否則繼續；

f)分別根據式i) j)更新各基因所含外激素和所獲概率；

g）t=t+1；

h）循環結束；

i）對所有t，比較各D，其中最好的那個為算法對全局最優解的表示，它對應的子集即為算法最終所選特征子集；

j）結束并輸出結果。

此算法中主要的參數有ε、α、β。其中：ε直接影響到第一輪選擇的子集初始規模，并影響到后來每次循環中基因被選的概率，它的大小一般根據基因全集的大小來確定；α用來計算每次循環中被選特征子集的優越性；β是每次循環基因被選概率計算參數。這些參數的存在增加了算法的靈活性，使我們能根據具體的數據集去調整這些參數，從而使選擇出來的關鍵基因集合能與具體數據樣本緊密相關。

3 實驗分析

3.1 參數分析

這個基因選擇模型的參數比較多，這樣雖然增加了算法的靈活性，同時也帶來了缺乏穩定性的可能。在此利用Yu等人提供的腫瘤基因表達數據(home.ccr.cancer.gov/oncology/oncogenomics/)。其中包括27個樣本(16個正常，11個腫瘤)的3 467個基因。

由于參數ε直接影響到被選基因子集的初始規模，首先隨意指定α和β的值(分別為0.9、0.8)，通過改變ε值，并用經典的KNN分類器來觀察所選擇特征基因預測樣本類別能力的大小。

通過表1可以發現，ε越大，對應的被選子集也較大，當ε在30~35時，冗余和分類能力達到較好的平衡。由此可見，被選基因太多，存在的冗余也會相應增加，它們相互干擾，不但不會提高，反而可能會降低分類準確度；當被選基因太少時，沒有充分體現其各類別的差異信息，同樣不利于樣本分類。

接下來先指定ε=30，β=0.8，通過改變α的大小來觀察分類準確度的變化，所得結果如表2所示；然后指定ε=30，α=0.9，通過改變β值來改變結果，所得結果如表3所示。由表2、3可以看出，當參數α足夠大時，被選基因子集的分類能力一直較穩定，說明在這個數據集上，基因子集的整體分類能力在選擇較好可行解的過程中有舉足輕重的作用。β的表現跟參數ε有點類似，說明β太小，每次循環中基因被選概率變化會很大，收斂速度很快，但很可能陷入局部最優；β太大時，收斂速度過慢，每次循環所得的基因子集不能得到較大的優化，這時，算法的最終結果很大程度上依賴于模型的初始化，沒有充分利用蟻群算法強大的智能搜索能力，因此也得不到理想的解。

從上面的實驗結果可以看出，在利用蟻群算法進行基因選擇的過程中，選擇適當的參數，從而以適當的收斂速度產生適當規模的基因子集是非常重要的。

3.2 對比實驗

Paul等人^[3]利用基于概率模型的遺傳算法，在包含12 625個基因和50個樣本的腦癌樣本數據集(www.broad.mit.edu/cgibin/cancer/datasets.cgi)上進行了多次基因選擇(PMBGA)。用這些基因子集對樣本進行分類，預測準確度的波動很大。其中最高的是含有19個基因的子集產生的90.48%的準確率；子集最小的基因個數為3，它預測的準確率為80.95%。結果中被選基因子集平均大小為8.48±4.94，平均預測準確度為72.50%±5.90%。現在在這個數據集上運用本文的基因選擇方法，通過調整參數得到結果如表4所示。

現在將本文結果與Paul等人的結果對關鍵數據進行比較如表5所示。

由表5可以看出，雖然利用本文的方法所選的基因子集平均要略大于利用PMBGA方法所選的基因子集，且最高準確度也略低于后者，但利用本文的方法所選擇的基因子集的分類能力平均提高了幾個百分點，并且通過設置合適的參數，本文的方法可在選出相同數量關鍵基因的同時取得更高的分類準確度。另外，與Paul將SVM的分類準確度引入了選擇算法不同，本文的方法并不與任何分類器相關，增加了算法的適應性，并降低了運算復雜度。

4 結束語

本文將傳統的蟻群算法引入基因分析領域，提出了一種新的基因選擇算法。為了加快算法的收斂速度，使用基因與樣本類別間的相關性分析所得值初始化每個基因的被選概率，同時也決定了算法選擇特征基因子集的規模。算法不需要領域知識，通過調整參數能用于不同的數據集。在作基因子集的優越性選擇時，采用基因子集整體的樣本辨別能力與子集中基因之間的平均距離的線性表達式作為目標函數，提高分類能力的同時考慮了冗余的減少，可理解性強，計算復雜度低。實驗分析表明，新的基因選擇算法所選擇出的基因能較大程度地提高分類準確度。

參考文獻：

［1］GOH L，SONG Q，KASABOV N. A novel feature selection method to improve classification of gene expression data[C]//Proc of the 2nd Conference on AsiaPacific Bioinformatics.Darlinghurst:Australian Computer Society，2004:161166.

[2]YANG Kun，LI Jianzhong， CAI Zhipeng，et al. A modelfree and stable gene selection in microarray data analysis[J].BMC Bioinformatics，2006，7(228):310.

[3]PAUL T K，IBA H. Extraction of informative genes from microarray data[C]//Proc ofConference on Genetic and Evolutionary Computation. New York:Association for Computing Machinery，2005:453460.

[4]XIONG Momiao， LI Wuju， ZHAO Jinying，et al. Feature (gene) selection in gene expressionbased tumor classification[J].Molecular Genetics and Metabolism，2001，73(3):239247.

[5]NG M，CHAN Laiwan. Informative gene discovery for cancer classification from microarray expression data[C]//Proc of Machine Learning for Signal Processing.America:IEEE Press，2005:393398.

[6]XU Xian，ZHANG Aidong.Selecting informative genes from microarray dataset by incorporating gene ontology[C]//Bioinformatics and Bioengineering of Fifth IEEE Symposium. Minneapolis:IEEE Press， 2005:241245.

[7]LU Xinguo，LIN Yaping，YANG Xiaolin，et al. Using most similarity tree based clustering to select the top most discriminating genes for cancer detection[C]//Proc of the 8th International Conference on Artificial Intelligence and Soft Computing. Berlin:SpringerVerlag，2006:931940.

[8]BELLO R， NOWE A， CABALLEROY，et al. A model based on ant colony system and rough set theory to feature selection[C]//Proc of Conference on Genetic and Evolutionary Computation. New York:Association for Computing Machinery，2005:275276.

[9]ALLEN C，FREITAS A A. A new ant colony algorithm for multilabel classification with applications in bioinformatics[C]//Proc of the 8th Annual Conference on Genetic and Evolutionary Computation. New York:Association for Computing Machinery，2006:2734.

[10]MARCO A. de OCA M，GARRIDO L，AGUiRRE J L. An hybridization of an ant based clustering algorithm with growing neural gas networks for classification tasks[C]//Proc of ACM Symposium on Applied Computing. New York:Association for Computing Machinery，2005:913.

[11]WANG Gang， GONG Wenrui， KASTNER R. Instruction scheduling using MAXMIN ant system optimization[C]//Proc of the 15th ACM Great Lakes Symposium on VLSI. New York:Association for Computing Machinery，2005:4449.

[12]黃席樾，張著洪，胡小兵，等.現代智能算法理論及應用[M].北京:科學出版社，2005:283386.