标题：An Approximation Scheme for RNA folding Structure Prediction including Pseudoknots
作者：Liu, Zhendong; Zhu, Daming; Cui, Wei; Liu, Nan
作者机构：[Liu, Zhendong; Zhu, Daming] Shandong Univ, Sch Comp Sci & Technol, Jinan 250100, Peoples R China.; [Liu, Zhendong; Cui, Wei; Liu, Nan] Shandong Jia 更多
会议名称：9th International Conference on Computational Intelligence and Security (CIS)
会议日期：DEC 14-15, 2013
来源：2013 9TH INTERNATIONAL CONFERENCE ON COMPUTATIONAL INTELLIGENCE AND SECURITY (CIS)
关键词：pseudoknotted structure; minimum free energy; stem; Polynomial Time; Approximation Schem; stacking
摘要：The paper further investigates the computational problem and complexity of predicting Ribonucleic Acid structure. In order to find a way to optimize the Ribonucleic Acid pseudoknotted structure, we investigate the Ribonucleic Acid pseudoknotted structure based on thermal dynamic model, computational methods, minimum free energy are adopted to predict Ribonucleic Acid structure. The contribution of this paper is to obtain an efficient Approximation algorithm for finding RNA pseudoknotted structure, compared with other algorithms, the algorithm takes O(n(3)) time and O(n(2)) space. The experimental test in PseudoBase shows that the algorithm is more effective and exact than other algorithms, and the algorithm can predict arbitrary pseudoknots. And we also give a proof of existing 1+epsilon (epsilon>0) Polynomial Time Approximation Scheme(PTAS) in Searching Maximum Number of Stackings.