Abstract
Secondary structure prediction (with or without pseudoknots) of an RNA molecule is a well-known problem in computational biology. Most of the existing algorithms have an assumption that each nucleotide can interact with at most one other nucleotide. This assumption is not valid for triple helix structure (a pseudoknotted structure with tertiary interactions). As these structures are found to be important in many biological processes, it is desirable to develop a prediction tool for these structures. We provide the first structural prediction algorithm to handle triple helix structures. Our algorithm runs in O(n 3) time where n is the length of input RNA sequence. The accuracy of the prediction is reasonably high, with average sensitivity and specificity over 80% for base pairs, and over 70% for tertiary interactions.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Lyngso, R., Pedersen, C.: A dynamic programming algorithm for RNA structure prediction including pseudoknots. In: Proc. of the Fourth Annual International Conferences on Compututational Molecular Biology (RECOMB 2000). ACM Press (2000)
Akutsu, T.: Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots. Discrete Applied Mathematics 104, 45–62 (2000)
Chen, H., Condon, A., Jabbari, H.: An O(n 5) algorithm for MFE prediction of kissing hairpins and 4- chains in nucleic acids. Journal of Computational Biology 16(6), 803–815 (2009)
Dirks, R., Pierce, N.: A partition function algorithm for nucleic acid secondary structure including pseudoknots. Journal of Comput. Chem. 24(13), 1664–1677 (2003)
Reeder, J., Giegerich, R.: Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics 5, 104 (2004)
Rivas, E., Eddy, S.: A dynamic programming algorithm for RNA structure prediction including pseudoknots. Journal of Molecular Biology 285(5), 2053–2068 (1999)
Uemura, Y., Hasegawa, A., Kobayashi, S., Yokomori, T.: Tree adjoining grammars for RNA structure prediction. Theoretical Computer Science 210, 277–303 (1999)
Qiao, F., Cech, T.R.: Triple-helix structure in telomerase RNA contributes to catalysis. Nature Structural and Molecular Biology 15(6), 634–640 (2008)
Chen, J.L., Greider, C.W.: Functional analysis of the pseudoknot structure in human telomerase RNA. Proc. Natl. Acad. Sci. USA 102, 8080–8085 (2005)
Theimer, C.A., Blois, C.A., Feigon, J.: Structure of the human telomerase RNA pseudoknot reveals conserved tertiary interactions essential for function. Molecular Cell 17, 671–682 (2005)
Su, L., Chen, L., Egli, M., Berger, J.M., Rich, A.: Minor groove RNA triplex in the crystal structure of a ribosomal frameshifting viral pseudoknot. Nature Structural Biology 6(3), 285–292 (1999)
Chen, X., Chamorro, M., Lee, S.I., Shen, L.X., Hines, J.V., Tinoco Jr., I., Varmus, H.E.: Structural and functional studies of retroviral RNA pseudoknots involved in ribosomal frameshifting: nucleotides at the junction of the two stems are important for efficient ribosomal frameshifting. EMBO 14(4), 842–852 (1995)
Siederdissen, C., Bernhart, S., Stadler, P., Hofacker, I.: A folding algorithm for extended RNA secondary structures. Bioinformatics 27, i29–i36 (2011) (ISMB 2011)
Wong, T.K., Lam, T., Yiu, S.: Structural alignment of RNA with triple helix structure. Journal of Computational Biology 19(4), 365–378 (2012)
Matsui, H., Sato, K., Sakakibara, Y.: Pair stochastic tree adjoining grammars for aligning and predicting pseudoknot RNA structures. Bioinformatics 21, 2611–2617 (2005)
Dowell, R.D., Eddy, S.R.: Evaluation of several lightweight stochastic context-free grammars for rna secondary structure prediction. BMC Bioinformatics 5, 71 (2004)
Durbin, R., Eddy, S.R., Krogh, A., Mitchison, G.: Covariance models: SCFG-based RNA profiles. In: Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press (1998)
Chastain, M., Tinoco, I.J.: A base-triple structural domain in RNA. Biochemistry 31, 12733–12741 (1992)
Dawson, W.K., Fujiwara, K., Kawai, G.: Prediction of RNA pseudoknots using heuristic modeling with mapping and sequential folding. PLoS One 2(9), e905 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hsu, BY., Wong, T.K.F., Hon, WK., Liu, X., Lam, TW., Yiu, SM. (2013). A Local Structural Prediction Algorithm for RNA Triple Helix Structure. In: Ngom, A., Formenti, E., Hao, JK., Zhao, XM., van Laarhoven, T. (eds) Pattern Recognition in Bioinformatics. PRIB 2013. Lecture Notes in Computer Science(), vol 7986. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39159-0_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-39159-0_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39158-3
Online ISBN: 978-3-642-39159-0
eBook Packages: Computer ScienceComputer Science (R0)
