Fast evaluation of internal loops in RNA secondary structure prediction
Fast evaluation of internal loops in RNA secondary structure prediction
复制标题
DOI：
10.1093/bioinformatics/15.6.440
复制
发表时间：
1999-06-01
期刊：
影响因子：
5.8
通讯作者：
Pedersen, CNS
中科院分区：
文献类型：
--
作者：
Lyngso, RB;Zuker, M;Pedersen, CNS
动机：虽然在已知的生物过程中不像蛋白质那样丰富，但RNA分子不仅仅是DNA和蛋白质之间的中介，而是作为分子-e。过去15年的研究表明，RNA分子具有多种作用，包括催化作用。此外，基于堆叠和环形成的非能量规则的RNA二级结构预测仍然是结构预测领域为数不多的重大突破之一，因为最小自由能结构和相关数量可以用完全的数学严格性计算出来。然而，在当前的能量参数下，目前使用的算法存在这样的缺点：要么采用启发式方法（尽管可能性很小），可能会错过最优结构，要么对大序列的模型消耗过多的时间。结果：我们提出了一种利用当前使用的能量规则来评估内部循环的新方法。该方法将这部分结构预测的时间复杂度从O（n(4)）降低到O(n(3))，从而将整体复杂度降低到O（n(3)）。即使评估的内部循环的大小以k为界（一种常用的启发式方法），所提出的方法也具有竞争优势，因为它减少了内部循环评估的时间复杂度-从O(k（2)n(2)）到O（kn(2)）。该方法也适用于平衡配分函数的计算。
Motivation: Though not as abundant in known biological processes as proteins, RNA molecules serve as mol-e than mere intermediaries between DNA and proteins. Research in the last 15 years demonstrates that RNA molecules serve in many roles, including catalysis. Furthermore, RNA secondary structure prediction based on fi ee energy rules for stacking and loop formation remains one of the few major breakthroughs in the field of structure prediction, as minimum free energy structures and related quantities can be computed with full mathematical rigor. However, with the curl-ent energy parameters, the algorithms used hither to suffer the disadvantage of either employing heuristics that risk (though highly unlikely) missing the optimal structure or becoming prohibitively time consuming for model ate to large sequences.Results: We present a new method to evaluate internal loops utilizing currently used energy rules. This method reduces the time complexity of this part of the structure prediction from O(n(4)) to O(n(3)), thus reducing the overall complexity to O(n(3)). Even when the size of evaluated internal loops is bounded by k (a commonly used heuristic), the method presented has a competitive edge by reducing the time complexity of internal loop evaluation fi-om O(k(2)n(2)) to O(kn(2)). The method also applies to the calculation of the equilibrium partition function.