摘 要：MicroRNA（miRNA）是一类大小为21～25nt的内源性非编码小核糖核酸（RNA）， 通过与mRNA的3’UTR互补结合， 导致mRNA降解或翻译抑制来调控编码基因的表达。为了提高构建基因调控网络的准确度， 提出一种基于粗糙集、融合粒子群（PSO）和遗传算法（GA）的基因调控网络构建方法（PSOGARS）。该方法首先通过对序列信息进行特征提取；然后采用粗糙集的依赖度作为适应度函数， 融合粒子群和遗传算法选出较优的特征子集；最后使用支持向量机（SVM）建立模型， 预测未知的调控关系。在拟南芥数据集上进行实验， 相比基于粗糙集和粒子群优化的特征选择方法和Rosetta算法， 所提方法的预测准确率、F值和受试者工作特征（ROC）曲线面积最多能提高5%， 在水稻数据集上最多能提高8%。实验结果表明所提方法能够比较准确地预测miRNA和靶基因之间的调控关系。
关键词：基因调控网络；粒子群优化；遗传算法；粗糙集；特征选择
中图分类号：TP399
文献标志码：A
文章编号：1001-9081（2016）11-2969-05
0 引言
MicroRNA（miRNA） 是一类非常重要的非编码核糖核酸（RiboNucleic Acid，RNA）分子， 通过诱导靶基因降解， 从而广泛地参与到基因的转录后调控， 或者通过抑制基因的转录， 对基因在转录水平上进行调控[1]。miRNA通过与靶mRNA（messenger RNA）匹配结合实现对生物学功能的调控， 因此， 研究miRNA与其靶基因的调控关系成为生物界广泛关注的问题。传统的实验验证方法耗费巨大， 利用现有的序列数据、基因表达数据或其他生物信息学数据， 通过统计学模型或机器学习的方法构建基因调控网络来发现基因之间的关系， 能够有效减少实验花费， 对生物学研究者有一定指导作用。
从机器学习的角度来看， 基因调控网络构建可以分为非监督学习和监督学习。非监督学习不需要已知的调控关系， 只是利用一些生物数据来进行调控网络的构建； 监督学习则需要已知的调控关系， 可以看出监督学习需要的数据信息多于非监督学习， 具有更强的发现能力。有研究表明， 在网络推断方面， 监督学习优于非监督学习[2]。
监督学习需要利用已有的调控关系数据， 通过学习调控关系的判别模型， 对未知的调控关系进行判别， 需要处理特征生成和分类器选择问题。miRNA与其靶基因的交互特征包括自由能特征、结构序列特征和基于绑定位置特征， 收集这些特征并进行计算， 然后使用分类器进行模型的构建。由于支持向量机（Support Vector Machine， SVM）在解决小样本、非线性以及高维问题中表现出的优势[3]， 使得它在基因网络构建方面独具一格， 已成为近期的研究热点。
本文提出了一种基于粗糙集、混合粒子群和遗传算法（Genetic Algorithm， GA）的基因调控构建方法。首先利用序列数据构建特征向量， 然后使用所提方法选取最优的特征子集， 构建支持向量机模型。由于存在正负样本不平衡问题， 本文采用SMOTE （Synthetic Minority Oversampling TEchnique）[4] 算法对样本进行处理， 降低类不平衡的影响。在拟南芥和水稻数据集上的实验结果表明该方法可以得到较好的性能。
3 遗传算法
遗传算法是一种模拟达尔文生物进化论的自然选择和遗传学机制演化而来的随机化搜索方法[12]。 它采用概率化的寻优方法， 能自动获取和指导优化的搜索空间， 不需要确定的规则， 能够自适应的调整搜索方向， 已经被广泛应用到信号处理、组合优化和机器学习等领域。
遗传算法具有粒子群算法所没有的交叉和变异操作。交叉就是按照一个较大的概率从种群中选择两个个体， 交换两个个体的某个或某些位， 从而形成两个新的个体。交叉操作方法有单点交叉、两点交叉、多点交叉和顺序交叉等。常用的交叉算子是单点交叉算子， 是指在个体中随机设置一个交叉点， 然后在该点相互交换两个配对个体的部分染色体。
变异操作是模拟生物由于偶然的因素而引起基因突变的原理来进行的。它使用一个很小的变异概率随机将染色体中的某一位或某些位使用其他值进行替换， 从而形成一个新的个体。
4 基于粗糙集的PSO和GA的混合算法
虽然粒子群算法中粒子的学习能力很强， 节省时间并且容易实现。
但是存在一些缺点：比如局部搜索能力比较差、搜索的精度不高、容易陷入局部最优解等。因此， PSO算法和其他算法的融合是当前的研究热点。Li等[13]在2006年提出将模拟退火算法和PSO进行融合；Ye等[14]在2005年将演化策略的变异算子引入到了PSO中； 文献[15] 在SVM特征选择方面对PSO和GA进行融合。
本文将粒子群算法和遗传算法的交叉与变异算子进行融合。遗传算法个体之间不共享信息， 侧重自然寻优， 而粒子群之间共享信息， 因此搜索时间较快， 将二者的优点进行融合。在粒子群算法的执行过程中， 将基于粗糙集的依赖度作为特征选择的适应度函数， 对于适应度函数排名靠前的粒子使用粒子群算法的速度和位置更新公式进行更新， 而对排名靠后的粒子则采用遗传算法的交叉和变异算子进行粒子的更新， 提出基于粗糙集的混合粒子群和遗传算法的方法（PSOGARS）。
每个粒子是一个长为d的二进制位串， d是特征的总数， 每一位代表一个属性， “1”代表这个属性被选择， “0”代表这个属性没有被选择。
4.1 参数设置和适应度函数
惯性权重w影响着粒子群的搜索能力， 一般将惯性权重设置为随着迭代次数递减的函数， 这样在开始时可以有较大的搜索空间， 之后在一个较小的空间搜索， 提高收敛速度。公式如下： 4.2 PSOGARS方法流程
基于粗糙集的粒子群和遗传算法的混合算法过程如下：
第一步 设定算法的初始参数（种群规模、迭代次数、遗传算法的概率p、交叉和变异速率等）。
第二步 随机产生初始种群， 随机化粒子的速度和位置， 设置每个粒子的个体极值Pbest和全局极值gbest。
第三步 根据式（11） 计算每个粒子的适应值。
第四步 按照适应值的大小对粒子进行排序， 将排序前p的粒子， 根据式（8）和（9） 更新速度和位置值。对于排在p以后的那些粒子， 使用遗传算法的交叉和变异算子进行更新。
第五步 根据更新后的粒子再次计算适应度值， 确定粒子的个体极值Pbest和全局极值gbest。
第六步 判断是否满足迭代次数要求：如果是， 就转向第七步；否则转向第三步。
第七步 输出最优粒子的最优位置。
5 实验分析
5.1 数据集
拟南芥和水稻的miRNA数据下载自miRNA数据库miRBase （版本号21）[16]， 它包含了427条拟南芥miRNA成熟体。拟南芥mRNA数据下载自拟南芥数据库TAIR[17]。水稻的mRNA数据下载自Ensembl Genomes数据库（http：//plants.ensembl.org）。本文使用的正样本来自一些文献中搜集的实验验证的拟南芥miRNA靶基因交互数据[18-22]， 共101条。实验验证的水稻的miRNA靶基因交互数据共30条。因为实验验证的负样本数据缺乏， 因此一些负样本按照下面的步骤生成。
根据拟南芥miRNA中碱基比例PU=0.29， PC=0.19， PA=0.26， PG=0.26， 300个人工的miRNA（30nt）已经生成[23]，用这些生成的miRNA产生负样本。用psRNATarget[24]产生这些人工的miRNA的靶基因。最后， 1311条负的调控关系已经生成。miRNA与其靶基因的序列特征一般包括自由能、结构和位置方面的特征， 本文采用文献[25]的方式提取48维特征。在水稻数据集上采用同样的方法生成负样本。因为需要样本数据中有miRNA与mRNA的交互的靶位点信息， 利用psRNATarget工具得到的调控关系作为测试集。
5.2 数据预处理及参数设置
实验中， 由于正负样本的比例不平衡， 负样本的比例大于正样本的比例， 结果会出现较高的假阴性。本文采用经典的SMOTE方法解决样本的不平衡问题。SMOTE算法是一种过采样算法， 基本思想是通过合成的方法产生新的少数样本。合成的方法是对每个少数类样本a， 计算a与少数类样本之间的欧氏距离， 选取k个最短的距离作为其最近邻， 文中的k值为5。然后从它的最近邻中随机选择样本b， 然后在a和b之间的连线上随机选一点作为新合成的少数类样本M， 如式（12）所示， 其中u是一个介于0～1的随机数，并不是简单地进行复制。使用数据挖掘工具Weka[26]将连续属性值进行离散化处理， 以间距0.1为分割， 分成10份， 离散化后小于0.1的值都看作0， 0.1～0.2的值都看作0.1， 依此类推。
算法中的遗传概率p， 从0.1～0.9， 以0.1为步长连续取不同的值进行实验， 最终选取一组准确率最高时的p值作为最终的结果。
本文采用了3种分类性能评价指标， 分别是准确率、F值和受试者工作特征（Receiver Operating Characteristic， ROC）曲线面积。其中：
准确率=（TP+TN）/（TP+TN+FP+FN）
F值=（2*TP）/（2*TP+FP+FN）
ROC曲线是显示分类器真正率和假正率折中的一种图形化方法。在一个ROC曲线中， 真正率（True Positive Rate， TPR）沿y轴进行绘制， 而假正率（False Positive Rate， FPR）显示在x轴上， 沿着曲线每一点对应于一个分类器归纳的模型。ROC曲线面积是曲线下方的面积， 其取值范围为0～1。
其中：TP、TN、FP、FN分别表示真阳性、真阴性、假阳性和假阴性。
表1按照不同的p值选出不同的特征子集， 根据不同的特征子集采用支持向量机进行训练， 使用10倍交叉验证得到在拟南芥数据集上不同p值时的准确率、F值和ROC面积。本实验中， p值最终选择的是0.2。最大迭代次数Maxiter=100， 惯性权重的最大值和最小值分别是1.4和0.4。种群的大小N为特征的个数48， 遗传算法的交叉概率c=0.7， 变异概率m=0.01。
5.3 结果分析
本文方法PSOGARS与基于粗糙集和粒子群优化的特征选择方法（Feature Selection based on Rough Sets and PSO， PSORSFS）[27]、粗糙集软件（ROSETTA）[28]等算法进行比较分析。ROSETTA中采用的是利用遗传算法得到的属性约简方法。然后使用支持向量机对每种算法得到的特征子集对应的样本子集进行分类， 采用10折交叉验证比较这三种算法的性能。因为使用粗糙集软件一共得到了4个不同的属性约简子集， 文中取它们的平均值进行比较。表2为三种方法在拟南芥数据集上的性能比较。
使用同样的方法在水稻数据集上进行实验， 结果如表3所示。
从表2和表3中可以看到， 虽然三种方法约简后的特征个数相同， 但是本文方法的准确率略高于其他两种方法。对于拟南芥数据集来说， 分类的准确率， F值和ROC面积都比PSORSFS高5%， 比ROSETTA高1%。在水稻数据上， 比PSORSFS高1%， 比ROSETTA高8%。 5.4 网络构建
根据构建的分类模型， 得到miRNAmRNA的调控网络。图1给出了部分的调控关系。miR156调控的AT1G27360、AT3G57920、AT1G35515等大部分均有GO术语GO：0006355。AT1G35515也具有相同的生物过程， 因此， 它们很可能同时被相同的调控因子调控。这里， 实验验证的miR157的靶基因都具有同样的GO标签， 而预测的AT2G42200也有相同的GO标签。同时被miR156和miR157预测A8T3G18217拥有的GO标签GO：0035195和GO：0006355都是GO标签GO：0010467的后代， 所以它们很可能也有相同的功能， 被同样的调控因子调控。表4给出了这些实验验证的以及预测的miRNA的靶基因的GO术语及其功能。
6 结语
基于粗糙集理论， 本文将粒子群优化算法与遗传算法相结合， 提出了一种新的构建调控网络的方法。考虑到miRNA与其靶基因之间的序列信息， 提取序列之间的关系， 构造特征向量， 混合粒子群和遗传算法选择最优的特征子集， 使用SMOTE算法解决样本不平衡问题。使用支持向量机进行实验， 采用10折交叉验证来衡量模型的准确性。结果表明， 该方法可以有效地预测调控关系。今后， 可以考虑结合其他种类的生物学数据， 提高预测的准确率。
参考文献：
[1] RUVKUN G. Glimpses of a tiny RNA world[J]. Science， 2001， 294（5543）： 797.
[2] MADHAMSHETTIWAR P B， MAETSCHKE S R， DAVIS M J， et al. Gene regulatory network inference： evaluation and application to ovarian cancer allows the prioritization of drug targets[J]. Genome Medicine， 2012， 4（5）： 1-16.
[3] 亓慧，王文剑，郭虎升.一种基于特征选择的SVM Bagging集成方法[J]. 小型微型计算机系统， 2014， 35（11）： 2533-2537.（QI H， WANG W J， GUO H S. An SVM bagging ensemble learning algorithm based on feature selection[J]. Journal of Chinese Computer Systems， 2014， 35（11）： 2533-2537.）
[4] CHAWLA N V， BOWYER K W， HALL L O， et al. SMOTE： synthetic minority oversampling technique[J]. Journal of Artificial Intelligence Research， 2002， 16（1）： 321-357.
[5] PAWLAK Z. Rough sets[J]. International Journal of Computer & Information Sciences， 1982， 11（5）： 341-356.
[6] 常犁云， 王国胤， 吴渝. 一种基于Rough Set理论的属性约简及规则提取方法[J]. 软件学报， 1999， 10（11）：1207-1211. （CHANG L Y， WANG G Y， WU Y. An approach for attribute reduction and rule generation based on rough set theory[J]. Journal of Software， 1999， 10（11）： 1207-1211.）
[7] 石云， 孙玉芳， 左春. 基于Rough Set的空间数据分类方法[J]. 软件学报， 2000， 11（5）： 673-678. （SHI Y， SUN Y F， ZUO C. Spatial data classification based on rough set[J]. Journal of Software， 2000， 11（5）： 673-678.）
[8] PAWLAK Z. Imprecise Categories， Approximations and Rough Sets[M]. Boston， Massachusetts： Kluwer Academic Publishers， 1991： 9-26.
[9] PAUL S， MAJI P. Rough set based gene selection algorithm for microarray sample classification[C]// ICM2CS 2010： Proceedings of the 2010 International Conference on Methods and Models in Computer Science. Piscataway， NJ： IEEE， 2010： 7-13.
[10] KENNDY J， EBERHART R C. Particle swarm optimization[C]// Proceedings of the 1995 IEEE International Conference on Neural Networks. Piscataway， NJ： IEEE， 1995：1942-1948.
[11] EBERHART R C， KENNEDY J. A new optimizer using particle swarm theory[C]// Proceedings of the 6th International Symposium on Micro machine and Human Science. Piscataway， NJ： IEEE， 1995： 39-43. [12] HAYESROTH F. Review of "Adaptation in Natural and Artificial Systems by John H. Holland". The University of Michigan Press[J]. ACM SIGART Bulletin， 1975， 53： 15.
[13] LI L， WANG L， LIU L. An effective hybrid PSOSA strategy for optimization and its application to parameter estimation[J]. Applied Mathematics and Computation， 2006， 179（1）： 135-146.
[14] YE B， ZHU C， GUO C， et al. Generating extended fuzzy basis function networks using hybrid algorithm[C]// Proceedings of the Second international conference on Fuzzy Systems and Knowledge Discovery. Berlin： SpringerVerlag， 2005： 79-88.
[15] 张进， 丁胜， 李波. 改进的基于粒子群优化的支持向量机特征选择和参数联合优化算法[J]. 计算机应用， 2016， 36（5）：1330-1335.（ZHANG J， DING S， LI B. Improved particle swarm optimization algorithm for support vector machine feature selection and optimization for parameters[J]. Journal of Computer Applications， 2016， 36（5）： 1330-1335.）
[16] GRIFFITHSJONES S， SAINI H K， VAN DONGEN S， et al. miRBase： tools for MicroRNA genomics[J]. Nucleic Acids Research， 2008， 36（1）： 154-158.
[17] SWARBRECK D， WILKS C， LAMESCH P， et al. The Arabidopsis Information Resource （TAIR）： gene structure and function annotation[J]. Nucleic Acids Research， 2008， 36（Database issue）： D1009-D1014.
[18] ADDOQUAYE C， ESHOO T W， BARTEL D P， et al. Endogenous siRNA and miRNA targets identified by sequencing of the Arabidopsis degradome[J]. Current Biology， 2008， 18（10）： 758-762.
[19] ALLEN E， XIE Z， GUSTAFSON A M， et al. MicroRNAdirected phasing during transacting siRNA biogenesis in plants[J]. Cell， 2005， 121（2）： 207-221.
[20] GERMAN M A， PILLAY M， JEONG D H， et al. Global identification of MicroRNAtarget RNA pairs by parallel analysis of RNA ends[J]. Nature Biotechnology， 2008， 26（8）： 941-946.
[21] LIANG G， HE H， YU D. Identification of nitrogen starvationresponsive MicroRNAs in Arabidopsis thaliana[J]. PloS One， 2012， 7（11）： e48951.
[22] ALLEN E， XIE Z， GUSTAFSON A M， et al. Evolution of MicroRNA genes by inverted duplication of target gene sequences in Arabidopsis thaliana[J]. Nature Genetics， 2004， 36（12）： 1282-1290.
[23] SAETROM O L A， SNVE O L A， SAETROM P. Weighted sequence motifs as an improved seeding step in MicroRNA target prediction algorithms[J]. RNA， 2005， 11（7）： 995-1003.
[24] DAI X， ZHAO P X. psRNATarget： a plant small RNA target analysis server[J]. Nucleic Acids Research， 2011， 39（Web Server issue）： W155-W159.
[25] MENG J， SHI L， LUAN Y. Plant MicroRNAtarget interaction identification model based on the integration of prediction tools and support vector machine[J]. PloS One， 2014， 9（7）： e103181.
[26] HOLMES G， DONKIN A， WITTEN I H. WEKA： a machine learning workbench[C]// Proceedings of the 1994 2nd Australian and New Zealand Conference on Intelligent Information Systems. Piscataway， NJ： IEEE， 1994：357-361.
[27] WANG X， YANG J， TENG X， et al. Feature selection based on rough sets and particle swarm optimization[J]. Pattern Recognition Letters， 2007， 28（4）： 459-471.
[28] KOMOROWSKI J. ROSETTA-a rough set toolkit for analysis of data[C]// Proceedings of the 3rd International Joint Conference on Information Sciences. Berlin： Springer， 1997： 403-407.
摘 要：MicroRNA（miRNA）是一类大小为21～25nt的内源性非编码小核糖核酸（RNA）， 通过与mRNA的3’UTR互补结合， 导致mRNA降解或翻译抑制来调控编码基因的表达。为了提高构建基因调控网络的准确度， 提出一种基于粗糙集、融合粒子群（PSO）和遗传算法（GA）的基因调控网络构建方法（PSOGARS）。该方法首先通过对序列信息进行特征提取；然后采用粗糙集的依赖度作为适应度函数， 融合粒子群和遗传算法选出较优的特征子集；最后使用支持向量机（SVM）建立模型， 预测未知的调控关系。在拟南芥数据集上进行实验， 相比基于粗糙集和粒子群优化的特征选择方法和Rosetta算法， 所提方法的预测准确率、F值和受试者工作特征（ROC）曲线面积最多能提高5%， 在水稻数据集上最多能提高8%。实验结果表明所提方法能够比较准确地预测miRNA和靶基因之间的调控关系。
关键词：基因调控网络；粒子群优化；遗传算法；粗糙集；特征选择
中图分类号：TP399
文献标志码：A
文章编号：1001-9081（2016）11-2969-05
0 引言
MicroRNA（miRNA） 是一类非常重要的非编码核糖核酸（RiboNucleic Acid，RNA）分子， 通过诱导靶基因降解， 从而广泛地参与到基因的转录后调控， 或者通过抑制基因的转录， 对基因在转录水平上进行调控[1]。miRNA通过与靶mRNA（messenger RNA）匹配结合实现对生物学功能的调控， 因此， 研究miRNA与其靶基因的调控关系成为生物界广泛关注的问题。传统的实验验证方法耗费巨大， 利用现有的序列数据、基因表达数据或其他生物信息学数据， 通过统计学模型或机器学习的方法构建基因调控网络来发现基因之间的关系， 能够有效减少实验花费， 对生物学研究者有一定指导作用。
从机器学习的角度来看， 基因调控网络构建可以分为非监督学习和监督学习。非监督学习不需要已知的调控关系， 只是利用一些生物数据来进行调控网络的构建； 监督学习则需要已知的调控关系， 可以看出监督学习需要的数据信息多于非监督学习， 具有更强的发现能力。有研究表明， 在网络推断方面， 监督学习优于非监督学习[2]。
监督学习需要利用已有的调控关系数据， 通过学习调控关系的判别模型， 对未知的调控关系进行判别， 需要处理特征生成和分类器选择问题。miRNA与其靶基因的交互特征包括自由能特征、结构序列特征和基于绑定位置特征， 收集这些特征并进行计算， 然后使用分类器进行模型的构建。由于支持向量机（Support Vector Machine， SVM）在解决小样本、非线性以及高维问题中表现出的优势[3]， 使得它在基因网络构建方面独具一格， 已成为近期的研究热点。
本文提出了一种基于粗糙集、混合粒子群和遗传算法（Genetic Algorithm， GA）的基因调控构建方法。首先利用序列数据构建特征向量， 然后使用所提方法选取最优的特征子集， 构建支持向量机模型。由于存在正负样本不平衡问题， 本文采用SMOTE （Synthetic Minority Oversampling TEchnique）[4] 算法对样本进行处理， 降低类不平衡的影响。在拟南芥和水稻数据集上的实验结果表明该方法可以得到较好的性能。
3 遗传算法
遗传算法是一种模拟达尔文生物进化论的自然选择和遗传学机制演化而来的随机化搜索方法[12]。 它采用概率化的寻优方法， 能自动获取和指导优化的搜索空间， 不需要确定的规则， 能够自适应的调整搜索方向， 已经被广泛应用到信号处理、组合优化和机器学习等领域。
遗传算法具有粒子群算法所没有的交叉和变异操作。交叉就是按照一个较大的概率从种群中选择两个个体， 交换两个个体的某个或某些位， 从而形成两个新的个体。交叉操作方法有单点交叉、两点交叉、多点交叉和顺序交叉等。常用的交叉算子是单点交叉算子， 是指在个体中随机设置一个交叉点， 然后在该点相互交换两个配对个体的部分染色体。
变异操作是模拟生物由于偶然的因素而引起基因突变的原理来进行的。它使用一个很小的变异概率随机将染色体中的某一位或某些位使用其他值进行替换， 从而形成一个新的个体。
4 基于粗糙集的PSO和GA的混合算法
虽然粒子群算法中粒子的学习能力很强， 节省时间并且容易实现。
但是存在一些缺点：比如局部搜索能力比较差、搜索的精度不高、容易陷入局部最优解等。因此， PSO算法和其他算法的融合是当前的研究热点。Li等[13]在2006年提出将模拟退火算法和PSO进行融合；Ye等[14]在2005年将演化策略的变异算子引入到了PSO中； 文献[15] 在SVM特征选择方面对PSO和GA进行融合。
本文将粒子群算法和遗传算法的交叉与变异算子进行融合。遗传算法个体之间不共享信息， 侧重自然寻优， 而粒子群之间共享信息， 因此搜索时间较快， 将二者的优点进行融合。在粒子群算法的执行过程中， 将基于粗糙集的依赖度作为特征选择的适应度函数， 对于适应度函数排名靠前的粒子使用粒子群算法的速度和位置更新公式进行更新， 而对排名靠后的粒子则采用遗传算法的交叉和变异算子进行粒子的更新， 提出基于粗糙集的混合粒子群和遗传算法的方法（PSOGARS）。
每个粒子是一个长为d的二进制位串， d是特征的总数， 每一位代表一个属性， “1”代表这个属性被选择， “0”代表这个属性没有被选择。
4.1 参数设置和适应度函数
惯性权重w影响着粒子群的搜索能力， 一般将惯性权重设置为随着迭代次数递减的函数， 这样在开始时可以有较大的搜索空间， 之后在一个较小的空间搜索， 提高收敛速度。公式如下： 4.2 PSOGARS方法流程
基于粗糙集的粒子群和遗传算法的混合算法过程如下：
第一步 设定算法的初始参数（种群规模、迭代次数、遗传算法的概率p、交叉和变异速率等）。
第二步 随机产生初始种群， 随机化粒子的速度和位置， 设置每个粒子的个体极值Pbest和全局极值gbest。
第三步 根据式（11） 计算每个粒子的适应值。
第四步 按照适应值的大小对粒子进行排序， 将排序前p的粒子， 根据式（8）和（9） 更新速度和位置值。对于排在p以后的那些粒子， 使用遗传算法的交叉和变异算子进行更新。
第五步 根据更新后的粒子再次计算适应度值， 确定粒子的个体极值Pbest和全局极值gbest。
第六步 判断是否满足迭代次数要求：如果是， 就转向第七步；否则转向第三步。
第七步 输出最优粒子的最优位置。
5 实验分析
5.1 数据集
拟南芥和水稻的miRNA数据下载自miRNA数据库miRBase （版本号21）[16]， 它包含了427条拟南芥miRNA成熟体。拟南芥mRNA数据下载自拟南芥数据库TAIR[17]。水稻的mRNA数据下载自Ensembl Genomes数据库（http：//plants.ensembl.org）。本文使用的正样本来自一些文献中搜集的实验验证的拟南芥miRNA靶基因交互数据[18-22]， 共101条。实验验证的水稻的miRNA靶基因交互数据共30条。因为实验验证的负样本数据缺乏， 因此一些负样本按照下面的步骤生成。
根据拟南芥miRNA中碱基比例PU=0.29， PC=0.19， PA=0.26， PG=0.26， 300个人工的miRNA（30nt）已经生成[23]，用这些生成的miRNA产生负样本。用psRNATarget[24]产生这些人工的miRNA的靶基因。最后， 1311条负的调控关系已经生成。miRNA与其靶基因的序列特征一般包括自由能、结构和位置方面的特征， 本文采用文献[25]的方式提取48维特征。在水稻数据集上采用同样的方法生成负样本。因为需要样本数据中有miRNA与mRNA的交互的靶位点信息， 利用psRNATarget工具得到的调控关系作为测试集。
5.2 数据预处理及参数设置
实验中， 由于正负样本的比例不平衡， 负样本的比例大于正样本的比例， 结果会出现较高的假阴性。本文采用经典的SMOTE方法解决样本的不平衡问题。SMOTE算法是一种过采样算法， 基本思想是通过合成的方法产生新的少数样本。合成的方法是对每个少数类样本a， 计算a与少数类样本之间的欧氏距离， 选取k个最短的距离作为其最近邻， 文中的k值为5。然后从它的最近邻中随机选择样本b， 然后在a和b之间的连线上随机选一点作为新合成的少数类样本M， 如式（12）所示， 其中u是一个介于0～1的随机数，并不是简单地进行复制。使用数据挖掘工具Weka[26]将连续属性值进行离散化处理， 以间距0.1为分割， 分成10份， 离散化后小于0.1的值都看作0， 0.1～0.2的值都看作0.1， 依此类推。
算法中的遗传概率p， 从0.1～0.9， 以0.1为步长连续取不同的值进行实验， 最终选取一组准确率最高时的p值作为最终的结果。
本文采用了3种分类性能评价指标， 分别是准确率、F值和受试者工作特征（Receiver Operating Characteristic， ROC）曲线面积。其中：
准确率=（TP+TN）/（TP+TN+FP+FN）
F值=（2*TP）/（2*TP+FP+FN）
ROC曲线是显示分类器真正率和假正率折中的一种图形化方法。在一个ROC曲线中， 真正率（True Positive Rate， TPR）沿y轴进行绘制， 而假正率（False Positive Rate， FPR）显示在x轴上， 沿着曲线每一点对应于一个分类器归纳的模型。ROC曲线面积是曲线下方的面积， 其取值范围为0～1。
其中：TP、TN、FP、FN分别表示真阳性、真阴性、假阳性和假阴性。
表1按照不同的p值选出不同的特征子集， 根据不同的特征子集采用支持向量机进行训练， 使用10倍交叉验证得到在拟南芥数据集上不同p值时的准确率、F值和ROC面积。本实验中， p值最终选择的是0.2。最大迭代次数Maxiter=100， 惯性权重的最大值和最小值分别是1.4和0.4。种群的大小N为特征的个数48， 遗传算法的交叉概率c=0.7， 变异概率m=0.01。
5.3 结果分析
本文方法PSOGARS与基于粗糙集和粒子群优化的特征选择方法（Feature Selection based on Rough Sets and PSO， PSORSFS）[27]、粗糙集软件（ROSETTA）[28]等算法进行比较分析。ROSETTA中采用的是利用遗传算法得到的属性约简方法。然后使用支持向量机对每种算法得到的特征子集对应的样本子集进行分类， 采用10折交叉验证比较这三种算法的性能。因为使用粗糙集软件一共得到了4个不同的属性约简子集， 文中取它们的平均值进行比较。表2为三种方法在拟南芥数据集上的性能比较。
使用同样的方法在水稻数据集上进行实验， 结果如表3所示。
从表2和表3中可以看到， 虽然三种方法约简后的特征个数相同， 但是本文方法的准确率略高于其他两种方法。对于拟南芥数据集来说， 分类的准确率， F值和ROC面积都比PSORSFS高5%， 比ROSETTA高1%。在水稻数据上， 比PSORSFS高1%， 比ROSETTA高8%。 5.4 网络构建
根据构建的分类模型， 得到miRNAmRNA的调控网络。图1给出了部分的调控关系。miR156调控的AT1G27360、AT3G57920、AT1G35515等大部分均有GO术语GO：0006355。AT1G35515也具有相同的生物过程， 因此， 它们很可能同时被相同的调控因子调控。这里， 实验验证的miR157的靶基因都具有同样的GO标签， 而预测的AT2G42200也有相同的GO标签。同时被miR156和miR157预测A8T3G18217拥有的GO标签GO：0035195和GO：0006355都是GO标签GO：0010467的后代， 所以它们很可能也有相同的功能， 被同样的调控因子调控。表4给出了这些实验验证的以及预测的miRNA的靶基因的GO术语及其功能。
6 结语
基于粗糙集理论， 本文将粒子群优化算法与遗传算法相结合， 提出了一种新的构建调控网络的方法。考虑到miRNA与其靶基因之间的序列信息， 提取序列之间的关系， 构造特征向量， 混合粒子群和遗传算法选择最优的特征子集， 使用SMOTE算法解决样本不平衡问题。使用支持向量机进行实验， 采用10折交叉验证来衡量模型的准确性。结果表明， 该方法可以有效地预测调控关系。今后， 可以考虑结合其他种类的生物学数据， 提高预测的准确率。
参考文献：
[1] RUVKUN G. Glimpses of a tiny RNA world[J]. Science， 2001， 294（5543）： 797.
[2] MADHAMSHETTIWAR P B， MAETSCHKE S R， DAVIS M J， et al. Gene regulatory network inference： evaluation and application to ovarian cancer allows the prioritization of drug targets[J]. Genome Medicine， 2012， 4（5）： 1-16.
[3] 亓慧，王文剑，郭虎升.一种基于特征选择的SVM Bagging集成方法[J]. 小型微型计算机系统， 2014， 35（11）： 2533-2537.（QI H， WANG W J， GUO H S. An SVM bagging ensemble learning algorithm based on feature selection[J]. Journal of Chinese Computer Systems， 2014， 35（11）： 2533-2537.）
[4] CHAWLA N V， BOWYER K W， HALL L O， et al. SMOTE： synthetic minority oversampling technique[J]. Journal of Artificial Intelligence Research， 2002， 16（1）： 321-357.
[5] PAWLAK Z. Rough sets[J]. International Journal of Computer & Information Sciences， 1982， 11（5）： 341-356.
[6] 常犁云， 王国胤， 吴渝. 一种基于Rough Set理论的属性约简及规则提取方法[J]. 软件学报， 1999， 10（11）：1207-1211. （CHANG L Y， WANG G Y， WU Y. An approach for attribute reduction and rule generation based on rough set theory[J]. Journal of Software， 1999， 10（11）： 1207-1211.）
[7] 石云， 孙玉芳， 左春. 基于Rough Set的空间数据分类方法[J]. 软件学报， 2000， 11（5）： 673-678. （SHI Y， SUN Y F， ZUO C. Spatial data classification based on rough set[J]. Journal of Software， 2000， 11（5）： 673-678.）
[8] PAWLAK Z. Imprecise Categories， Approximations and Rough Sets[M]. Boston， Massachusetts： Kluwer Academic Publishers， 1991： 9-26.
[9] PAUL S， MAJI P. Rough set based gene selection algorithm for microarray sample classification[C]// ICM2CS 2010： Proceedings of the 2010 International Conference on Methods and Models in Computer Science. Piscataway， NJ： IEEE， 2010： 7-13.
[10] KENNDY J， EBERHART R C. Particle swarm optimization[C]// Proceedings of the 1995 IEEE International Conference on Neural Networks. Piscataway， NJ： IEEE， 1995：1942-1948.
[11] EBERHART R C， KENNEDY J. A new optimizer using particle swarm theory[C]// Proceedings of the 6th International Symposium on Micro machine and Human Science. Piscataway， NJ： IEEE， 1995： 39-43. [12] HAYESROTH F. Review of "Adaptation in Natural and Artificial Systems by John H. Holland". The University of Michigan Press[J]. ACM SIGART Bulletin， 1975， 53： 15.
[13] LI L， WANG L， LIU L. An effective hybrid PSOSA strategy for optimization and its application to parameter estimation[J]. Applied Mathematics and Computation， 2006， 179（1）： 135-146.
[14] YE B， ZHU C， GUO C， et al. Generating extended fuzzy basis function networks using hybrid algorithm[C]// Proceedings of the Second international conference on Fuzzy Systems and Knowledge Discovery. Berlin： SpringerVerlag， 2005： 79-88.
[15] 张进， 丁胜， 李波. 改进的基于粒子群优化的支持向量机特征选择和参数联合优化算法[J]. 计算机应用， 2016， 36（5）：1330-1335.（ZHANG J， DING S， LI B. Improved particle swarm optimization algorithm for support vector machine feature selection and optimization for parameters[J]. Journal of Computer Applications， 2016， 36（5）： 1330-1335.）
[16] GRIFFITHSJONES S， SAINI H K， VAN DONGEN S， et al. miRBase： tools for MicroRNA genomics[J]. Nucleic Acids Research， 2008， 36（1）： 154-158.
[17] SWARBRECK D， WILKS C， LAMESCH P， et al. The Arabidopsis Information Resource （TAIR）： gene structure and function annotation[J]. Nucleic Acids Research， 2008， 36（Database issue）： D1009-D1014.
[18] ADDOQUAYE C， ESHOO T W， BARTEL D P， et al. Endogenous siRNA and miRNA targets identified by sequencing of the Arabidopsis degradome[J]. Current Biology， 2008， 18（10）： 758-762.
[19] ALLEN E， XIE Z， GUSTAFSON A M， et al. MicroRNAdirected phasing during transacting siRNA biogenesis in plants[J]. Cell， 2005， 121（2）： 207-221.
[20] GERMAN M A， PILLAY M， JEONG D H， et al. Global identification of MicroRNAtarget RNA pairs by parallel analysis of RNA ends[J]. Nature Biotechnology， 2008， 26（8）： 941-946.
[21] LIANG G， HE H， YU D. Identification of nitrogen starvationresponsive MicroRNAs in Arabidopsis thaliana[J]. PloS One， 2012， 7（11）： e48951.
[22] ALLEN E， XIE Z， GUSTAFSON A M， et al. Evolution of MicroRNA genes by inverted duplication of target gene sequences in Arabidopsis thaliana[J]. Nature Genetics， 2004， 36（12）： 1282-1290.
[23] SAETROM O L A， SNVE O L A， SAETROM P. Weighted sequence motifs as an improved seeding step in MicroRNA target prediction algorithms[J]. RNA， 2005， 11（7）： 995-1003.
[24] DAI X， ZHAO P X. psRNATarget： a plant small RNA target analysis server[J]. Nucleic Acids Research， 2011， 39（Web Server issue）： W155-W159.
[25] MENG J， SHI L， LUAN Y. Plant MicroRNAtarget interaction identification model based on the integration of prediction tools and support vector machine[J]. PloS One， 2014， 9（7）： e103181.
[26] HOLMES G， DONKIN A， WITTEN I H. WEKA： a machine learning workbench[C]// Proceedings of the 1994 2nd Australian and New Zealand Conference on Intelligent Information Systems. Piscataway， NJ： IEEE， 1994：357-361.
[27] WANG X， YANG J， TENG X， et al. Feature selection based on rough sets and particle swarm optimization[J]. Pattern Recognition Letters， 2007， 28（4）： 459-471.
[28] KOMOROWSKI J. ROSETTA-a rough set toolkit for analysis of data[C]// Proceedings of the 3rd International Joint Conference on Information Sciences. Berlin： Springer， 1997： 403-407.