A dynamic programming algorithm for RNA structure prediction including pseudoknots
A dynamic programming algorithm for RNA structure prediction including pseudoknots
复制标题
DOI：
10.1006/jmbi.1998.2436
复制
发表时间：
1999-02-05
影响因子：
5.6
通讯作者：
Eddy, SR
中科院分区：
文献类型：
--
作者：
Rivas, E;Eddy, SR
我们描述了一个动态规划算法预测最佳RNA二级结构，包括伪结。该算法在最坏情况下的时间复杂度为O（N-6），存储复杂度为O（N-4）。该算法的描述是复杂的，这使我们采用了一个有用的图形表示（费曼图）借用量子场论。我们提出了一个实现的算法，产生一个单一的RNA序列的最佳最小能量结构，使用标准的RNA折叠热力学参数增加了一些参数描述的热力学稳定性的伪结。我们证明了该算法的性能，用它来预测几个小的pseudoknotted和非pseudoknotted RNA的结构。虽然该算法的时间和内存需求是陡峭的，我们相信这是第一个算法，能够折叠最佳的（最小能量）pseudoknotted RNA与公认的RNA热力学模型。(C)北京：科学出版社.
We describe a dynamic programming algorithm for predicting optimal RNA secondary structure, including pseudoknots. The algorithm has a worst case complexity of O(N-6) in time and O(N-4) in storage. The description of the algorithm is complex, which led us to adopt a useful graphical representation (Feynman diagrams) borrowed from quantum field theory. We present an implementation of the algorithm that generates the optimal minimum energy structure for a single RNA sequence, using standard RNA folding thermodynamic parameters augmented by a few parameters describing the thermodynamic stability of pseudoknots. We demonstrate the properties of the algorithm by using it to predict structures for several small pseudoknotted and non-pseudoknotted RNAs. Although the time and memory demands of the algorithm are steep, we believe this is the first algorithm to be able to fold optimal (minimum energy) pseudoknotted RNAs with the accepted RNA thermodynamic model. (C) 1999 Academic Press.