英语原文共 16 页，剩余内容已隐藏，支付完成后下载完整资料
一种新的高效模拟退火算法RNA二级结构对假结进行预测
摘要
RNA分子的假结构在细胞功能上起着重要作用。然而，现有算法无法快速准确地预测假结构。在本文中，我们提出了一种新的有效的遗传算法来预测具有平面假结的核酸二级结构。首先，对所有可能的最大连续互补碱基对堆叠计算并保存。其次，候选的解决方案新状态可以通过在SA的中间步骤中随机选择这些连续碱基对中的一个来生成。我们的算法应该更喜欢保持新的状态更多连续的碱基对和更少的组号。最后，整个模拟退火程序至少运行10次，最终解决方案是10个候选解的最小自由能结构。此外，我们的算法的性能由PseudoBase的实例测试数据库，与RNA结构，IPknot，TT2NE，CyloFold，RNAflod，CombFold和HotKnots比较。比较结果表明，我们的算法更准确，更具竞争力，灵敏度和特异性更高指标。
关键词：RNA二级结构，Pseudoknot，模拟退火框架
介绍
RNA是核苷酸酸分子的长链，其由A（腺嘌呤），U（尿嘧啶），G（鸟嘌呤）和C（胞嘧啶）组成。四碱基排列允许RNA具有多种功能，可以在遗传编码，翻译，调节和基因表达中发挥作用。例如，在细胞生物学中，mRNA（信使RNA）是遗传信息的传递者，可以指导蛋白质的合成。因此，寻找RNA序列的二级结构已被广泛使用理解生物功能的第一步[1]。目前的方法预测二级RNA结构是通过物理方法如X射线和核磁共振。虽然这些物理方法可以准确预测RNA分子的二级结构，但是需要过多的资源和努力来操作导致预测RNA二级结构的成本太高。所以，如何降低预测RNA二级结构的成本，同时确保二级结构预测的准确性和高效性，使得二级结构预测问题成为生物信息学最重要的研究课题。
RNA二级结构通过在G C，A-U和G-U之间形成氢键而折叠自身。 因此，RNA二级结构的预测归结为预测来自序列主要结构的所有氢键连接。二级结构中被识别的组件有许多，例如堆叠对或堆栈，发夹循环，多分支循环或多循环，凸起循环和内部环。 组件结构可以用示意图表示或表示弧形表示，如图1所示
图1（a）典型的RNA二级结构
（b）典型RNA二级结构的圆弧表示。 这张图片是使用jViz.Rna [2]创建的
根据最近邻热力学模型，RNA自由能Delta;G由子结构的自由能组成。堆叠对Delta;GS、发夹环Delta;GH、多分支环Delta;GM、凸环Delta;GB、中间环Delta;GI和假结Delta;GP.RNA结构的自由能可以计算如下：
假结构是普遍存在的RNA三级结构。它在不同的RNA序列中发挥各种各样的作用。这些作用包括端粒酶的形成各种核酶的催化核心，以及自我拼接的内含子，此外，假结通过诱导核糖体转移在改变许多病毒基因的表达中起关键作用[3]。预测包括假结的RNA二级结构一般问题已被证明是理想化的热力学模型的NP完全问题[4]。假结是RNA二级的特殊拓扑结构结构，通常包含至少两个堆叠，使得（图1.a pseu doknot结构）中的未配对碱基一个茎对的环与环外的基部形成另一个茎。从图1.b我们可以看出，与其他结构相比假结的预测更复杂，而影响算法预测结果的准确性。这也使许多研究人员在预测RNA二级结构时忽略假结。
在本文中，我们提出了一种有效的模拟退火算法来预测具有平面假结的RNA二级结构。根据最近的相邻热力学模型，只有连续的碱基对有助于RNA自由能的减少，才使得RNA分子更稳定。首先，将计算所有可能的最大连续互补碱基对堆叠并保存。其次，候选解决方案的新状态将由生成在SA的中间步骤中随机选择这些连续碱基对中的一个。我们的算法更喜欢使用更多连续的碱基对保持新状态。第三，整个模拟退火程序至少会运行10次，因为随机解决方案不是独特的结构。最终的解决方案是最小的结构10种候选解决方案的自由能（MFE）。最后，我们的算法表现与使用PseudoBase [17]基准的RNA结构方法进行比较。比较结果表明，我们的算法更准确，更具竞争力，具有更高的灵敏度和特异性值。
相关工作
给定长度为n的RNA序列X = 5x1x2 ... xn-3，M（X）为映射字符串X，M（X）=（m1，m2，...，mi，...，mn）的互补碱基对。 如果xi与xj结合，mi的值分配给j，mj的值分配给i。 如果xi不粘合且与任何其他基础一起，mi的值被赋予i本身。 RNA的自由能可以通过给定的M（X）和最近邻热力学参数来计算。实际上，随机RNA序列存在指数组合映射M（X）。 最稳定的RNA结构是具有MFE的结构。
然而，自由能的计算复杂性非常昂贵。 因为在所有二级结构中，只有连续的碱基对堆叠结构Delta;GS该RNA序列的稳定性也可以通过连续碱基来对堆栈近似评估。动态规划算法和启发式算法是两个主要的用假结法预测RNA二级结构的方法。
2.1动态规划算法
动态编程（DP）是用于预测的第一种计算方法RNA结构[5] 。DP的基本思想是将复杂问题分成许多简单的子问题，以方便他们的处理[6]。 结合DP理念与研究人员提出了许多RNA二级结构预测算法。 如pknots-RE算法，pknotsRG-mfe算法，NUPACK算法。
基于DP的预测算法增加了时间和空间复杂度预测算法在考虑假结预测时的应用例如，里瓦斯并且Eddy提出pknots-RE [7]算法可以预测RNA序列假结构。它们提供了完整的模型以及参数计算假结二级结构的自由能。然而，这种算法很复杂，最坏的情况是O（n6）时间复杂度和O（n4）空间复杂度。这使得使用这种算法预测长链序列非常耗时。由于DP的限制，其最大预测序列长度不能超过150.此外，pknots-RE算法只能输出MFE结构不提供次优的MFE结构。这些算法为未来的研究人员提供了一个完整的参数化热力学模型，可用于计算自由度具有二级结构的假结构能量。 pknotsRG-mfe [8]从pknots-RE算法改进算法，克服了上述pknots-RE算法的许多上述缺点。 pknotsRG-mfe算法通过进一步限制类来减少时间复杂度和空间复杂性假结的处理。此外，它不仅足以提供次优自由能结构还要延长预测的序列长度。
Dirks和Pierce提出的NUPACK [9]算法是一个变换分区函数算法，用于计算可以的一系列递归概率用于计算有或没有假结的基础配对概率。NUPACK时间复杂度为O（n5）和空间复杂度O（n4）。
可以看出，预测算法的时间和空间复杂性因为动态编程很高，这对于算法来说对长序列做出预测是不利的，因为它需要更多的时间和资源。
2.2启发式算法
与先前讨论的基于动态编程的方法相比，启发式方法不能保证找到MFE结构。然而，启发式方法可以更快且具有处理长RNA的能力序列[10]。此外，越来越多的研究人员尝试使用启发式算法预测RNA二级结构的方法，例如HotKnots算法，SARNA-predict-pk算法和IPKnot算法
HotKnots [11]通过一次一个地添加子结构来构建候选二级结构形成部分结构。它保持多个部分形成结构，对于每个部分形成的结构，考虑几个不同的添加单个子结构，产生候选结构树。确定在部分形成的结构中添加哪些子结构的标准相对于以前的算法，树的连续级别也是新的：能量通过调用Zuker的算法找到称为“热点”的有利子结构，具有约束的结构中没有碱基已经配对。算法使用标准的自由能模型[12] [13]，扩展到假结[9]，确定树节点处的哪些结构具有最低的自由能。这个能量模型也用于确定如何修剪部分结构树从最有希望的（即最低能量）探索更多的替代品部分结构。
SARNA-predict-pk [15]算法是SARNA-Predict的扩展版本[10]它预测具有假结的RNA二级结构。 SARNA-Predict-pk采用Rastegari和Condon描述的新热力学模型
[16]并在HotKnots软件[11]中实现。该模型可用于评估具有假结的RNA序列。
IPknot [14]算法提出了一种计算方法，用于基于最大化预期准确度来预测具有假结的RNA二级结构预测。该算法将假结分解为一组无假结的子结构并近似考虑假结的基础配对概率分布，带来广泛类型假结建模的能力并且运行得很快。此外，他们使用启发式算法来提高参考匹配的概率，以提高IPknot算法的预测精度。
上述启发式算法HotKnots算法和SARNA-predict-pk算法通过构造复杂的热动力学模型处理具有假结的RNA序列，这在一定程度上削弱了heuristic算法的执行效率。为了弥补这一不足，在我们的算法中，提出了RNA二级结构评估函数（RSSEF）来代替热力学模型评估函数。
拟议方法
3.1问题定义
对于长度为n的给定RNA序列X = 5-x1x2 ... xn-3，M（X）是映射字符串
X，M（X）=（m1，m2，...，mi，...，mn）的互补碱基对。 每个mi对应以（i,j,k）的形式，必须满足两个约束：
碱基对约束: If (k 1)}isin;M, then {(xi, xj), (xi 1, xj-1),hellip;, (xi k-1, xj-k 1)}isin;{(A, U),(G, C),(G, U)} in RNA
K个连续碱基对约束： If (k 1)}isin;M, then j - i gt; 2 * MinStem MinLoop，MinStem ge; 2 MinLoop ge; 3 and K ge; MinStem，其中MinStem是最小堆栈数，MinLoop是最小循环数（图2）。例如，发夹环中必须至少有1/8不成对的碱基
图2 MinStem和MinLoop的图形说明
根据包含假结的RNA二级结构的碱基对特征，可以表示茎，环和假结构。由（i,j,k），称为K连续碱基对。i表示的位置连续对中的第一个基数，j表示连续对中最后一个基数的位置，k表示连续对的长度，其具有最小值。一个例PseudoBase [17]数据库中的Mengo_PKB序列如图3所示序列是S= 5rsquo;-ACGUGAAGGCUACGAUAGUGCCAG-3rsquo;茎是（2,14，4）和（8,22,3）。（2,14,4）的形式意味着第一个基地的位置第一个连续碱基对位于位置2，第一个连续碱基对中最后一个碱基对的位置位于第14位，茎长度为4。
图3.（a）Mengo PKB二级结构。 （b）Mengo PKB的Arch代表
因此，RNA二级结构预测的问题可以转化为特定的（i,j,k）问题。 我们提出了一种基于模拟退火的方法有效地解决了如何选择这些连续碱基对的问题。
3.2一组K个连续碱基对算法
本节描述了如何找到一组K个连续碱基对来准备结构预测的过程。
在计算机模拟的碱基配对中，我们不对单个碱基进行配对，而是使用成功的碱基对，这提高了碱基对的效率。 算法划分分三步：
- 确定给定参数中可能的碱基对的边界
我们通过设置MinStem和MinLoop减少了所有可能碱基对的范围参数。 假设有三个变量i，j，k，它们代表第i个基数位置，第j个基本位置，k是K个连续碱基对的数量。 根据上面的图2，可以看出i，j，k需要满足以下条件三个约束同时：
其中n代表RNA序列的长度。
-
找到给定序列中的所有碱基对。
在该步骤中，首先，RNA序列是基于碱基位置的长度编码。以Mengo_PKB的RNA序列为例，序列为{1,2,3，..，22,23,24}通过RNA长度编码。设计RNA的主要目的长度编码是记录RNA的折叠路径。当基地在位置i，j的RNA序列满足Waston-Crick碱基对规则，即数量交换位置i，j，此时保存折叠。我们将Min Stem初始化为3并将MinLoop初始化为3.根据约束的第一步，所有基数Mengo_PKB对是（2,14,3），（2,14,4），（2,20,3），（3,13,3），（3,21,3），（8,22,3）（9,19,4），（10,18,3），（11,20,3）。 具体细节可以参考算法1。
算法1：计算基于MinStem和MinLoop的所有碱基对
-
根据所有碱基对合并K个连续碱基对的集合。
在所有碱基对中，都会出现碱基相同位置的现象不同的连续碱基对数。 因此，我们需要合并这些相同的位置。与上面的Mengo_PKB序列一样，合并后的基集对也是如此（2,14，（3,4）），（2,20，（3）），（3,13，（3）），（3,21，（3）），（8,22，（3） ），（9,19，（3,4）），（10,18，（3）），（11,20，（3））。 具体实现细节可以参考算法2。
算法2.在所有碱基对上合并K个连续碱基对的集合
3.3基于模拟的RNA二级结构预测退火算法
本节描述了如何基于模拟退火框架生成RNA二级结构。
在计算所有碱基对RandomList的集合和K的连续集合之后从RandomList中随机选择的碱基对（i，j)一对新的。在生成新对期间，如果存在冲突的碱基对，则首先去除冲突的边缘，然后编码分子的长度。在这点，之前的有效匹配可能无效，因此也有必要进行检测编码的当前RNA序列长度是否具有无效匹配。例如，去除冲突的碱基对将减少连续匹配碱基的数量在小组中，使得不可能满足最小茎区的条件并
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[442231]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
