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 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article