史巧硕，马 岱，米少华

（1.河北工业大学 计算机科学与软件学院，天津 300401；2.河北工业大学 教务处，天津 300401）

0 引言

MicroRNA是一类长度约为20～40个核苷酸的非编码RNA.它可通过分裂或者翻译抑制靶mRNA来达到调控基因的目的.人类全部基因的三分之一都受到microRNA调控，它不仅与生物早期发育、细胞增殖死亡，分化、脂肪代谢等生物过程有关，还与癌症有着紧密的联系.同时，它们也广泛存在于55个物种[1]之中.

目前，通过对m iRNA的研究表明，被鉴定出来的m iRNA的数量比实际存在的要少的多，还有大量的miRNA有待发现.而目前已知的m iRNA预测主要有两种方式，即cDNA克隆预测方法和计算预测方法.前者是microRNA早期主要的预测方式，这种方式直接、可靠,但缺点很明显，如很难克隆出在不同时期表达或只在特定组织或细胞系中表达的m iRNA，这是由于预测方式本身固有的只能捕获高丰度m icroRNA所造成的.后者是目前比较流行的预测m icroRNA的途径，其主要的优点是预测不会受到m iRNA在表达时间、组织特异性及表达水平的影响，以便弥补cDNA克隆测序方法造成的不足.其中，基于机器学习的方法是近几年来使用比较普遍的预测m icroRNA的方法[2].它不仅需要已知的m icroRNA，还需要已知的“非microRNA”，然后通过阳性和阴性数据集来构建能够区分二者的分类器.由于支持向量机(SupportVector Machines,SVMs)方法在逼近和泛化能力方面均具有良好的性能，目前大多数m iRNA预测方法采用SVM训练分类器，也有少数预测方法采用其他机器学习方法训练分类器，如随机森林(Random Forest)方法、隐马尔可夫模型(Hidden Markov Model,HMM)和Naive贝叶斯分类器 (Naive Bayes Classifier).

考虑到SVM分类器的性能受核函数和相关参数的影响很大，因而本文提出采用蚁群算法(AntColony A lgorithm,ACA)搜索SVM的相关参数，以构建无偏、且同时具有较高敏感性和特异性的分类器[3].

1 基于蚁群和支持向量机的m icroRNA预测方法

1.1 蚁群算法

蚁群算法是受到对真实蚁群觅食行为启发而提出的一种进化论算法.该算法通过蚂蚁个体间外激素的诱导作用，逐步寻找求解问题的全局最优解.由于其算法本身固有的并发性和可扩充性，非常适合于约束条件下二次优化问题的求解[4].

1.2 支持向量机

支持向量机是根据结构风险最小化原则，引入VC维及最优化理论来解决模式识别问题的一种机器学习算法.针对神经网络在解决分类问题时常常容易出现过学习而导致泛化能力差的情况，支持向量机寻找的是线性空间中的最优超平面[5].如图1所示.

图中圆圈和矩形框分别代表两类样本，中间的实线为分类线，而两条虚线之间的距离为分类间隔.落在两条虚线上的样本为支持向量.为了找到最优超平面以达到最佳的泛化性能，就需要使分类间隔尽量大，即使线性可分的样本集S满足

图1 线性可分空间的分类超平面Fig.1 Hyperplanes in linear separable space

其分类超平面为

2 实验

2.1 数据采集

阳性数据集选取m iRBase 14的718条已被报道的人类的pre-m iRNA.通过筛选，去除那些不存在发夹结构或者多环序列，得到646个人类pre-m iRNA作为人类阳性数据集.随机抽取其中的495条作为训练集，余下的151条作为测试集.目前发现的绝大多数的m iRNA都位于基因间区域，基因内的一些序列，即使它们具有与真正pre-m iRNA相似的某些特性，但它们仍是假的pre-m iRNA.因此可以从基因内区域提取一些序列作为阴性数据集的来源.选择从UCSC数据库中提取人类蛋白编译区的RefSeq序列，然后用RNAfold软件计算出这些序列的二级结构，选择具有以下3个条件的片段作为阴性数据集CODING：1）茎环结构中核苷酸配对数不少于18个，包括GU配对；2）MFE小于-15kcal/mol；3）没有多环.最后，共收集到5687条阴性pre-miRNA.本文从中随机抽取485条和155条序列分别作为阴性训练集和测试集.

2.2 特征提取

首先采用85个序列特征和9个结构特征描述整个样本，具体如下：1）一、二、三联碱基组成，共有84个；2）环的个数、最大环的大小、最小环的大小、大小分别为1到10nt的内部环的个数、大小小于6nt的内部环的个数、大小大于10 nt的内部环的个数、配对数、最低自由能、序列长度及GC个数，共计10个特征.其中，前9个结构特征是采用RNA fold折叠序列后在其二级结构中提取.

经验表明，pre-m iRNA二级结构中的局部邻近结构在预测中起着很大的作用，因此再采用罗迪的左三元编码方法[6]对pre-m iRNA进行特征提取.如图2所示，每3个相邻的核苷酸组成1个编码单元，每个核苷酸有匹配和不匹配两种状态.“(”表示匹配，“.”表示不匹配.提取每个编码单元对应的第1个核苷酸，同该编码单元共同组成结构序列的左三元子，如图2中(((表示一个左三元子，共有4×2×2×2=32种形式的左三元子.

这里，仅考虑pre-m iRNA茎部分的信息.图2中，序列的左右分别为5'端和3'端.m iRNA合成过程中，由Dicer酶剪切pre-m iRNA形成双螺旋结构，将其两条链的3'端的两个游离核苷酸也应用于miRNA预测.从两端的第一个“(”到最后一个“(”进行编码，对于最后一个“(”后面添加两个非匹配的核苷酸，标识为“(..”，表示含有两个自由核苷酸的结构.

图2 编码提取pre-miRNA特征Fig.2 Extracting pre-m iRNA featuresby coding

2.3 蚁群算法寻优SVM中形变控制参数与惩罚因子的思路流程

图3 实验流程Fig.3 Experimental flow chart

2.4 实验结果分析

图4是蚁群算法寻优支持向量机中的惩罚因子C与形变参量g的过程中测试误差的变化图.其中蚁群规模为10，最大迭代次数为20，最终寻找到的C为139，g为0.0619.本文同时使用WEKA机器学习平台对所选实验的学习和测试数据用J48决策树分类算法与RBF神经网络算法进行对比实验，训练和测试集的最终精度如表1所示.

通过表1中的数据可以明显看出，使用蚁群算法与支持向量机分类算法相结合的方法对m iRNA进行学习和测试的效果优于J48决策树和RBF神经网络.

表1 ACO+SVM与J48、RBF神经网络对比Tab.1 Comparison of ACO+SVM,J48 and RBF

图4 蚁群寻优SVM参数的过程Fig.4 Processof AntColony optim izing SVM parameters

3 结论

随着信息量的剧增和数据挖掘技术在各个领域的广泛应用，利用数据挖掘技术挖掘生物领域的知识并进行预测已成为当前研究的热点.本文针对m icroRNA的预测问题，基于SVM分类器逼近和泛化能力方面的优势并与蚁群算法结合，提出了基于蚁群和支持向量机的m icroRNA预测方法，并进行了实验分析.文中首先提取特征数据，而后使用蚁群算法寻优支持向量机参数，找到参数后生成模型，最后利用模型进行了分类测试.实验结果验证了该算法的正确性和有效性.由此得出，基于蚁群和支持向量机的m icroRNA预测方法具有一定的理论意义和研究价值.

[1]YimeiCai，Xiaom in Yu，SongnianHu，etal.A brief review on the mechanisms of miRNA regulation[J].Genom ics，Proteomicsamp;Bioinformatics，2009，7（4）：147-154.

[2]Mendes N D，Freitas A T，SagotM F.Current tools for the identification of miRNA genes and their targets[J].Nucleic Acids Research，2009，37（8）：2419-2433.

[3]M inh HoaiNguyen，Fernando de la Torre.Optimal featureselection for supportvector machines[J].Pattern Recognition，2010，43（3）：584-591.

[4]Xiaoxia Zhang，Lixing Tang.A new hybrid ant colony optim ization algorithm for the vehicle routing problem[J].Pattern Recognition Letters，2009，30（9）：848-855.

[5]Samad Jahandideh，Parviz Abdolmaleki.Prediction of melatonin excretion patterns in the ratexposed to ELFmagnetic fieldsbased on supportvector machine and linear discri minantanalysis[J].Micron，2010，41（7）：882-885.

[6]罗迪.基于支持向量机的m iRNA预测及其靶基因预测 [D].长春：吉林大学，2009，4：19-20.

[7]Nan Zhao，ZhiluWu，Yaqin Zhao.Antcolony optimization algorithm with mutation mechanism and itsapplications[J].ExpertSystemsw ith Applications，2010，37（7）：4805-4810.

[8]Jan Eggers，Dom inique Feillet.Optimization of thekeyboard arrangement problem usingan AntColonyalgorithm[J].European JournalofOperational Research，2003，148（3）：672-686.