Predicting Model and Algorithm in RNA Folding Structure Including Pseudoknots

The prediction of RNA structure with pseudoknots is NP-hard problem. According to.minimum free energy models and computational methods, we investigate the RNA.pseudoknotted structures and their characteristics. The paper presents an efficient algorithm for.predicting RNA structures with pseudoknots, and the algorithm runs in O(n3) time and O(n2).space. The experimental tests in Rfam10.1 and PseudoBase indicate that the algorithm is more.effective and precise, and the algorithm can predict arbitrary pseudoknots. And through our.research, we can draw that there exists an 1 + ε (ε > 0) polynomial time approximation scheme in searching maximum number of stackings, and we give the proof of the approximation scheme in RNA pseudoknotted structures

含假结的RNA结构预测是NP难问题。根据最小自由能模型和计算方法，我们研究了RNA假结结构及其特征。本文提出了一种预测含假结RNA结构的高效算法，该算法的时间复杂度为O(n³)，空间复杂度为O(n²)。在Rfam10.1和PseudoBase上的实验测试表明，该算法更有效、更精确，并且能够预测任意假结。通过我们的研究，我们可以得出在寻找最大堆叠数方面存在一个1 + ε（ε>0）多项式时间近似方案，并且我们给出了RNA假结结构中近似方案的证明。