LinearFold: linear-time approximate RNA folding by 5'-to-3' dynamic programming and beam search
LinearFold: linear-time approximate RNA folding by 5'-to-3' dynamic programming and beam search
复制标题
DOI：
10.1093/bioinformatics/btz375
复制
发表时间：
2019-07-15
期刊：
影响因子：
5.8
通讯作者：
Mathews, David H.
中科院分区：
文献类型：
--
作者：
Huang, Liang;Zhang, He;Mathews, David H.
预测核糖核酸（RNA）序列的二级结构在许多应用中是有用的。现有的算法[基于动态规划]受到一个主要的限制：它们的运行时间与RNA长度成立方关系，这种缓慢性限制了它们在全基因组应用中的使用。结果我们提出了一种新颖的替代RNA折叠动态规划算法，该算法适合启发式算法，使其在O（n）时间和O（n）空间内运行，同时产生最优解的高质量近似。受计算语言学中上下文无关语法的增量解析的启发，我们的替代动态规划算法以从左到右（5到3）的方向而不是以自下而上的方式扫描序列，这使我们能够采用有效的光束修剪启发式。我们的工作，虽然不精确，是第一个RNA折叠算法，以实现线性运行时间（和线性空间），而不施加限制的输出结构。令人惊讶的是，我们的近似搜索结果在具有已知结构的序列的不同数据库上具有更高的整体准确性。更有趣的是，它导致对该数据库中最长序列家族（16S和23S核糖体RNA）的预测显著更准确，以及对长距离碱基对（相隔500多个核苷酸）的准确性提高，这两个都是众所周知的对当前模型的挑战。可用性和实现我们的源代码可在https：//github.com/LinearFold/LinearFold获得，我们的网络服务器在http://linearfold.org（序列限制：10000nt）。补充信息补充数据可在Bioinformatics online获得。
Motivation Predicting the secondary structure of an ribonucleic acid (RNA) sequence is useful in many applications. Existing algorithms [based on dynamic programming] suffer from a major limitation: their runtimes scale cubically with the RNA length, and this slowness limits their use in genome-wide applications.Results We present a novel alternative O(n(3))-time dynamic programming algorithm for RNA folding that is amenable to heuristics that make it run in O(n) time and O(n) space, while producing a high-quality approximation to the optimal solution. Inspired by incremental parsing for context-free grammars in computational linguistics, our alternative dynamic programming algorithm scans the sequence in a left-to-right (5-to-3) direction rather than in a bottom-up fashion, which allows us to employ the effective beam pruning heuristic. Our work, though inexact, is the first RNA folding algorithm to achieve linear runtime (and linear space) without imposing constraints on the output structure. Surprisingly, our approximate search results in even higher overall accuracy on a diverse database of sequences with known structures. More interestingly, it leads to significantly more accurate predictions on the longest sequence families in that database (16S and 23S Ribosomal RNAs), as well as improved accuracies for long-range base pairs (500+ nucleotides apart), both of which are well known to be challenging for the current models.Availability and implementation Our source code is available at https://github.com/LinearFold/LinearFold, and our webserver is at http://linearfold.org (sequence limit: 100000nt).Supplementary informationSupplementary data are available at Bioinformatics online.