Predicting scheme of RNA folding structure including pseudoknots
by Zhendong Liu; Daming Zhu; Hongwei Ma
International Journal of Sensor Networks (IJSNET), Vol. 16, No. 4, 2014

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.

Online publication date: Mon, 26-Jan-2015

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Sensor Networks (IJSNET):
Login with your Inderscience username and password:

Username:        Password:          Forgotten your password?

Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com