标题：Approximation algorithm of RNA folding including pseudoknots
作者机构：[Liu, Zhendong ] School of Computer Science and Technology, Shandong University, Jinan 250101, China;[Liu, Zhendong ] School of Computer Science and T 更多
来源：International Review on Computers and Software
关键词：Approximation algorithm; MFE principle; N-Stem; Pseudoknots; RNA structure
摘要：Computational prediction of RNA secondary structure is among the few problems that can be solved satisfactory in polynomial. Based on MFE principle and the relative stability of the n-stems in RNA molecules, Minimum Free Energy method is adopted widely to predict RNA secondary structure, an improved approximation algorithm is presented to predict RNA pseudoknotted structure, the algorithm can solve arbitrary nested or parallel pseudoknots,the algorithm takes O(n3) time and O(n2) space. This algorithm not only reduces the time complexity to O(n3), but also widens the maximum length of the sequence. The preliminary experimental test on the RNA sub-sequences in PseudoBase confirm that the algorithm outperforms other known algorithms in predicting accuracy, specificity and sensitivity. © 2012 Praise Worthy Prize S.r.l. - All rights reserved.