标题：Approximation Algorithm of the RNA Pseudoknotted Structure Prediction Baesed on MFE
作者：Liu, Zhendong; Li, Yuejun; Zhang, Peng; Yang, Zhaohui
作者机构：[Liu, Zhendong; Li, Yuejun; Yang, Zhaohui] Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Shandong, Peoples R China.; [Liu, Zhendong; 更多
会议名称：IEEE International Conference on Information and Automation (ICIA)
会议日期：AUG 26-28, 2013
来源：2013 IEEE INTERNATIONAL CONFERENCE ON INFORMATION AND AUTOMATION (ICIA)
关键词：RNA Pseudoknotted structure; Minimum free energy; Stacking pairs;; Approximation algorithm
摘要：Determination of Ribonucleic Acid structure is challenging, in order to optimize the RNA pseudoknotted structure, the paper investigates the computational problem and complexity of predicting RNA structure. A new computational method and model with minimum free energy are adopted to predict RNA structure. The main contribution of the paper is to achieves an efficient approximation algorithm for finding RNA pseudoknotted structure and nested structures. We have compared with other algorithms in time complexity and space complexity, the approximation algorithm takes O(n(3)) time and O(n(2)) space, where n is the length of the RNA sequences. The experimental tests for a large database of RNA show that the algorithm is more exact and effective than the algorithms, the algorithm can predict arbitrary pseudoknots, and improve the a predicting accuracy.