Linear-Time Algorithms for RNA Structure Prediction.
Linear-Time Algorithms for RNA Structure Prediction.
复制标题
RNA 结构预测的线性时间算法。
DOI：
10.1007/978-1-0716-2768-6_2
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Huang,Liang
中科院分区：
文献类型：
--
作者：
Zhang,He;Zhang,Liang;Liu,Kaibo;Li,Sizhen;Mathews,DavidH;Huang,Liang
RNA二级结构预测被广泛用于理解RNA的功能。现有的基于动态规划的算法，无论是经典的最小自由能（MFE）方法和配分函数方法，都受到一个主要的限制：它们的运行时间与RNA长度成立方关系，这种缓慢限制了它们在全基因组应用中的使用。受计算语言学中上下文无关语法的增量解析的启发，我们设计了线性时间启发式算法LinearFold和LinearPartition来近似MFE结构、分区函数和碱基配对概率。这些程序在长序列上比维也纳RNAfold和RNAfold快几个数量级。更有趣的是，LinearFold和LinearPartition可以更准确地预测最长序列家族的结构（16S和23S核糖体RNA），以及提高长距离碱基对（相隔500多个核苷酸）的准确性。本章提供了使用LinearFold和LinearPartition进行二级结构预测的协议。
RNA secondary structure prediction is widely used to understand RNA function. Existing dynamic programming-based algorithms, both the classical minimum free energy (MFE) methods and partition function methods, suffer from a major limitation: their runtimes scale cubically with the RNA length, and this slowness limits their use in genome-wide applications. Inspired by incremental parsing for context-free grammars in computational linguistics, we designed linear-time heuristic algorithms, LinearFold and LinearPartition, to approximate the MFE structure, partition function and base pairing probabilities. These programs are orders of magnitude faster than Vienna RNAfold and CONTRAfold on long sequences. More interestingly, LinearFold and LinearPartition lead to more accurate predictions on the longest sequence families for which the structures are well established (16S and 23S Ribosomal RNAs), as well as improved accuracies for long-range base pairs (500 + nucleotides apart). This chapter provides protocols for using LinearFold and LinearPartition for secondary structure prediction.