文章基本信息

标题：An Improved Algorithm for RNA Secondary Structure Prediction
本地全文：下载
作者：Rune B. Lyngsø ; Michael Zuker ; Christian N. S. Pedersen 等
期刊名称：BRICS Report Series
印刷版ISSN：0909-0878
出版年度：1999
卷号：6
期号：15
出版社：Aarhus University
摘要：Though not as abundant in known biological processes as proteins, RNA molecules serve as more than mere intermediaries between DNA and proteins, e.g. as catalytic molecules. Furthermore, RNA secondary structure prediction based on free energy rules for stacking and loop formation remains one of the few major breakthroughs in the field of structure prediction. We present a new method to evaluate all possible internal loops of size at most k in an RNA sequence, s, in time O(k|s|^2); this is an improvement from the previously used method that uses time O(k^2|s|^2). For unlimited loop size this improves the overall complexity of evaluating RNA secondary structures from O(|s|^4) to O(|s|^3) and the method applies equally well to finding the optimal structure and calculating the equilibrium partition function. We use our method to examine the soundness of setting k = 30, a commonly used heuristic.