Title: Improved predicting algorithm of RNA pseudoknotted structure

Authors: Zhendong Liu; Daming Zhu; Qionghai Dai

Addresses: School of Computer Science and Technology, Shandong Jianzhu University, Jinan, 250101, China; Department of Automation, Tsinghua University, Beijing, 100084, China ' School of Computer Science and Technology, Shandong University, Jinan, 250101, China ' Department of Automation, Tsinghua University, Beijing, 100084, China

Abstract: 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(n³) time and O(n²) 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.

Keywords: RNA pseudoknotted structure; algorithm; polynomial time approximation scheme; PTAS; pseudoknots; minimum free energy.

DOI: 10.1504/IJCSE.2019.099641

International Journal of Computational Science and Engineering, 2019 Vol.19 No.1, pp.64 - 70

Received: 04 Jul 2016
Accepted: 18 Oct 2016
Published online: 20 May 2019 *

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