网站首页  词典首页

请输入您要查询的论文:

 

标题 一种基于先验信息BPSO的基因选择方法
范文 杨春 韩飞



摘 要:针对如何提高所选基因子集的可解释性和分类性能,提出一种耦合先验信息二进制微粒群算法(BPSO)的基因选择方法。基因灵敏度(GCS)信息和基因调控(GR)信息分别耦合进两个相互独立的共享全局最优位置的BPSO过程中,主要利用先验约束进行粒子群初始化、粒子更新、限制最大速度和自适应变异操作。在两个公开微阵列数据集上的实验表明,由于GCS和GR信息的约束,新方法选出的基因数目较少但具有较强的分类能力。
关键词:基因选择;基因灵敏度;基因调控;二进制微粒群
DOIDOI:10.11907/rjdk.151385
中图分类号:TP301 文献标识码:A 文章编号:1672-7800(2015)007-0036-05
0 引言
基因表达谱数据已经广泛应用于疾病诊断和预测。但是基因表达谱数据具有高维度、小样本的特点,存在大量冗余基因信息。因此,采用基因选择方法去除冗余基因是十分必要的。
根据基因选择过程中是否有分类器的参与,基因选择方法通常可以分为基于Fliter的方法、基于Warpper的方法和基于Embedded的方法3类[1]。基于Filter的方法通常根据某种规则,给每一个基因作一个重要性度量的排序,从而进行筛选;基于Warpper的方法将分类算法嵌入其中,并不断地反馈分类器的分类准确率作为评价准则,将分类决策和特征选择耦合在一起,该方法的分类效果要比基于Filter的好[2];基于Embedded的方法将基因子集的搜索和评价过程完全耦合到构建分类器的过程中,所选择的基因具有很低的可解释性。
Wrapper法因其直接使用分类器分类性能作为特征
子集的评价标准,从而可以选择出高分类预测率的基因的优点,受到越来越多研究人员的青睐。许多基于群体随机优化的特征子集搜索算法已经被广泛地应用在Wrapper法中,包括:遗传算法(Genetic algorithms,GA)[3]、模拟退火算法(Simulated annealing)[4]、蚁群算法(Ant colony optimization,ACO)[5]和微粒群优化算法(Particle swarm optimization,PSO)等。相比于遗传算法,PSO算法需要调整的参数少,因而简洁、收敛速度更快,更易实现[6];相比于模拟退火算法,PSO算法更易收敛于全局最优点[7]。二进制微粒群算法(Binary PSO,BPSO)是PSO的一个离散版本,用于处理离散空间的组合优化问题。然而所有PSO算法都容易失去粒子多样性,从而在收敛时陷入局部最优,即“过早熟”现象。其主要原因在于PSO进化过程中随机因素太多,缺乏实际有效的先验信息对粒子的初始化和进化运动进行约束和方向性引导。
为了有效利用先验信息来指导PSO的粒子进化,提高所选基因子集的识别率,增加所选基因的可解释性,文献[16]提出了耦合GCS信息BPSO的基因选择方法(BPSO-GCSI-ELM)。由于仅考虑一种先验信息,容易出现先验信息过于主导选择过程的现象,且耦合程度不高。本文在BPSO中耦合两种先验信息:基因灵敏度(Gene-to-class sensitivity,GCS)信息[8]和基因调控(Gene interaction regulation,GR)信息,同时选取极限学习机(Extreme learning machine,ELM)[9]作为分类器评价所选的基因子集。实验结果表明,本文提出的方法能够有效而快速地选取具有低冗余度且高识别率的基因子集。
1 相关理论基础
1.1 BPSO算法
Kennedy与Eberhart[10]于1997年提出了二进制粒子群算法 (Binary Particle Swarm Optimization , BPSO)。在该算法中,粒子位置的每一位被限制为1或0,对速度则不作这种限制。BPSO算法并不直接优化二进制变量本身,而是引入模糊函数Sig(x),将粒子的速度转化为二进制变量取值为1的概率。在粒子更新过程中,速度越大,粒子位置取值为1的可能性越大,反之则粒子位置取值为0 的可能性越大。其位置进化公式为:
表示第t+1次迭代中第i个粒子的第j维的速度,xij(t+1)表示第t+1次迭代中第i个粒子的第j维的位置取1或0的概率,rand()表示[0,1]之间的一个随机数。
1.2 极限学习机
极限学习机是由黄广斌教授在单隐层反馈神经网络(Single-hidden layer feedforward network,SLFN)的基础上,于2004年提出的一种简洁有效的机器学习算法。设N个不同的样本(xi,yi),i=1,2,…,N。其中xi=[xi1,xi2,…,xm。在SLFNs中,给定L个隐层节点以及激励函数g(·),对于任意的W、B,存在一个输出权值矩阵β,使得SLFNs能够以零误差逼近这N个样本[36]。ELM的数学模型为:
其中wk=[w1k,w2k,…,wnk]T为输入权重,是连接第k个隐层节点与所有n个输入节点的权重向量;βk=[βk1,βk2,…,βkm]T为输出权重,是连接第k个隐层节点与所有m个输出节点的权重向量;bk为第k个隐层节点偏置,g(·)为激励函数,加法型隐层节点网络中可选作任意有界非常数分段连续函数,本文中采用sigmoid函数。
2 耦合先验信息BPSO算法的基因选择方法
2.1 基因灵敏度信息
从单个基因对分类器输出的直接影响程度来去除冗余基因,这种方法称为基于分类模型的灵敏度分析。下面给出基于单隐层前馈神经网络的ELM基因类别灵敏度信息定义。在训练集样本XTraining中,利用ELM网络结构可得第i个输入对所有输出的灵敏度:
S(i)=∑x∈XTraining(∑mt=1yitxi)(3)
根据(2)式有:
S(i)=∑x∈XTraining(∑mt=1∑Lk=1(βktg(Hid(k))(1-g(Hid(k)))wik))(4)
其中Hid(k)=∑nj=1wjkxj+bk,βkt为连接第k个隐层节点与第t个输出节点的权重,wjk是连接第j个输入节点与第k个隐层节点的权重,S(i)的值即第i个基因对ELM网络所有输出类别的灵敏度,S(i)值越大表示第i个基因对整个样本类别的敏感度越大。通常需要对灵敏度信息作归一化处理。
2.2 基因调控信息
基因之间存在多种多样的表达调控活动,一般认为这些调控关系隐含在基因表达谱中。因此,可以根据基因表达谱对基因调控状态进行建模以提取基因调控信息。下面给出两类样本分类的基因调控信息定义,设样本Y=1类中样本数目为m,Y=-1类中样本数目为n,则上调控状态可以定义为:给定一个常数p∈[0.5,1],对于一个基因g,当且仅当:
Pugs(ap∧(5)
其中,q表示参照样例组Y∈{-1,1}中的样本数目。若li=1 agiP(U)=P(U|A1)P(A1)+P(U|A2)P(A2)(6)
P(D)=P(D|A1)P(A1)+P(D|A2)P(A2)(7)
其中,P(A1)、P(A2)分别表示子空间事件A1:{Y=1},A2:={Y=-1}的独立发生概率,且P(A1)+P(A2)=1,P(A1)=mm+n,P(A2)=nm+n。对于条件概率P(U|A1),有:
P(U|A1)≈∑mi=1lmim(8)
其中,lmi=1 Pugi≥p,i=1,2,3,...,m;0 others ,p为基因调控置信阈值。Pugi为基因g相对于参考组A2:{Y=-1}在属于肿瘤类别A1:{Y=1}的样例i中的上调控概率。同理可以定义P(U|A2),P(D|A1),P(D|A2),式(5)-(8)便给出了基于全概率公式的基因调控概率的计算过程。
2.3 编码先验信息的BPSO算法
为了避免滤除高度相关性的基因,简化基因选择过程,本文直接使用BPSO算法进行全局搜索。另外,为了使所选取的基因更具有可解释性,用GCS和GR信息来耦合BPSO,从而使算法的初始化更加合理,微粒进化更具有方向性与多样性。本文提出的BPSO算法采取并行形式,两个BPSO独立运行,分别耦合GCS和GR信息,但是两者共享全局最优解,从而加快收敛。以GCS信息为例,先验信息主要运用在以下4个方面:
2.3.1 微粒初始化
一般情况下,一个GCS值大的基因对于分类的影响程度要高于GCS值偏小的基因。因而按照GCS值对所有基因进行降序排列,选取GCS值前20%的基因随机初始化为选中,其余的80%基因都初始化为未选中。
2.3.2 粒子位置更新
与传统BPSO和MBPSO[8]不同,本文在原始BPSO位置进化公式的基础上耦合GCS信息,公式如下:
Xij=1 rand()+Avg(Sensitivity)其中Sensitivity(j)表示基因j的GCS值,Ls()表示激活函数,本文中为sigmoid函数,Avg(Sensitivity)表示所有基因的GCS均值。Xij和Vij分别表示第i个微粒的第j维分量的位置和速度。式(9)表明,微粒的位置受所有GCS平均值的影响。灵敏度越高的基因微粒越容易被选中,而低灵敏度的基因则被舍弃。
2.3.3 自适应限制微粒的最大速度
由于Ls(Vij)是一个单调增函数,式(9)右边大于左边的可能性也随着Vij的增大而增大。当微粒速度很大时,Ls(Vij)的值会很接近1,相应的基因肯定会被选取,且一直被选取,进而局部最优解和全局最优解也会保持不变。因此有必要对微粒的速度进行最大值限制。具体方法是,当全局最优解gbest保持m(例如:m=3)次迭代不变时,Vmax按照如下方式进行自适应调整:
if(gbest(t+1)-gbest(t)==0&&gbest(t+1)-gbest(t-1)==0){ Vmax=Vmax-0.15; if(Vmax<1.5 ) Vmax=1.5; }else{Vmax=Vmax+0.1; if(Vmax>6.0 ) Vmax=6.0;}通过以上方法将Vmax限制在[1.5,6.0]之间,从而有助于种群收敛于全局最优解并且算出最优的基因子集。
2.3.4 自适应变异
若当前微粒的最佳适应值保持预设的迭代次数不变,则执行变异操作。根据GCS值排序结果,将GCS值最大的10%基因的位置重新设定为1,将GCS值最小的10%基因的位置重新设定为0,其余80%的基因位置保持不变。这样操作的目的是除了算法本身的进化外,加入强制干扰因素,从而使得微粒跳出局部最小点,继续进行全局范围内的搜索。
2.4 基于编码先验信息BPSO的基因选择方法
本文结合GCS、GR信息和ELM的BPSO基因选择方法为BPSO-GCS&GR-ELM。两个独立的BPSO过程,每次迭代共享较优的gbest,能够相对加快进化较慢的BPSO过程,从而相互作用,加快收敛速度。其详细步骤流程如图1所示。



Step1:初始基因池预处理。首先,将基因表达谱数据分为训练集和测试集。由于基因表达谱数据维数较大且存在较多冗余基因,通常根据分类信息指数(IIC)[11]采用过滤的方法进行降维,从训练集中选取400个基因。然后,将得到的训练集进一步分为训练集和验证集。Step2:根据规则1初始化BPSO_1所有微粒的位置和速度,每个微粒代表一种基因子集选择方案,并同样地初始化BPSO_2。Step3:两个BPSO中各自计算每个微粒的适应度函数值,并设置微粒的初始个体最优位置pbest和种群的全局最优位置gbest。适应度函数定义如下:fitness(i)=104×(1-accuracy(i))+k×GenesNumber(i)(10)其中accuracy(i)表示第i个微粒所选择的基因集在验证集上返回的ELM准确率,GeneNumber(i)表示第i个微粒所选择的基因数目。参数k是一个大于0的权重系数。 Step4:根据每个微粒的适应度函数值调整微粒的历史个体最优解和全局最优解。比较两个BPSO各自所得的全局最优,取适应度较小的作为共享全局最优解。
图1 BPSO-GCS&GR-ELM基因选择算法流程
Step5:根据规则3调整微粒最大速度Vmax,根据规则4采取自适应变异操作。Step6:根据规则2更新所有微粒的位置。Step7:重复以上操作,直到适应度函数达到某个阈值或者达到预设的最大迭代次数,否则返回Step3。
3 实验
3.1 数据集
为验证本文所提出的基因选择方法的有效性与高效性,在两个公开的微整列数据集上设计并进行了实验,分别是白血病数据集和脑癌数据集。白血病(Leukemia)数据集包含72个样本,分为两类亚型,包括47个急性淋巴性白血病(ALL)样本和25个急性骨髓性白血病(AML)样本,每一个样本共有7129个基因表达值;脑癌(Brain cancer)数据集包含60个样本,分为两类:46个classic样本和14个desmoplastic样本。每个样本包含7 219个基因。
3.2 实验结果与分析
在验证本文方法的实验中,BPSO算法中种群规模设置为100,最大迭代次数设置为20,加速常量c1和c2均设置为1.49 455,惯性权重ω [12]设置为ω=0.9-tMaxNumber×0.5,MaxNumber为最大迭代系数,t为当前迭代次数。所有数据集上,规则3中m均设置为3。式(10)中参数k在两个数据集上设置为2。参数值是通过验证集上的交叉验证结果来确定的。
本文选取ELM为分类器来评价所选基因子集的分类性能,在每个数据集上独立重复运行500次,所选基因子集及其分类性能如表1所示。
从表1可以看出,在Leukemia数据集上,本文提出的方法所选取的最小基因子集在ELM上返回的LOOCV(leave-one-out cross validation)测试准确率和5折交叉验证(cross validation)测试准确率均能达到100%,且基因数目仅为3个。Brain cancer数据集上,本文的方法选择了数目为4的基因子集,同样也获得了很高的测试准确率。这些实验结果表明,本文所提出的基因选择方法能够有效地选出那些与样本分类高度相关的基因。
表2和表3给出了500次独立重复运行中所选基因统计频次最高的10个基因,以及其GCS和GR排位值与生物学描述。
从表2中可以看出,基因M63138、M27891、U05259、X95735都被文献[13]、[14]、[15]、[8]中的方法选中过,从而证明了本文所提出的方法的正确性与可行性。
结合表1和表2可以得出结论,大多选取频次高的基因相应地具有相对排位靠前的GCS值和GR值。同时也选择了一些GCS或GR排位相对靠后的基因,这是因为在选择过程中综合考虑了两种先验信息,可以看到表1中即使基因4328和1704的GCS信息排位靠后,但其GR信息排位靠前。
为了更直观地验证所选基因的分类性能,图2给出了表2和表3中基因的热点图。
从图2(a)中可以看出绝大部分基因的基因表达水平能够将AML和ALL两种亚型很清晰地区分开来。从图2(b)中可以看出,在Brain cancer的热点图中,第4413和1970号基因能将两类区分开来,其余基因则不太明显。由图2可以得出结论,本文提出的基因选择方法在大多数情况下有能力选取在不同类别之间表达水平有着明显差异的基因。
为了进一步验证本文方法的有效性,将本文方法与BPSO-ELM、Kmeans-BPSO-ELM、BPSO-GCSI-ELM[16]和Kmeans-GCSI-MBPSO-ELM[8]进行比较。4种方法均采用ELM作为分类器。表4给出相应的实验结果。
从表中可以看出,本文方法获得最高的分类准确率。这是因为BPSO-ELM和Kmeans-BPSO-ELM方法在基因选择过程中缺乏相应的先验信息的约束和引导,BPSO-GCS-ELM和Kmeans-GCSI-MBPSO-ELM方法中仅考虑一种先验信息,可能出现过约束等情况。
4 结语
本文提出了基因耦合先验信息约束BPSO的基因选择算法,首先从原始基因数据中提取基因灵敏度信息和基因调控信息,然后将两个先验信息编码进BPSO的4个方面:粒子群初始化、位置更新、最大速度限制和自适应变异操作,提出了并行进化共享全局最优的BPSO算法。最后结合ELM进行进一步的基因选择。本文所提出的方法能够选出不同种具有高分类性能、低冗余度且高可解释性的基因子集,结合GCS和GR两种先验信息,优化过程中相互影响和矫正,可确保粒子进化方向的正确性。今后工作的重心在于如何将两种先验信息扩展到多类数据上,以及如何减少基因选择算法的计算量。
参考文献:
[1]
SAEYS Y,INZA I, LARRANAGA P. A review of feature selection techniques in bioinformatics[J]. Bioinformatics, 2007, 23(19):2507-2517.
[2] RIGET J, VESTERSTRM J S. A diversity-guided particle swarm optimizer-the ARPSO[J]. Dept. Comput. Sci., Univ. of Aarhus, Aarhus, Denmark, Tech. Rep,2002.
[3] GOLDBERG D E. Genetic algorithms in search, optimization and machine learning[M]. Addison-Wesley Publishing, 1989.
[4] N METROPOLIS,A W ROSENBLUTH,M N ROSENBLUTH,et al.Equation of state calculations by fast computing machines[J].The Journal of Chemical Physics,1953,21(6):1087-1092.
[5] 黄席樾,张著洪,胡小兵,等.现代智能算法理论及应用[M].北京:科学出版社,2005:283-386.
[6] 张家柏,王小玲.基于聚类和二进制PSO的特征选择[J].计算机技术与发展,2010,20(6): 25-28.
[7] YUDONG ZHANG,LENANWU.A robust hybrid restarted simulated annealing particle swarm optimization technique[J].Advances in Computer Science and its Applications, 2012.
[8] F HAN,W SUN, Q H LING.A novel strategy for gene selection of microarray data based on gene-to-class sensitivity information[J]. PLoS ONE,2014.
[9] G B HUANG, Q Y ZHU,C K SIEW.Extreme learning machine:theory and applications[J].Neurocomputing,2006.
[10] KENNEDY J, EBERHART R C.A discrete binary version of the particle swarm algorithm[C].Pro of IEEE International Conference on Computational Cybernetics and Simulation. 1997:4104-4108.
[11] 李颖新,阮晓钢.基于支持向量机的肿瘤分类特征选取[J].计算机研究与发展,2005, 42(10):1796-1801.
[12] SHI Y, EBERHART R C.Empirical study of particle swarm optimizer[J].In:Proceedings of the 1999 Congress on Evolutionary Computation. Piscataway, NJ,IEEE Service Centerm,1999.
[13] T R GOLUB, D K SLONIM, P TAMAYO, et al.Molecular classification of cancer:class discovery and class prediction by gene expression monitoring[J]. Science ,1999.
[14] D L TONG.Hybridising genetic algorithm-neural network (GANN) in marker genes detection[C].The Eighth International Conference on Machine Learning and Cybernetics, 2009.
[15] K E LEE, N SHA, E R DOUGHERTY, et al. Gene selection:a bayesian variable selection approach[J].Bioinformatics,2003.
[16] FEI HAN, CHUN YANG.A gene selection method for microarray data based on binary PSO encoding gene-to-class sensitivity information[J].ACM/IEEE Translations on Computational Biology and Bioinformatics (TCBB),2015.
(责任编辑:黄 健)
随便看

 

科学优质学术资源、百科知识分享平台,免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。

 

Copyright © 2004-2023 puapp.net All Rights Reserved
更新时间:2025/3/10 5:29:43