将蚁群优化算法(antcolony optimization algorithm,ACO)引入基因选择领域,并用基因与类别的相关性分析所得值来初始化最优化问题,缩短了找寻最优解的时间;以基因子集整体的样本辨别能力与子集中基因之间的平均距离的线性表达作为目标函数,有利于在找到关键基因的同时消除冗余;同时,由于目标函数不采用分类准确度,大大降低了计算复杂度,提高了方法的灵活性和适应性。

第2 5卷第 9期 20 0 8年 9月

计算机应用研究 Ap l ai n Re e r h o o u e p i t s a c fC mp t￣ c o

V0 . 5 No 9 12 .

Sp 20 e. 08

基于蚁群优化算法的基因选择术 蔡立军，蒋林波易叶青， (南大学 a计算机与通信学院； .湖 . b软件学院，沙 408 )长 102摘要：将蚁群优化算法(n cl yot i tna o t A O引入基因选择领域，用基因与类别的相关性 at o n pmz i grh C ) o i ao l i m,并

分析所得值来初始化最优化问题，缩短了找寻最优解的时间；以基因子集整体的样本辨另能力与子集中基因之 1 间的平均距离的线性表达作为目标函数，有利于在找到关键基因的同时消除冗余；同时，由于目标函数不采用分类准确度，大大降低了计算复杂度，高了方法的灵活性和适应性。提 关键词：蚁群优化算法；因选择；关性基相中图分类号：T 3 1 P 9文献标志码：A 文章编号：10— 6 5 2 0 ) 9 2 5 .4 0 13 9 (0 8 0 . 74 0

Ge e s lcin b s d o ag rt m n ee t a e n ACO loih o C I i u JA G L nb Y eqn A . n一. I N i-o . I—ig Lj Y ( . colfC m u r& C m n ain b Sho o fw r, n nU i rt, hn sa4 0 8,C i a Sho o o p t e o mu i t, . col St ae Hua nv sy C a gh 10 2 hn c o o f ei a)

A sr c:T i p p r a i n cl y pi zt n A O) gr h t ted m i o gn e c o, n sdt l i b t t hs a e c r e a t oo t ai ( C a oi m i o h o a f e e l t n a du e er a— a r d n o mi o l t n n sei h e t vt ewe n g n sa d s mpe c a s so i a i h r b e o r d c h u t . I d i o .i r g r e山e l e re . i b t e e e n a l l se fi t l e t e p o l m t e u e te r n i y ni z me n a d t n t e ad

d i i a x n p e s n o ea it f i ig i i gt e s mp e f e e n ea e a e d s n e a n e e h e e s b e st e t - r si f h b l yo s n u s n a l s n sa d t v rg it c mo gg n si t eg n u s t o t i d t h h og h a n ah a r g tfn t n,w ih wa n f v r o n ig t e k y g n s a d a o d n e u d n y e u ci o h c s i a o ff d n e e e n v ii g r d n a c .At h a i,c mp t g te tr e i h e s me t t me o u i h a g t n fn t n h w c mp e i e a s fi w t c u e n h oe meh d h s b t r a i t n d p a i t . u ci a a l o l xt b c u e o so n s u t r,a d t ewh l t o a et gl y a d a a tbl y o s o y t r e i i Ke r s: a tc lnyo i z to y wo d n o o ptmia in;g ne s lcin;r ltvt e ee t o ea iiy

0引言 对病变组织细胞的精确识别与分类是提高疾病诊断准确率并进一步提高疾病治愈率至关重要的一个环节，对整个人类 社会具有重要意义。近些年发展起来的生物芯片技术可以同

1相关方法 1 1相关性分析 .

不同于在初始化时把每个基因被选概率设置为相同值的其他基因选择方法，将可以体现单个基因类别区分能力的值作 为初始化的依据，即类别区分能力越大的基因，在初始化中被选概率也越大，这样不仅 I I快算法的收敛速度，能使选择 II还的特征更具生物学意义。这个值的计算方法有很多种，文采本用 D di等人提出的类别间与类别内平方和比率 ( S/ uos t BS

时测定不同样本中成千上万的基因表达水平，为本文进行相关研究提供了数据基础。但这些数据经过处理形成的基因表达矩阵的最大特点是少量的样本 (般不超过 10)一 0对应着相对很多的特征 (几千甚至上万个基因)也给本文的研究带来巨大挑战。为了应对这个难题，在进行组织样本

分类之前必须进行基因选择，这是一个在基因表达矩阵中，找到在不同组织类别中有显著不同表达水平的基因的过程。它的目的在于： ) a剔除与分类无关的基因，减小样本向量维度，而降低计算复杂从度以及用于实际临床诊断的费用； ) b减少噪声和冗余，提高分类的准确度和可靠性。 基因选择实质上是生物领域中的特征选择。近来关于它的算法研究得比较多， agK n等人提出了一种适应性 Yn u

WS ) S值。具体做法是对于每个给定特征根据式 ( ), 1计算基 因的相关性。 s:B Sj/ S j=∑,Y= )“ j B () WS () ( i c (—u)/ j ‘ J

∑∑,Y= )一% ) (。 c (

() 1

其中： u表示特征在所有样本中的平均表达水平；4 u表示特征在属于样本类别 c中的平均表达水平；%表示基因.在第 i『 个样本中的表达水平；是当前样本的类别；( ),, ,是一个辨别函数，用来判断当前对应的样本属于哪个类别，当逻辑表达式为真，则它的值为 1否则为 0 i,。s的分子部分实质上计算了在给定基因的情况下，对应基因在样本类别之间的表达差异； 而分母部分计算了此基因在各类别内部的表达差异。很明显， 基因在类别间表达差异越大、类别内表达差异越小，对应 s就 越大， s越大，即 说明对应的单个基因区分样本类别的能力越

强的基于自由模型的基因选择方法；a l Pu等人通过改进遗 传算法，成功地从一万多个基因中选取了十个左右的基因并取得了较高的分类准确率；其他研究人员也在统计或信息熵分析的基础上提出了各自的方法 J。意大利学者 M. o g受自 D ro i

然界中真实蚁群集体行为的启发， 19年提出基本的蚁群于 91 算法，后来的研究者对其进行了很多改进，并用来解决特征选择 J聚类、、分类等问题。 收稿日期：2 0 .1O;修回日期：20—2 2 071.1 0 80—6

强。这个计算方法的优点在于其可理解性好、可操作性强、准 基金项目：湖南省自然科学基金资助项目( 6J0 4,7J0 5 0 J20 9 0 J 8 ) 5

作者简介：蔡立军( 94 )男， 16 .,湖南常德人，教授，博士，主要研究方向为机器学习、计算机网络、因

分类(ja@h u c )蒋林波( 9 5 )基 1 i n.n; c 18 ,男，湖南岳阳人，硕士研究生‘,主要研究方向为机器学习、数据挖掘；易叶青 (9 6 )男， 17一，湖南邵阳人，讲师，士研究生，博主要研究方向为机器学习、 无线传感器网络 . .