基于多解并行遗传算法预测RNA二级结构及假结.pdf

第44卷第2期2023年6月淮北师范大学学报（自然科学版）Journal of Huaibei Normal University(Natural Sciences)Vol.44 No.2Jun.2023基于多解并行遗传算法预测RNA二级结构及假结尹正胜1，崔梦琦1，徐成振1，吴晓敏2（1.淮北师范大学 计算机科学与技术学院，安徽 淮北 235000；2.淮北师范大学 生命科学学院，安徽 淮北 235000）摘要：非编码RNA功能通常与其结构密切相关，准确预测RNA的二级结构有助于揭示RNA的功能。在传统的遗传算法基础上，结合RNA二级结构和假结的特点，提出一种多解并行的遗传算法预测RNA二级结构和假结。首先构建茎区池和初始解集；然后根据RNA二级结构的基本特点建立目标函数、约束函数、自适应度函数和相应的遗传算子，基于初始解集中多条序列结构模型进行并行遗传迭代，预测最优RNA二级结构；然后在RNA二级结构基础上，使用遗传算法继续进行迭代和筛选，预测含假结的RNA二级结构。实验结果表明，该方法不仅可以解决大规模茎区的组合问题，还可以减少随机性。该方法与常用的预测假结的IPknot方法比较，对单序列RNA的结构预测结果正确率高且稳定。关键词：遗传算法；多解并行；RNA二级结构；假结；预测方法中图分类号：N 32文献标识码：A文章编号：2095-0691（2023）02-0063-070引言RNA二级结构主要是由茎区和环区组合形成的，而假结则是RNA二级结构中的一种特殊结构，介于二级结构和三级结构之间。有研究表明，生物分子在发挥特有功能时就要有对应的特定结构1，所以说，RNA结构决定其生物功能2。预测RNA二级结构就能够用来表征RNA结构、推断功能机制并设计新实验3。目前只有少量RNA结构被测定，只用序列就能快速预测RNA二级结构成为每个RNA生物学家的必备工具。另外，研究RNA的结构和功能还有助于研究疾病与基因的相互关系以及进行药物设计4。所以现在面对的挑战就是找到一种利用这些丰富的一级序列数据来预测潜在的二级结构和其功能的高效方法，因此必须使用计算方法进行大数据处理与预测才能达到要求。RNA二级结构预测已经有几十年的历史，虽然RNA二级结构预测算法取得很大进步，但假结预测正确率依然达不到要求。如Turner的最近邻模型5-6，通过对表征环路自由能参数求和来计算每个最近相邻环的自由能量，整个RNA二级结构的自由能通过对分解的最近邻环的自由能求和来计算。许多工具，包括Mfold/UNAfold7-8、RNAfold9-10和RNAstructure11-12都采用这种方法。最近，还开发基于机器学习的RNA二级结构预测方法。这些方法将大量RNA序列对及其参考二级结构作为训练数据，训练热力学参数的替代参数。以下方法属于使用机器学习的方法类别：CONTRAfold13、ContextFold14、MXfold215和SPOT-RNA16。虽然基于机器学习模型在预测精度方面取得极高的性能，但也有报道称该模型存在过拟合风险。启发式算法和遗传算法同样擅长解决各类组合优化问题。Asai17提出IPknot方法，使用启发式算法预测具有假结的RNA二级结构，由于其预测精度较高，IPknot已成为常用的预测假结方法。Chen18基于遗传算法提出一种考虑自由能和结构保守性的RNA二级结构预测方法，该方法不仅可以预测单一序列结构，而且可以同时对多条同源序列进行预测。Shi19等使用多种群辅助量子遗传算法预测RNA二级结构，其策略涉及在每次迭代中以协作方式一起进化的多种群，并且通过算子转移操作来执行不同种群之间的遗传交换。启发式算法和遗传算法可以解决大规模茎区组合问题，但该类方法预测结果有一定的随收稿日期：2023-03-20基金项目：安徽省自然科学基金项目（1908085QF286，2208085MC65）；闽南师范大学智能优化与信息处理重点实验室开放项目（ZNYH202003）作者简介：尹正胜（1995），男，安徽马鞍山人，硕士生，研究方向为生物信息学。通信作者：徐成振（1988），男，安徽淮北人，博士，副教授，研究方向为优化算法和RNA结构。淮北师范大学学报（自然科学版）2023年机性，不能够保证收敛到最优状态，也无法判断找到的解与最优解接近程度。本文基于传统遗传算法，结合RNA二级结构及假结特点，提出一种多解并行遗传算法预测RNA假结结构，首先根据假结的茎区相容性标准有效地预测出假结结构，将假结结构能量通过目标函数计算得出，再通过对种群进行复制、交叉、变异等过程，最后收敛到最适应茎区，得到最优解。1多解并行遗传算法模型1.1目标函数已知RNA序列，RNA种类未知，以预测的自由能最小RNA二级结构作为最优二级结构。计算预测出的RNA二级结构自由能公式如下。E总=i=1aE茎区i+i=1bi+i=1ci+i=1di+i=1ei+i=1fi（1）式（1）中，a、b、c、d、e、f分别表示 RNA二级结构中茎区、突环、内环、多分支环、发夹环、假结总个数，i、i、i、i、i分别表示在第i个突环、内环、多分支环、发夹环、假结的自由能。E茎区表示RNA二级结构的茎区能量。E总则是RNA二级结构的自由能总量，RNA二级结构总体自由能等于其各个结构单元自由能之和。单个RNA二级结构自由能通过式（1）都可以计算出来，因此寻找预测出的所有RNA二级结构中自由能最小的结构就是优化算法的目标函数，如式（2）所示：Emin=min(E1,E2,En)，（2）E1，E2，En表示每一条RNA二级结构的自由能，Emin表示所有二级结构中最小的自由能。1.2约束函数和适应度函数在RNA二级结构及假结预测中，其数学模型应建立在RNA结构特点上：任意发卡环，其未配对碱基数量必须3；任意茎区，必须至少包含2对配对碱基；每个碱基，在同一时刻，只能与另外一个碱基形成配对关系，即茎区相容；茎区的自由能量只与临近的碱基对相关；前后相邻的2个碱基不可形成配对；非假结茎区只可形成嵌套、并行结构，不能交叉；假结茎区要与二级结构中的茎区组成嵌套结构，2个假结茎区之间不构成嵌套，即假结茎区相容；任意假结结构，其配对碱基数量2；适应度函数：E(k+1)E(k)+2，（3）式中E(k)代表第k子代RNA二级结构的自由能，不符合适应度函数的个体将随遗传淘汰掉。通过适应度函数，可排除不符合的解，提高算法运行效率和准确性。1.3二级结构茎区池根据一条长度为n的RNA序列，建立M矩阵，M矩阵的行列为RNA序列的长度n，M矩阵的行与列均为RNA的序列，通过RNA碱基的配对方式，即A-U、U-A、G-C、C-G、G-U、U-G碱基配对方式，以行优先遍历，若满足配对，则M（i，j）=1，否则为0。遍历后得到一个RNA序列配对上三角矩阵M。在矩阵M中，一条斜线上的值连续为1的位置可以形成茎区，每个茎区记为S（i，j，k），其中（i，j）为茎区的起始配对位置，k为茎区在矩阵内所跨的位置数，k3，记Stems为从矩阵中找到的所有茎区，如下所示：Stems=S1,S2,Sn,|S()i,j:k。（4）每条茎区都是连续的碱基配对，通常情况下，茎区中碱基对越多则自由能越小，茎区自由能越小则越稳定。因此，茎区池中的茎区以k的大小从大到小进行初步排序。1.4初始解空间选择二级结构茎区池中的茎区进行相容性判断和嵌套判断之后，得到初始解Rank：Rank=S1，S2，,Sn|Si表示S中的第i条茎区。（5）当RNA碱基长度小于100 nt时，选取茎区池中前10个作为根茎区；当RNA碱基长度大于100 nt时，选取茎区池中前20个作为根茎区。将选择好的根茎区与余下的茎区进行相容性判断，组合出初始的RNA二级结构，构成初始解集。1.5遗传算子遗传算法进化的规则即为遗传算子。遗传算子包括选择算子、交叉算子和变异算子。1.5.1选择算子在茎区池中选取第i个茎区的概率大小按照式（6）进行：64第2期尹正胜等：基于多解并行遗传算法预测RNA二级结构及假结P=O不相容Eij=1nEj。第i个茎区与已有结构相容（6）其中：L为茎区长度，E为茎区能量，Ej代表相容茎区能量总和，Ei则代表第i个茎区能量。将所得初始解集按自由能大小从上到下排序，通过算法约束函数排除不符合的茎区。将剩下的茎区保存到种群，作为父代进行遗传。1.5.2交叉算子本研究以两点交叉形式进行结构的交叉替换，按选择概率和所选茎区位置设置两个或多个茎区替换的交叉点，然后交换2个父代个体在2个交叉点之间的结构。1.5.3变异算子变异操作是将已得到的RNA二级结构中的点和括号以一定的变异概率进行取反操作，本文的变异概率设为pm，pm0.001。2预测RNA二级结构和假结2.1预测RNA二级结构按概率选择茎区，对初始解集中的结构进行交叉遗传步骤，得到第一代子代，这时引用目标函数，计算出各个子代的能量E，以及判断是否满足适应度函数；然后对子代进行继续迭代遗传，直到所有子代解都不满足适应度函数为止，中间和最后进行随机变异，最后输出解空间中的每个解迭代过程中自由能最小的RNA结构。通过E（E1，E2，,En），进行最小自由能升序排序，排在最前面的为最终预测结果。2.2预测RNA最优假结结构基于预测得到的最优RNA二级结构S来预测最优假结结构。首先根据S中未配对碱基重新构建假结茎区池，方法同上。因构成假结的茎区之间不能嵌套，所以要在相容的基础上去除相互嵌套的假结茎区。假设挑选假结茎区池中的S1()i1,j1:k1与最优二级结构S可以相容，那么再将S1与假结茎区池做嵌套判断筛选，因假结茎区之间不可嵌套的性质，排除掉假结茎区池中与S1相互嵌套的茎区。嵌套判断如下所述，假设挑选作为可相容的茎区S1()i1,j1:k1和假结茎区池中S2()i2,j2:k2已经满足相容性，把S1与S2转换为二进制形式，S1：区域(i1-k1,i1)(j1,j1-k1)部分对应的碱基化为1，其余序列碱基化为0。得到与序列S长度一致的L位二进制一维数组r1。S2：区域(i2-k2,i2)(j2,j2-k2)部分对应的碱基化为1，其余序列碱基化为0。得到与序列S长度一致的L位二进制一维数组r2。C=r1r2（7）D=sum(find(C=1)，（8）其中D为二进制r1与r2按位相与之后的数值中1的个数，则S1与S2构成茎区非嵌套必满足下面的公式。D=0D=2k1。（9）当茎区S1与茎区S2满足以上条件相容时，将茎区S2加入到根茎区S1所在的结构中，构成新的结构S，以此类推，继续向下选一个新茎区S3，先判断新结构S与新茎区S3是否相容，再判断S中的茎区与S3不构成嵌套结构，就将S3合并到结构S中；如果不相容或相容但组成嵌套结构，则需要重新选择茎区池中的下一条茎区并做上述判断。直到构成的新结构S与茎区池中的剩余茎区均不相容时，得到构造的一条带假结的二级结构Knot。通过以上方式，分别用S2，S3,作为根茎区再次构造多条假结结构，并存放起来。K=Knot1,Knot2,Knotn|n表示以第n条茎区作为根茎区组成的假结。（10）通过目标函数，计算K=Knot1,Knot2,Knotn|n自由能E1，E2，En，以自由能大小升序排序。自由能能量最小的假结结构即为预测最优的假结结构。65淮北师范大学学报（自然科学版）2023年3实验结果与分析使用本文提出的多解并行遗传算法和IPknot方法分别预测RNA的二级结构，并比较预测结果。IPknot是常用的预测带假结RNA二级结构的方法，其预测精度较高，而其余大部分预测方法都无法预测假结。从RNA STRAND和RNA FRABASE数据库中选取RNA真实结构数据进行预测比较，数据库中的数据较少，且大部分数据没有假结结构，另有部分数据的序列或结构重复，可用数据较少，因此进行比较之后，选择26组含有假结且序列和结构没有重复的数据进行实验，其中包含不同序列长度、不同茎环结构和不同假结结构的数据。如表1和表2所示，L为序列长度；EP为真实二级结构中碱基对的个数，即期望值；SUM为本文算法预测出的RNA二级结构及假结的碱基对总数；TP为预测到含假结二级结构中正确碱基对数；FP为预测到的错误的碱基对数；FN为预测错误的游离碱基个数；TN为正确预测到的没有配对的游离碱基数；SS为本文算法预测的敏感性；SP为本文算法预测的特异性；MCC为本文算法预测的马修兹相关系数值。表1本文的算法预测结果PDB id1L2X1F271KAJ2JLT1F5U1BJ21YMO2M8K2K951E8O1R9T2B571CX01Y261B231G592CSX1SJ41VC62GIS1U6P2H0S1U6B1Y0Q1X8W2A2EaverageNDB idUR0020DR00051KAJ2JLT1F5U1BJ21YMO2M8K2K951E8OPH0007UR0070PR0010UR0051PR0004PR0035PR0161PR0123PR0120UR00821U6PUR0091PR0133UR0048UR0041UR0064L2830323436404748485052667272747575767696101151222233247300EP81181616201517151917232225192121221427344760577070SUM81181616201520151818222423222021231723364956567277TP81181616201516151814191522192020171122342251475252FP00000004004391301661227592025FN0000000200155202222130720141925TN128162401781813131824263031313042312956118121103146SS1.0001.0001.0001.0001.0001.0001.0000.8001.0001.0000.7780.8640.6250.9570.8641.0000.9520.7390.6470.9570.9440.4490.9110.8390.7220.6750.874SP1.0001.0001.0001.0001.0001.0001.0000.8001.0001.0000.7780.8640.6250.9570.8641.0000.9520.7390.6470.9570.9440.4490.9110.8390.7220.6750.874MCC1.0001.0001.0001.0001.0001.0001.0000.5771.0001.0000.7020.6480.4650.8820.8860.9240.8850.7020.6590.6280.9400.3830.7200.7180.5680.5290.800表1是使用本文算法预测含假结的RNA二级结构结果，结果显示该方法预测短序列RNA二级结构准确度普遍较高，预测长序列RNA二级结构准确度相对较低。表2中是IPknot预测RNA含假结二级结构的预测结果。从表2中可看出，该方法对二级结构预测的准确性普遍较低，仅在短序列预测中表现较好，当碱基序列高于70后，IPknot预测的准确性急速下降。例如，序列长度为75 nt，预测正确率为88.5%，序列长度为76 nt，预测正确率为14.5%。图13是本文的算法和IPknot对RNA二级结构预测在敏感性（SS）、特异性（SP）、MCC值拟合曲线图，由图可知，本文的算法预测正确率明显高于IPknot的预测结果。当碱基长度高于150 bp时，IPknot的拟合曲线整体低于0.5，而本文的算法依然保持0.7以上，随着序列长度的增加，2种方法的敏感性、特异性、MCC值均出现不同程度的下降，但是本文的算法下降较慢，预测准确性较为稳定，而IPknot方法预测结果的波动性较大。图4是本文的算法和IPknot方法对RNA二级结构预测的MCC值对比，其中圆形代表本文的算法预测相同数据时MCC值更高，星形代表IPknot方法预测的MCC值更高，可以观察到散点集66第2期尹正胜等：基于多解并行遗传算法预测RNA二级结构及假结中分布在左上方（圆形较多），代表本文算法预测的RNA二级结构质量更高，更接近真实结构。表2IPknot预测结果PDB id1L2X1F271KAJ2JLT1F5U1BJ21YMO2M8K2K951E8O1R9T2B571CX01Y261B231G592CSX1SJ41VC62GIS1U6P2H0S1U6B1Y0Q1X8W2A2EaverageNDB idUR0020DR00051KAJ2JLT1F5U1BJ21YMO2M8K2K951E8OPH0007UR0070PR0010UR0051PR0004PR0035PR0161PR0123PR0120UR00821U6PUR0091PR0133UR0048UR0041UR0064L2830323436404748485052667272747575767696101151222233247300EP81181616201517151917232225192121221427344760577070SUM5100161417920152017242122212221201723343559687283TP5100161409161515101272014212071122232232323550FP000001704057121427111361111327363733FN621604612204691710822182134742344218TN12816240168186101214162429311842312952756360119SS1.0001.00001.0001.00001.0000.8001.0000.7500.5880.5000.3330.9090.6670.9550.9520.3500.6470.9570.6760.6290.5420.4710.4860.6020.685SP1.0001.00001.0001.00001.0000.8001.0000.7500.5880.5000.3330.9090.6670.9550.9520.3500.6470.9570.6760.6290.5420.4710.4860.6020.685MCC0.5500.81601.0000.6241.0000.4950.5771.0000.3420.2130.0710.2120.5400.4140.8850.8850.1450.6590.6280.5660.5340.1750.1210.0740.4940.473图1预测结果敏感性（SS）拟合曲线图2预测结果特异性（SP）拟合曲线67淮北师范大学学报（自然科学版）2023年图3预测结果MCC值拟合曲线图4MCC值比较图4结论本文基于多解并行遗传算法构造RNA二级结构及假结的预测模型。使用本文算法预测出的二级结构减少错误配对的数目，预测到的碱基对及假结更接近真实结构，在敏感性及特异性上结果更好，与常用于预测带假结的RNA二级结构的IPknot方法相比更接近期望值。与IPknot方法一样，随着序列长度变长，算法的误差则越大，准确率越低，但是本文的算法较为稳定。同时，当RNA真实的二级结构越简单，预测的准确性越高，游离碱基及环状结构越少，预测越准确。当然，在预测的准确性上，还有发展和改进的空间，特别是在结构中存在短假结结构时难度较大，此种结构一直是预测的难题。未来，可从假结的生物属性、机器学习、深度学习等角度，结合各算法的优势，进一步提高预测带假结RNA二级结构的准确性。参考文献：1王曦，汪小我，王立坤，等.新一代高通量RNA测序数据的处理与分析 J.生物化学与生物物理进展，2010，37（8）：834-846.2HU Xichan，KIM J K，YU C，et al.Quality-control mechanism for telomerase RNA folding in the cell J.Cell Reports，2020，33（13）：108568.3GANDHAR M，ARAUJO T R D C，HAN W，et al.RSCanner：rapid assessment and visualization of RNA structure contentJ.Bioinformatics，2023，39（3）：1-3.4唐超智，黄召怡，张玉玲.RNA的结构，功能及应用 J.生物学教学，2022，47（1）：88-91.5 SCHROEDER S J，TURNER D H.Optical melting measurements of nucleic acid thermodynamicsJ.Methods inEnzymology，2009，468：371-387.6TURNER D H，MATHEWS D H.NNDB：the nearest neighbor parameter database for predicting stability of nucleic acidsecondary structure J.Nucleic Acids Research，2009，38（Database issue）：D280-D282.7ZUKER M.Mfold web server for nucleic acid folding and hybridization prediction J.Nucleic Acids Research，2003，3168第2期尹正胜等：基于多解并行遗传算法预测RNA二级结构及假结（13）：3406-3415.8MARKHAM N R，ZUKER M.UNAFold：software for nucleic acid folding and hybridizationJ.Methods in MolecularBiology，2008，453：3-31.9HOFACKER I L.Vienna RNA secondary structure server J.Nucleic Acids Research，2003，31（13）：3429-3431.10LORENZ R，BERNHART S H，SIEDERDISSEN C H Z，et al.ViennaRNA package 2.0 J.Algorithms for MolecularBiology，2011，6（1）：26.11MATHEWS D H，ANDRE T C，KIM J，et al.An updated recursive algorithm for RNA secondary structure prediction withimproved thermodynamic parameters J.ACS Symposium Series，1998，682：246-257.12REUTER J S，MATHEWS D H.RNA structure：software for RNA secondary structure prediction and analysis J.BMCBioinformatics，2010，11（1）：873.13DO C B，WOODS D A，BATZOGLOU A S.CONTRAfold：RNA secondary structure prediction without physics-basedmodels J.Bioinformatics，2006，22（14）：e90-8.14ZAKOV S，GOLDBERG Y，ELHADAD M，et al.Rich parameterization improves RNA structure prediction J.Journal ofComputational Biology：A Journal of Computational Molecular Cell Biology，2011，18（11）：1525-1542.15AKIYAMA K.A max-margin training of RNA secondary structure prediction integrated with the thermodynamic modelJ.Journal of Bioinformatics and Computational Biology，2018，16（6）：1840025.16SINGH J，HANSON J，PALIWAL K，et al.RNA secondary structure prediction using an ensemble of two-dimensionaldeep neural networks and transfer learning J.Nature Communications，2019，10：5407.17ASAI K.IPknot：fast and accurate prediction of RNA secondary structures with pseudoknots using integer programmingJ.Bioinformatics，2011，27（13）：i85-i93.18CHEN J H，LE Shuyun，MAIZEL J V.Prediction of common secondary structures of RNAs：a genetic algorithm approachJ.Nucleic Acids Research，2000，28（4）：991-999.19SHI Sha，ZHANG Xinli，ZHAO Xianli，et al.Prediction of the RNA secondary structure using a multi-population assistedquantum genetic algorithm J.Human Heredity，2019，84（1）：1-8.Prediction of RNA Secondary Structure and Pseudoknot based on Multi-solution Parallel Genetic AlgorithmYIN Zhengsheng1，CUI Mengqi1，XU Chengzhen1，WU Xiaomin2（1.School of Computer Science and Technology，Huaibei Normal University，235000，Huaibei，Anhui，China；2.School of Life Sciences，Huaibei Normal University，235000，Huaibei，Anhui，China）Abstract：Non-coding RNA function is usually closely related to its structure，and accurate prediction ofRNA secondary structure can help reveal the function of RNA.In this paper，a multi-solution parallel geneticalgorithm for predicting RNA secondary structure and pseudoknot is proposed based on the traditionalgenetic algorithm，combining the characteristics of RNA secondary structure and pseudoknot.Firstly，thestem region pool and initial solution set are constructed；then the objective function，constraint function，adaptive degree function and corresponding genetic operators are established according to the characteristicsof RNA secondary structure，and the optimal RNA secondary structure is predicted by parallel geneticiteration based on multiple sequence-structure models in the initial solution set；Based on the RNAsecondary structure，the genetic algorithm is then used to continue iteration and screening to predict theRNA secondary structure containing pseudoknot.The experimental results show that this method can notonly solve the combination problem of large-scale stem regions，but also reduce the paredwith the IPknot method，this method is more acourate and stable in predicting the structure of single sequeceRNA.Key words：genetic algorithm；multi-solution parallelism；RNA secondary structure；pseudoknot；predictionmethod69