Ren Jihong, Rastegari Baharak, Condon Anne, Hoos Holger H
Department of Computer Science, University of British Columbia, Vancouver, BC V6T 1Z4, Canada.
RNA. 2005 Oct;11(10):1494-504. doi: 10.1261/rna.7284905.
We present HotKnots, a new heuristic algorithm for the prediction of RNA secondary structures including pseudoknots. Based on the simple idea of iteratively forming stable stems, our algorithm explores many alternative secondary structures, using a free energy minimization algorithm for pseudoknot free secondary structures to identify promising candidate stems. In an empirical evaluation of the algorithm with 43 sequences taken from the Pseudobase database and from the literature on pseudoknotted structures, we found that overall, in terms of the sensitivity and specificity of predictions, HotKnots outperforms the well-known Pseudoknots algorithm of Rivas and Eddy and the NUPACK algorithm of Dirks and Pierce, both based on dynamic programming approaches for limited classes of pseudoknotted structures. It also outperforms the heuristic Iterated Loop Matching algorithm of Ruan and colleagues, and in many cases gives better results than the genetic algorithm from the STAR package of van Batenburg and colleagues and the recent pknotsRG-mfe algorithm of Reeder and Giegerich. The HotKnots algorithm has been implemented in C/C++ and is available from http://www.cs.ubc.ca/labs/beta/Software/HotKnots.
我们提出了HotKnots，一种用于预测包括假结在内的RNA二级结构的新启发式算法。基于迭代形成稳定茎干的简单思想，我们的算法探索了许多替代二级结构，使用自由能最小化算法来处理无假结的二级结构，以识别有前景的候选茎干。在对该算法进行实证评估时，我们使用了从Pseudobase数据库和有关假结结构的文献中选取的43个序列。我们发现，总体而言，就预测的敏感性和特异性而言，HotKnots优于著名的Rivas和Eddy的Pseudoknots算法以及Dirks和Pierce的NUPACK算法，这两种算法均基于针对有限类别的假结结构的动态规划方法。它还优于Ruan及其同事的启发式迭代环匹配算法，并且在许多情况下比van Batenburg及其同事的STAR包中的遗传算法以及Reeder和Giegerich最近的pknotsRG - mfe算法给出更好的结果。HotKnots算法已用C/C++实现，可从http://www.cs.ubc.ca/labs/beta/Software/HotKnots获取。
