遗传算法和模拟退火预测RNA结构的框架及其性能比较

沙特国王大学学报基于遗传算法和模拟退火的RNA结构预测框架马里兰州Shahidul Islama，Md.RafiqulIslam aa孟加拉国库尔纳大学计算机科学与工程学科，Khulna 9208阿提奇莱因福奥文章历史记录：收到2019年2020年3月5日修订2020年3月9日接受2020年3月19日网上发售保留字：RNA结构遗传算法模拟退火混合算法伪结预测A B S T R A C T具有伪结点的RNA结构预测是一个NP完全问题，需要计算一个能量最小的最优RNA结构。在过去的几十年里，已经开发了几种方法来预测RNA结构的伪结。其中，元启发式方法已被证明是有益的预测长RNA结构在很短的时间。本文采用遗传算法（GA）和模拟退火算法（SA）两种遗传算法对具有假结的RNA二级结构进行预测。我们还应用了这两种算法的组合作为GA-SA，其中GA用于全局搜索和SA用于局部搜索，反之SA-GA，其中SA用于全局搜索和GA用于局部搜索。用四种不同的能量模型计算了RNA结构的能量五个数据集，从RNA链和Pseudobase++数据库构建算法的性能进行了比较，与现有的几个元启发式算法。在这里，我们已经得到的GA和SA的组合（GA-SA）给出了更好的结果比GA，SA和SA-GA算法和所有其他四个最先进的算法在所有数据集上。©2020作者（S）。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍核糖核酸（RNA）是所有活细胞中发现的重要生物聚合物。它由四种核苷酸组成：腺嘌呤（A）、鸟嘌呤（G）、胞嘧啶（C）和尿嘧啶（U）。RNA二级结构涉及通过形成规范（A-U，G-C）碱基对和非规范（G-U）碱基对来折叠分子（El Fatmi等人，2017年;Tong等人，2013年a）。RNA的主要作用是转录和翻译。RNA聚合物在细胞过程中还具有许多重要的功能，如携带遗传信息、参与基因表达调控、作为催化 剂 等 。 预 测 RNA 结 构 的 物 理 方 法 如 X 射 线 晶 体 学 和 核 磁 共 振（NMR）是昂贵且耗时的（El Fatmi等人， 2017; Shapiro等人，2007; Cheong等人，2004年; Al-Khatib等人， 2010年）。一个伪-*通讯作者。电子邮件地址：shahidcseku@gmail.com（马里兰州）Shahidul Islam）。沙特国王大学负责同行审查结是RNA二级结构，其中茎的未配对的尾随核苷酸与茎的未配对的内部区域配对。形式上，如果存在两个茎S1（i，j）和S2（k，l），使得它们重叠（i< k< j< l），则该结构被称为伪结（Tong等人，2013年a）。图1显示了包括假结的RNA结构。RNA假结存在于许多类型的RNA中。因此，识别RNA的假结结构对于正确理解其功能是非常重要的在这里，我们将RNA假结结构预测问题表示为RNA-PSPP。存在几种用于具有伪结的RNA二级结构预测的计算方法，其在非常短的时间内预测结构（Tong等人，2013 b; Sato等人，2011;Reeder等人，2007年）。例如，在pknotsRG软件中折叠1000个核苷酸需要10分钟Rivas和Eddy（Rivas andEddy，1999）首先介绍了一种基于自由能最小化的动态方法，其多项式复杂度为O（n6）。这在实践中很难使用，特别是对于较长的RNA序列。启发式方法（El Fatmi等人，2017年; Tong等人，2013 a; Kai和Yulin，2018）在很短的时间内给出了令人满意的结果。然而，他们中的大多数没有考虑长RNA序列（例如，长度大于200的序列 其中一些（El Fatmi等人，2017年; Kai和Yulin，2018年）使用了一些序列来测试预测准确性。https://doi.org/10.1016/j.jksuci.2020.03.0051319-1578/©2020作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.com马里兰州Shahidul Islam，MD.Rafiqul Islam/ Journal of King Saud University913XX×Fig. 1.简单伪结的图形视图。该图像使用VARNA（Darty等人， 2009年）。遗传算法和模拟退火算法是两种有效的和流行的元启发式算法。提出了一种改进局部搜索启发式的模拟退火算法。它可以用作局部搜索或全局搜索元启发式。遗传算法主要用于全局搜索（Blum和Roli，2003）。模拟退火和遗传算法已经在几个工作中使用（El Fatmi等人，2017年; Tong等人，2013 a，b; Kai和Yulin，2018; Tsang和Wiese，2008）预测RNA假结结构。在本文中，我们提出了两种方法来预测RNA结构，包括伪结。第一种方法是采用遗传算法和模拟退火算法，另一种是这两种算法的混合。我们采用两种混合算法。第一种方法是用遗传算法进行全局搜索，用模拟退火算法进行局部搜索。第二种方法是用模拟退火算法进行全局搜索，用遗传算法进行局部搜索。我们的主要目标是研究遗传算法和SA算法以及GA和SA算法。工作的贡献如下：1. 设计了RNA-PSPP的三个遗传算子，以找到能量最小的稳定结构2. 关于RNA-PSPP的SA算子的重新设计3. 将遗传算法和模拟退火算法相结合，提出了两种求解RNA-PSPP的混合算法。4. 实施四种能源模式。所提出的工作使用特纳模型（Mathews等人，1999）、CC06（Cao和Chen，2006）、CC09（Cao和Chen，2009）和LongPK（Sperschneider和Datta，2010）模型。2. 目标函数RNA 结 构 的 稳 定 性 取 决 于 吉 布 斯 自 由 能 DG （ Neethling 和Engelbrecht，2006）。因此，RNA结构预测的目标是使DG最小化。其表示如下：E¼min DGi;1≤i≤n1其中n是序列的可能二级结构的数目。无假结的RNA二级结构的DG可称为使用以下函数计算（Montaseri等人， 2016年）。DG¼ DG柄部D G环部DG环部我 们 使 用 Turner 1999 最 近 邻 （ NNDB ） 参 数 （ Turner 和Mathews，2009）计算自由能。使用NNDB参数的能量计算示例见第4.2节。一个假结包含三个环（L1，L2，L3）和两个茎（S1，S2）.图1显示了长度为S1= 3，S2= 4，L1= 1，L2= 0，L3= 2的RNA假结。对于伪结能量计算，我们使用了三种能量模型。螺旋间环（L2）长度的假-结有助于确定哪个能量模型应当用于相应的伪结候选。对于螺旋间环长度使用0至1 CC06（Cao和Chen，2006）和用于环路长度2至6 CC09（Cao和Chen，2009）的能量模型。对于大于6的螺旋间环（L2），目前还没有可用的物理环熵模型。因此，对于循环长度7至50，使用称为LongPK（Sperschneider和Datta，2010）的启发式能量模型。我们的算法可以处理1L1100的结构，0 L2 50和2 L3 50。对于赝结，自由能DG计算如下（Cao和Chen，2009）：DGS1;S2;L1;L2;L3DGS1DGS2-TDSL1;L2;L33其中DGS1和DGS2是S1和S2的堆叠能，并且TDS（L 1，L 2，L 3）是L1，L2和L3的循环熵。循环熵TDS（L1，L2，L3）计算如下：对于CC 06（Cao andChen，2006），TDSL1;L2;L3TDSL1TDSL3-DGcs-DGassembly4其 中 DG cs 是 同轴堆叠的 自 由 能 ， DG assemble= 1.3 k cal/mol（37 °C）。对于CC09（Cao和Chen，2009），TDSL1;L2;L3其中l是螺旋间环长度（L2），a和b是由（Serra和Turner，1995）提供的参数。对于LongPK（Sperschneider和Datta，2010年），TDSL1;L2;L3ab×L6其中a = 7.0千卡/摩尔，b = 0.1千卡/摩尔，L = L1+ L2+ L3。3. 文献调查近年来，已经针对RNA假结结构预测问题开发了几种元启发式算法（Jiwan和Singh，2012;Al-Khatib等人，2010年）。其中一些在这里简要介绍。3.1. 加克诺Tong等人提出了一种基于遗传算法的名为GAknot的方法（Tong等人，2013年a）。为了表示长度为n的RNA二级结构，他们构建了一个n-n矩阵。特定的行和列表示输入RNA序列中的相应核苷酸例如，第i行和第j列表示第i个核苷酸和第j个核苷酸。如果矩阵中的元素构成典型的沃森-克里克碱基对（AU，GC）或摆动碱基对（GU），则值矩阵[i，j]= 1，否则，矩阵[i，j]= 0。在填充矩阵之后，计算最大词干列表，称为词干列表其次，利用最大茎的不同组合构建RNA二级结构然后应用遗传算法寻找自由能最小的最优解。采用两种不同的热力学能量模型进行适应度计算。 在候选茎生成阶段，他们使用了 Mfold （ Zuker ， 2003 ） 和 RNAfold （ Mathews et al. ， 1999年）。在遗传算法中，他们应用了具有新参数的修改后的&Dirks-Pierce（DP）能量模型（Andronescu等人， 2010）作为适应度函数来评估个体的适应度。他们在两个数据集上进行了测试，以验证GAknot。PK168数据集，取自（Sato et al.，2011），包含168个RNA的假结结构。 另一个被称为HK41，包含41个序列，由HotKnots中使用的序列子集构建（Ren et al.， 2005年）。这种方法的主要优点是，他们释放了对个体形成的限制，并对染色体的操作符和格式做了一些修改，以提高准确性。GAknot的缺点914马里兰州Shahidul Islam，MD.Rafiqul Islam/ Journal of King Saud UniversityXXE1/4E-笔式注射器2008年3月8日DP092×我#markk-1j-k+1算法无法准确预测RNA序列的所有二级结构。作为能量计算函数的适应度函数仍然是不完善的（Tong等人，2013年b）。GAknot需要很长时间来预测具有大量螺旋的RNA结构。3.2. GAknot 2.0Tong等人 提出了另一种具有自由能模型的修改版本的方法，其改进了具有伪结的RNA二级结构预测（Tong等人，2013年b）。使用DP 09（Andronescu等人， 2010）能源模式。首先，他们从RNASTRAND数据库中选择了1057个具有伪结的RNA结构作为训练数据集然后，他们从训练数据中提取每个序列的茎，并扫描茎以分别获得3-mer，4-mer和5-mer的列表。k聚体是RNA序列的k长度子序列之后，他们计数每个k-聚体模式的相应数量.对于给定的k-聚体，通过以下函数计算相应的惩罚因子：马克最小自由能该算法不使用任何热动力学模型，而是通过连续的碱基对堆叠来近似估计RNA结构的自由能。为了评估算法的性能，他们使用了来自PseudoBase数据库的10个RNA假结序列。结果表明，该算法的平均灵敏度和PPV分别为92.6和84.3，优于另一种比较算法IPknot（Sato etal. ， 2011 ） 、 TT2NE （ Bon 和 Orland ， 2011 ） 和 CyloFold（Bindewald等人， 2010年）。4. 方法在这项工作中，我们应用遗传算法和模拟退火来预测RNA的二级结构，包括假结。我们还使用了两种混合算法，使用遗传算法和模拟退火。这两种算法分别称为GA-SA和SA-GA。在GA-SA中，GA用于全局搜索，SA用于局部搜索。在SA-GA中，SA用于全局搜索，GA用于局部搜索。算法主要分为三个步骤：初始化种群生成、迭代和终止评估。所有的算法-佩·N·K。马若琪#ið7Þ能量模型使用以下公式计算：5K iK我们将共同讨论共享部分，并单独讨论算法的执行。4.1. 人口世代k¼3我其中EDP09是DP09模型的能量值。通过应用新的能量模型，他们在HK41数据集中发现了灵敏度和PPV分别为85.2和77.1的最佳结果，该数据集先前已用于验证GAknot。3.3. 基于GRASP方法的Fatmi等人开发了一种基于两种主要技术处理RNA二级结构预测的算法;遗传算法和GRASP（贪婪随机自适应搜索过程）方法（El Fatmi等人，2017年）。主要的好处是GRASP方法结合了随机搜索、邻域方法和贪婪算法的优点。他们使用特纳模型2004来计算RNA二级结构的自由能。为了评估算法的性能，在IPknot（Sato等人，2011）、TT2NE （ Bon 和 Orland ， 2011 ） 、 CyloFold （ Bindewald 等 人 ，2010），并且使用四种RNA序列TMV、CcTMV、Hs PrP和CGMMV进行RNA构建（El Fatmi等人，2017），以及两个参数灵敏度（SN）和特异性（SP）。结果表明，该算法的性能优于其他方法。主要的局限性是，它们只适用于较短的序列，并且并不总是保证最优解3.4. 模拟退火Kai等人开发了一种基于模拟退火的算法来预测具有伪结的RNA二级结构（Kai和Yulin，2018）。首先，识别最大连续互补碱基对。（i，j，k）形式的互补碱基对称为k个连续碱基对，其中i和j是碱基位置，k是连续碱基对的数目。碱基对必须满足条件{（xi，xj），（xi +1，xj1）... （xi +k-，x）}（A，U），（G，C），（G，U）. 新的相邻状态是从连续的碱基对随机产生的。设计了退火算法的调度函数，使退火算法系统地降温，最终得到RNA结构的解，群体生成过程将长度为n的RNA假结序列作为输入。然后构造一个名为board的大小为n n的空数组。行和列都被索引，使得第i个索引保存序列的第i然后板上填充了set，v={0，1}的值。 董事会[i，j]如果对应的第i行和第j列构成规范Watson-Crick碱基对（A-U，G-C）或非规范Wobble碱基对（G-U），则得到1。否则，板[i，j]被填充为值0。下三角形（1）是从从左下角到右上角的对角线。如果至少从（i，j）开始找到u个连续的1，我们添加词干（j，i，1的个数）在一个叫做词干列表的列表中。其中u是一个变量，称为最小所需的连续的。它根据输入序列的长度在3到7之间变化。之后，我们将stem列表的索引放入另一个名为stem_numbers的列表中。为茎数构建了一个每突变表.从排列表中选出的“PopSize种群生成过程如图2所示。在附录A中的算法1中给出了用于群体生成的伪代码4.2. 二次结构施工从初始群体中随机选择一个茎编号对于词干编号中的每个索引，可以从词干列表中提取词干。设一个词干表示为（p，q，l）。其中p表示词干的起始位置，q表示词干的结束位置。其中p映射到i，q映射到矩阵中的j。这里，l表示茎的长度，以核苷酸（nt. ）.茎是lnt。从开始（p）到右边和lnt。从左到右（q）。一个名为dp的列表，长度为序列长度（n），填充有点（.）已经有人了对于每个词干（p，q，l），我们将l个连续的如果两个茎重叠，则切割重叠的茎并检查截断长度l如果我Rithms共享相同的群体生成、二级结构构建和假结构建技术。因此，我们认为，马里兰州Shahidul Islam，MD.Rafiqul Islam/ Journal of King Saud University915≥图二. 种群生成过程：（a）电路板构建，（b）词干列表，（c）词干编号，（d）词干编号排列。3，则继续该过程，将词干视为（p，q，l否则，将茎从二级结构的建造中丢弃。每个茎数产生的dp是给定序列的RNA二级结构的不同构型。首先，使用等式（2）计算二级结构的自由能。二级结构施工过程如图3（a）所示。从总体中随机选择个体（[4，1，5，2，0，3]）。输入序列长度为21。因此，创建了一个列表dp[0-20]，所有索引都用点（.）填充。 对于词干4（5，19，5），从索引5开始插入五个左括号“（“。类似地，从索引19向后插入五个右括号“）”。对于茎1、5、2、0，茎是重叠的因此，这些股骨柄对结构没有影响。对于股骨柄3（3、15、6），可能有几种不同的情况。首先，股骨柄重叠，因此无法放置股骨柄3。其次，我们可以用茎3替换茎4，以实现茎最大化。第三，计算两个重叠的茎的能量，保留较低的茎。也可以这样做其他的茎也一样然而，一个螺旋少茎通常-盟友有更多的正自由能。因此，我们在能量最小化和碱基对最大化之间进行权衡。 在这种情况下，图2（a）所示的最终结构具有最低的能量。二级结构能量计算：CCCUUGUCUCAGGUAGAGACC（一级序列）.. . . .. . .（（（（（.）））））. （二级结构）碱基对50GUCUC30| | | | |30CAGAG50DG茎 =DG°37（GC后UA）+DG°37（UA后CG）+DG°37（CG后UA）+DG°37（UA后CG）=–2.24千卡/摩尔–2.35千卡/摩尔–2.08千卡/摩尔2.35千卡/摩尔= -9.02千卡/摩尔DG环 =长度为5的发夹环+外部环（末端错配、悬空末端、同轴堆叠）916马里兰州Shahidul Islam，MD.Rafiqul Islam/ Journal of King Saud University30-0G --5个30-0GA -五个--≤ ≤≤≤hð Þ图三. 用假结构建RNA一级序列到二级结构。(a)二级结构构造，（b）假结结构构造。=发夹起始+悬挂末端。50-CC-30+dan-.50-C--30分钟因此我们跳过词干4。对于词干1（2，12，4），尝试将'']". 在这里，一个索引（索引5）与词干4重叠，因此我们将长度减少1（根据规则4有效），并放置三个开放-格林恩德30-GU-50+端子失配用同样的方法去掉方括号，.50-CA-30分钟=+5.6千卡/摩尔+3.3千卡/摩尔DG =D G股骨柄 +D Gloops=-9.02千卡/摩尔+3.3千卡/摩尔=-5.72千卡/摩尔4.3. 伪纽结构造来自二级结构构造阶段的dp的副本被传递到伪结构造过程。对于每对词干（p1，q1，l1）和（p2，q2，l2），检查它们是否满足以下条件：1.其中至少有一家没有参与过二次结构施工2.p1p2q1q23. 1 L1 100、0 L2 50、2 L3 1004. 茎大小至少为2nt。5. 伪结能量0其中L1=p2-p1-l1;L2=（q1-l1+ 1）-（p2+l2）;L3=l l2 q1;然后，对于二级结构构造中未使用的词干，我们在DP中为简单伪结放置使用等式（3-6）计算伪结能量将二级结构的能量和假结的能量相加，得到RNA假结结构的总能量。伪结构建过程如图3（b）所示。我们已经从二级结构构造（第4.2节）中提取了二级结构。茎4已经参与了二级结构构建（违反规则1），二级结构建设。由于L1 = 0，因此生成的结构无效（违反规则3，1L1 1 0 0类似地，对于词干5，L3 = 0（违反规则3），并且对于词干2，L1 = 0，L3 = 0（违反规则3）。对于词干0，所有规则都为真，因此结构有效。对于股骨柄3，没有构建假结的有效方法因此，最终的假结结构是股骨柄1和0的结构。假结结构能量计算：CCCUUGUCUCAGGUAGAGACC（一级序列）. [[. (((((]]] ..））））. （伪结结构）这里，L2为0，因此应使用CC06模型来计算伪结能量。S1，DGS1的堆积能= -5.34 kcal/mol S2，DGS2的堆积能= -9.02 kcal/mol L1熵，TDSL1= 1.43 kcal/molL3熵，TDSL3= 4.03 kcal/mol赝结能，DGS1;S2;L1;L2;L3 DGS1 DGS2-TDSL1 DSL3 DGcsADG装配=-5.34= -7.6千卡/摩尔4.4. 遗传算法遗传算法（GA）是一种基于遗传学和自然选择原理的基于搜索的优化技术。它是一种流行的算法，用于为NP难（及相关）时间复杂性问题找到最优或接近最优的解决方案。我们实现了遗传算法的三个操作，如交叉，变异和幸存者选择，以搜索最优解马里兰州Shahidul Islam，MD.Rafiqul Islam/ Journal of King Saud University917溶液突变是染色体的一个小的变化，以获得一个新的解决方案。它用于探索解决方案的局部搜索空间突变是趋同的必要条件在交叉中，不止一个个体在它们之间交换信息因此，多样性带来了新的解决方案。Crossover用于在解空间中进行选择是寻找的过程最合适的人在遗传算法中，个体被称为染色体。染色体是解决问题的一个办法。它是人口的一个单位。在附录A的算法2中给出了遗传算法的伪代码运算符的描述和算法如下。4.4.1. 交叉交叉算子类似于生物交叉。在这个操作符中，选择一个以上的父代，并产生一个或多个子代。在我们的算法中，我们选择两个父母和交叉产生两个新的后代。单点，多点或均匀交叉是可能的。单点变异可以产生几乎相同的解，而均匀交叉可能会破坏好的解。根据我们的训练实验，我们选择了两点（多点）交叉。如图4（a）所示，两条染色体m1和m2是从群体中概率性地选择的。生成两个范围为1到m1的随机整数x和y，以选择将每个染色体分成三段的交叉点。 偶数段交换，奇怪段在新产生的后代m11和m22中保持不变。交叉算子的伪代码在附录A的算法3中给出4.4.2. 突变突变是指染色体发生微小的随机变化以获得新的解。由于RNA的长序列，单点突变可能非常缓慢。另一方面，我们在实验中也使用了较短的RNA序列。因此，乱序或倒位突变对这些短序列不可能那么有效。因此，在不同的变异中，我们选择了两点交换变异。在该算子中，概率性地选择单个染色体（m1）。生成范围为1到大小为m1的两个随机整数x和y以帮助交换过程。交换m1[x]和m1[y]的值以生成新的个体m11（如图4（b）所示）。变异的伪代码在附录A的算法4中给出4.4.3. 幸存者选择“幸存者”选择操作符确定要为下一代选择哪些个体。为了选择一个更好的适应性染色体，后代通过它们的自由能与它的父母进行比较。负自由能越多，个体的适应性越好。因此，无论父染色体还是子染色体，算子都会选择具有最小自由能的染色体. 图4（c）中示出了幸存者选择过程的示例。幸存者选择的伪代码在附录A中的算法5中给出4.4.4. GA参数设置表1示出了GA中使用的参数表2总结了参数选择过程。为此目的，选择了具有20个RNA假结序列的名为DCC 06的独立数据集对于迭代80到200，F-测量的值为见图4。GA的操作员。(a)交叉，（b）突变，（c）存活者选择。918马里兰州Shahidul Islam，MD.Rafiqul Islam/ Journal of King Saud University表1遗传算法参数在RNA结构预测中的应用SL.符号描述1迭代进程的重复次数2PopSize种群大小或染色体数目人口空间3突变率单个基因或生物体的突变频率随着时间4交叉率2条染色体之间的交叉频率随着时间表2用遗传算法对具有伪结的RNA结构进行预测的参数值。a2（a）F-抗迭代a黑体字数值表示相应年份达到的最高F值。迭代、突变率和交叉率。改善。超过200次（最多1000次）迭代，性能没有显著变化。因此，选择迭代= 200的最佳值。根据实验结果，PopSize= 70是最适合最大化性能的一个小群体不包含所有的茎，而一个大群体可以有重复的染色体。MutationRate在以下范围内进行调整：0.05到0.4，我们发现MutationRate= 0.1时的最佳结果。同样，交叉率从1.0到0.65并设置为0.85。使用所有这些参数值进行最终测试。它给出了性能，F测量= 87.34。遗传算法的参数整定图如图所示。 五、4.4.5. GA的实现在初始化阶段，为GA的参数赋值并生成初始种群（附录A中的算法1）。在迭代开始时，计算染色体的适应度值并选择最适合的染色体。然后在选定的种群上进行交叉和变异。如果没有交叉，则后代是父母如果有一个交叉，后代是由部分父母的染色体如果没有变异，则交叉后取后代，不作任何改变。如果发 生 突 变 ， 染 色 体 的 一 部 分 发 生 改 变 . 名 为 CrossoverRate 和MutationRate的两个参数表示交叉和突变的执行频率每次迭代后，计算新种群的适应度值并选择最佳个体迭代一直进行，直到满足停止标准。4.5. 模拟退火退火是加热和冷却金属以改变其内部结构的过程。当金属冷却时，它的新结构被抓住，金属保持其新获得的性能。模拟这种自然现象的计算机算法被称为模拟退火（SA）。在退火过程中，温度保持可变。最初，温度被设置得很高，然后随着算法的进行而缓慢冷却。SA的伪代码在附录A中的算法6中给出4.5.1. SA参数设置表3显示了SA中使用的参数。表4总结了参数选择过程。在此过程中也使用了GA（DCC06）中使用的相同数据集。当温度（T）较低（T200）时，性能为F-测量= 74.7。在200 ~ 500 ℃的温度范围内，F-测度值有提高的趋势。超过500次（最多1000次）迭代，性能没有显著变化，F-度量固定在91.3。因此，选择温度的最佳值T= 500。根据实验结果，PopSize= 70是最大化性能的最佳值。SA的参数调整图如图所示。 六、4.5.2. SA的实施首先，为参数赋值并生成初始群体（附录A中的算法1）。计算种群的初始能量，选择能量最小的个体。在每次迭代中，生成该个体的一组近邻。从邻居的集合中，选择具有最低能量的个体。 计算Δ能量DE，并计算接受新邻居的概率。如果满足条件DE 0或e-DE/Trandom（0，1），则将具有最小能量的邻居分配给当前个体，并对其应用下一次迭代。在每次迭代结束时，温度（T）降低。我们使用了指数乘法冷却函数。调度函数的方程如下所示。Ti1Ti×ai9其中a= 0.9，i是迭代。当温度冷却到0时，该过程停止4.6. 混合GA-SA算法在具有伪结点的我们将遗传算法和模拟退火算法相结合，提出了一种用于带伪节点的RNA二级结构预测的混合算法GA-SA。在该算法中，我们使用遗传算法的全局搜索和SA的局部搜索的结果，遗传算法产生的。GA-SA已执行使用相同的参数，以前使用的GA和SA算法分别。在该方法中，GA和SA算法都存在一定的缺陷.在图2（b）所示的种群生成过程中，对于茎（3，15，6），两个其他茎（4，14，5）和（8，10，5）可以通过从内侧（即8和10键）或外侧（即4和14键）切割碱基对来产生。我们可以把两边都剪到长度>=3。这样，一个较大的茎可以被分成几个较小的茎。有可能使用这些较小的茎以最小的能量构建RNA结构。SL.迭代F-measure15078.4928082.71310081.27415083.65520084.98630084.54750084.688100084.682（b）针对MutationRate的F-测度SL.突变率F-measure10.0583.9520.184.4730.1580.4740.280.9850.2581.9960.379.4170.3579.4180.478.882（c）针对交叉率的F-测量SL.交叉率F-measure1182.6720.9582.4730.982.4740.8583.1150.881.7360.7582.2670.78080.6581.82马里兰州Shahidul Islam，MD.Rafiqul Islam/ Journal of King Saud University919图五、遗传算法的参数整定（a）GA迭代，（b）突变率，（c）交叉率。表3用伪结预测RNA结构的SA参数。符号描述T随时间PopSize种群大小或种群空间中的个体数表4模拟退火算法在RNA结构预测中的参数取值SL.温度（°C）F-measure120074.7230084.5350091.34100091.35150091.3图六、SA的参数（温度）调整因此，我们考虑结合GA-SA和SA-GA的实现，以研究解决空间与较小的茎。GA的另一个缺点是GA容易陷入局部极小。由于其算子的破坏性影响，GA有时会丢失好的解（Zhanget al.，2005年）。不同的决策机制，如玻尔兹曼分布，以确定拒绝或接受新结构的概率可以帮助在这个问题上。在个体的不同组合中搜索也可以发现全局极小点。这可以用GA GA或SA SA杂交来完成。研究表明，混合遗传模拟退火算法比单一遗传模拟退火算法具有更好的效果GA-SA算法是先正常执行GA算法，然后将GA算法的输出作为SA算法的输入然后，SA算法生成现有词干的所有可能的词干组合GA-SA流程图如图所示。 7（a）.4.7. 混合模拟退火-遗传算法在具有伪结点的为了测试不同方法的效率，我们已经实现了另一种杂交SA和GA命名SA-GA，我们探索搜索空间使用GA的SA产生的人口。参数与GA-SA算法相同。SA-GA的执行类似于GA-SA。在这种情况下，我们使用SA的全局搜索和GA的局部搜索SA的结果。SA-GA的流程图如图所示。 7（b）.920马里兰州Shahidul Islam，MD.Rafiqul Islam/ Journal of King Saud University¼ ð Þ-1/4见图7。混合算法流程图：（a）GA-SA，（b）SA-GA。5. 实验结果五个数据集被用来验证我们开发的算法。D-CC 06用于参数选择（训练），其他四个用于测试。表5总结了这些数据集。在表中，D-CC06、D-SA和D-GA表示CC 06（Cao和Chen，2006）、模拟退火（Kai和Yulin，2018）和遗传算法（El Fatmi等人，2017年）。从IPknot提取PK168数据集（Sato等人， 2011年），是灵敏度和PPV的平衡度量，是灵敏度和PPV的加权调和平均值。INF被称为马修斯在数学上，灵敏度、PPV、F-测量和INF表示如下（Sperschneider和Datta，2010）：灵敏度TP10TPFFN含有168个假结RNA序列和HK 41（Tong等人， 2013a）数据集包含41个序列。这些算法在Windows上用Python实现我们取了10的平均结果PPVTP��运行所提出的方法的每个序列。预测准确度用灵敏度、阳性预测值（PPV）、F-测量和交互网络保真度（INF）表示。灵敏度是真阳性与实际类别中阳性总数的比率。PPV是真阳性F测量2×灵敏度×PPVSensitiv ity PPVINF¼pSensitivity×PPVð12Þð13Þ预测类中的阳性总数F度量，其中TP =真阳性，FP =假阳性，FN =假阴性。表5在GA、SA、GA-SA、SA-GA中使用的数据集用于具有伪结的RNA结构预测。SL.数据集序列数序列长度引用1PK16816821–137（Sato等人，（2011年）241港4128–400（Tong等人，2013年a）3D-SA1041–134（Kai和Yulin，2018）4D-ga438–45（El Fatmi等人，（ 2017年）5公司简介2039–83（曹和陈，2006）马里兰州Shahidul Islam，MD.Rafiqul Islam/ Journal of King Saud University921表6GA，SA，GA-SA和SA-GA算法与以前的算法的灵敏度进行了比较数据集GASAGA-SASA-GA参考文献中提到的算法的结果引用PK16879.4979.1684.7281.4481.60、80.9、69.0（Tong等人，2013 a; Sato等人，2011; Ren等人，（2005年）41港74.8773.4082.1882.0085.2、81.6、50.8、64.6（Tong等人，2013 b; Tong等人，2013 a; Sato等人，2011; Ren等人，（2005年）D-SA92.7192.2694.5793.2492.60（Kai和Yulin，2018）D-ga93.3093.3093.3093.3081.00（El Fatmi等人，（ 2017年）表7并将GA、SA、GA-SA和SA-GA算法与已有算法进行了PPV比较。数据集GASAGA-SASA-GA参考文献中提到的算法的结果引用PK16881.3681.2784.4682.6275.10、74.9、72.7（Tong等人，2013 a; Sato等人，2011;Ren等人，（2005年）41港75.4374.1480.9480.9477.1、77.4、57.5、68.4（Tong等人，2013 b; Tong等人，2013 a; Sato等人，2011; Ren等人，（2005年）D-SA81.3981.3991.3480.9884.40（Kai和Yulin，2018）D-ga89.7389.7391.3891.3894.5（El Fatmi等人，（ 2017年）表8在F-测度方面，将GA、SA、GA-SA和SA-GA算法与已有算法进行了比较数据集GASAGA-SASA-GA参考文献中提到的算法的结果引用PK16880.4180.2084.5982.03七十八点二二，七十七点七八，七十点八（Tong等人，2013 a; Sato等人，2011; Ren等人，（ 2005年）41港75.1573.7781.5681.4780.95、79.44、53.94、66.45（Tong等人，2013 b; Tong等人，2013 a; Sato等人，2011; Ren等人，（2005年）D-SA86.6886.4892.9386.6888.31（Kai和Yulin，2018）D-ga91.4891.4892.3392.3387.23（El Fatmi等人，（ 2017年）表9将GA、SA、GA-SA和SA-GA算法与已有算法进行了INF比较数据集GASAGA-SASA-GA参考文献中提到的算法的结果引用PK16880.4280.2184.5982.03七十八点二八，七十七点八四，七十点八三（Tong等人，2013 a; Sato等人，2011; Ren等人，（ 2005年）41港75.1573.7781.5681.4781.05、79.47、54.05、66.47（Tong等人，2013 b; Tong等人，2013 a; Sato等人，2011; Ren等人，（2005年）D-SA86.8786.6592.9486.8988.40（Kai和Yulin，2018）D-ga91.5091.5092.3392.3387.49（El Fatmi等人，（ 2017年）对于RNA结构，碱基对被认为是正类，游离碱基被认为是负类。因此，预测一个真实的碱基对是TP，而预测一个碱基对的失败被认为是FN。另一方面，将游离碱基省略为游离碱基是TN，将其预测为碱基对是FP。我们没有在RNA-PSPP中使用TN，因为它不需要在方程中。计算TP、FP、TN和FN的混淆矩阵如图所示。8.第八条。表6显示，GA-SA算法在PK 168和D-SA数据集上具有最高的灵敏度。在D-GA数据集中，所有四种方法都是-见图8。 RNA-PSPP的混淆矩阵。运行之前的算法。在HK41数据集