Title: Predicting scheme of RNA folding structure including pseudoknots
Authors: Zhendong Liu; Daming Zhu; Hongwei Ma
Addresses: School of Computer Science and Technology, Shandong Jianzhu University & Shandong University, Jinan 250101, China ' School of Computer Science and Technology, Shandong University, Jinan 250101, China ' School of Computer Science and Technology, Shandong Jianzhu University, Jinan 250101, China
Abstract: The problem of predicting ribonucleic acid (RNA) structure with pseudoknots makes it NP-hard. To find optimal RNA pseudoknotted structure, we investigate the RNA pseudoknotted structure based on computational methods and models with minimum free energy (MFE). The contribution of this paper is to obtain an efficient algorithm for predicting RNA pseudoknotted structure with pseudoknots, and the algorithm takes O(n³) time and O(n²) space. The experimental test in PseudoBase and Rfam10.1 shows that the proposed algorithm is more effective and precise than other compared algorithms, and can predict arbitrary pseudoknots. Furthermore, we prove that there exists 1 + ε (ε > 0) polynomial time approximation scheme (PTAS) in searching maximum number of stackings. We also present a 2-approximation algorithm and analyse the approximation algorithm.
Keywords: RNA structure; pseudoknots; stem; polynomial time approximation; RNA folding structure; pseudoknots; minimum free energy; bioinformatics.
DOI: 10.1504/IJSNET.2014.067096
International Journal of Sensor Networks, 2014 Vol.16 No.4, pp.229 - 235
Received: 21 Jun 2014
Accepted: 24 Jun 2014
Published online: 26 Jan 2015 *