New Algorithm for Predicting RNA Secondary Structure with Pseudoknots

Abstract:

Pseudoknots are complicated and stable RNA structure. Based on the idea of iteratively forming stable stems, and the character that the stems in RNA molecules are relatively stable, an algorithm is presented to predict RNA secondary structure including pseudoknots, it is an improvement from the previously used algorithm ,the algorithm takes O(n³) time and O(n²) sapce , in predicting accuracy, it outperforms other known algorithm of RNA secondary structure prediction, its performance is tested with the RNA sub-sequences in PseudoBase. The experimental results indicate that the algorithm has good specificity and sensitivity.

• Periodical: Advanced Materials Research (Volumes 532-533)
• Pages: 1796-1799
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.532-533.1796
• Online since: June 2012
• Authors: Zhen Dong Liu, Da Ming Zhu
• Keywords: Algorithm (GA), Free Energy, Pseudoknot, RNA Secondary Structure, STEM

References

[1] LyngsΦ R B, Christian N S. Pseudoknots in RNA Secondary Structure: Proceedings of Recomb, Tokyo Japan USA, (2000).

[2] Rivals E, Eddy S. A Dynamic Programming Algorithm for RNA Structure Prediction Including Pseudoknots: Journal of Molecular Biology. (1999), p.285: 2053-(2068).

DOI: 10.1006/jmbi.1998.2436

[3] Jens Reeder, and Robert Giegerich. Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics: BMC Bioinformatics. (2004), p.5: 104.

[4] Michael Zuker. On finding all suboptimal foldings of an RNA molecule: Science, (1989), 244: pp.48-52.

DOI: 10.1126/science.2468181

[5] Kolk M.H., vanderGraff,M., Wijmenga S.S., Pleij C.W.A., Heus H.A., Hilbers C.W., NMR structure of a classical pseudoknots: interplay of single- and double-stranded RNA: Science, Vol. 280, (1998), pp.434-438.

DOI: 10.1126/science.280.5362.434

[6] Ieong,S., Kao M.Y., Lam T.W., Sung W.K., Yin S.M. Prediction RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs: Journal of Computational Biology, (2003), Vol. 6, pp.981-995.

DOI: 10.1089/106652703322756186

[7] Jihong Ren, BaharaK RastegarI, ANNE CONDON, and HOLGER H. HOOS. HotKnots: Heuristic prediction of RNA secondary structures including pseudoknots: RNA, (2005) , Vol. 11, No. 10, p.1494–1504.

DOI: 10.1261/rna.7284905

[8] TurnerD H, Sugimoto N, Freier S M. RNA Structure Prediction: Annual Rewiew of Biophysics Chemistry. (1988), 17: pp.167-192.

[9] Jaeger JA, Turner DH, Zuker M. Improved predictions of secondary structures for RNA［J］: Proc Natl Acad Sci USA, (1989), Vol. 86, No. 20, pp.7706-7710.

DOI: 10.1073/pnas.86.20.7706

[10] Z.D. Liu H.W. Li, and D.M. Zhu. the Predicting Algorithm of RNA Secondary Structure for Computing Maximum Stacking: The Journal of NanjingUniversity, (2005), Vol. 41, No. 5, pp.532-537.

[11] Zhendong Liu, Hengwu Li, Daming Zhu. A predicting algorithm of RNA secondary structure based on stems: kybernetes. (2010), Vol 39, issue6, pp.1050-1057.

DOI: 10.1108/03684921011046825

[12] PseudoBase: Theoretical Biology.