Dynamic Iterated Algorithm for RNA Pseudoknots Prediction

Abstract:

Pseudoknots have generally been excluded from the prediction of RNA secondary structures due to its difficulty in modeling. Here we present an algorithm, dynamic iterated matching to predict RNA secondary structures including pseudoknots with O(n4) time. The method can utilize either thermodynamic or comparative information or both, thus is able to predict pseudoknots for both aligned and individual sequences. We have tested the algorithm on a number of RNA families. Comparisons show that our algorithm and loop matching method has similar accuracy and time complexity, and are more sensitive than the maximum weighted matching method and Rivas algorithm. Among the four methods, our algorithm has the best prediction specificity. The results show that our algorithm is more reliable and efficient than the other methods.

• Periodical: Applied Mechanics and Materials (Volumes 44-47)
• Pages: 3365-3369
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.44-47.3365
• Online since: December 2010
• Authors: Heng Wu Li
• Keywords: Algorithm (GA), Dynamic Matching, Pseudoknot, RNA Structure Prediction

References

[1] D.W. Staple and S.E. Butcher. PLoS Biol., Vol. 3(2005), p.213.

[2] D.H. Mathews, and D.H. Turner. Current Opinion in Structural Biology, Vol. 16(2006), pp.270-278.

[3] S. Ieong, M.Y. Kao, and T.W. Lam. Journal of Computational Biology, Vol. 6(2003), pp.981-995.

[4] J. Ren, B. Rastegari, and H.H. Hoos. RNA, Vol. 11(2005), pp.1494-1504.

[5] E. Rivas and S. Eddy. J. Mol. Biol., Vol. 285(1999), p.2053–(2068).

[6] L. Hengwu, Z. Daming, L. Zhendong, and L. Hong. Vol. 17(2006), pp.717-724.

[7] J. Tabaska, R. Cary, H. Gabow, and G. Stormo. Bioinformatics, Vol. 14(1998), pp.691-699.

DOI: 10.1093/bioinformatics/14.8.691

[8] J. Ruan, G. D. Stormo and W. Zhang. Bioinformatics, Vol. 20(2004), pp.58-66.

[9] W. Chuanming, P. Min and C. Kui. Nature, Vol. 26(2004), pp.249-255.