Abstract
Analysis of the folding space of RNA generally suffers from its exponential size. With classified Dynamic Programming algorithms, it is possible to alleviate this burden and to analyse the folding space of RNA in great depth. Key to classified DP is that the search space is partitioned into classes based on an on-the-fly computed feature. A class-wise evaluation is then used to compute class-wide properties, such as the lowest free energy structure for each class, or aggregate properties, such as the class’ probability. In this paper we describe the well-known shape and hishape abstraction of RNA structures, their power to help better understand RNA function and related methods that are based on these abstractions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
McCaskill JS (1990) The equilibrium partition function and base pair binding probabilities for RNA secondary structure. Biopolymers 29:1105–1119
Hofacker IL et al. (1994) Fast folding and comparison of RNA secondary structures. Monatshefte Für Chem Chem Mon 125:167–188
Giegerich R, Voß B, Rehmsmeier M (2004) Abstract shapes of RNA. Nucl Acids Res 32:4843–4851
Giegerich R (2000) A systematic approach to dynamic programming in bioinformatics. Bioinformatics 16:665–677
Giegerich R, Meyer C, Steffen P (2004) A discipline of dynamic programming over sequence data. Sci Comput Programm 51:215–263
Sauthoff G, Janssen S, Giegerich R (2011) Bellman’s GAP: a declarative language for dynamic programming. In: Proceedings of the 13th International ACM SIGPLAN Symposium on Principles and Practices of Declarative Programming. ACM, New York (2011), pp 29–40
Janssen S, Giegerich R (2015) The RNA shapes studio. Bioinformatics 31:423–425
Bellman R (1952) On the theory of dynamic programming. Proc Natl Acad Sci U S A 38:716–719
Bellman R (1954) The theory of dynamic programming. Bull Amer Math Soc 60:503–515
Bellman R (1957) Dynamic Programming, 1st edn. Princeton University Press, Princeton
Steffen P, Giegerich R (2005) Versatile and declarative dynamic programming using pair algebras. BMC Bioinformat 6:224
Janssen S, Schudoma C, Steger G, Giegerich R, Lost in folding space? comparing four variants of the thermodynamic model for RNA secondary structure prediction. BMC Bioinformat 12:429
Waterman MS (1995) Introduction to Computational Biology: Maps, Sequences and Genomes. CRC Press, Boca Raton
Lorenz W, Ponty Y, Clote P (2008) Asymptotics of RNA shapes. J Comput Biol 15:31–63
Nebel ME, Scheid A (2009) On quantitative effects of RNA shape abstraction. Theory Biosci 128:211
Voß B, Giegerich R, Rehmsmeier M (2006) Complete probabilistic analysis of RNA shapes. BMC Biol 4:5
Ding Y, Lawrence CE (2003) A statistical sampling algorithm for RNA secondary structure prediction. Nucl Acids Res 31:7280–7301
Janssen S, Giegerich R (2010) Faster computation of exact RNA shape probabilities. Bioinformatics 26:632–639
Sankoff D (1985) Simultaneous solution of the RNA folding, alignment and protosequence problems. SIAM J Appl Math 45:810–825
Mathews DH, Turner DH (2002) Dynalign: an algorithm for finding the secondary structure common to two RNA sequences. J Mol Biol 317:191–203
Havgaard JH, Lyngso RB, Gorodkin J (2005) The FOLDALIGN web server for pair-wise structural RNA alignment and mutual motif search. Nucl Acids Res 33(Suppl_2):W650–653
Will S, Otto C, Miladi M, Möhl M, Backofen R (2015) SPARSE: quadratic time simultaneous alignment and folding of RNAs without sequence-based heuristics. Bioinformatics btv185:2489–2496
Hofacker IL, Fekete M, Stadler PF (2002) Secondary structure prediction for aligned RNA sequences. J Mol Biol 319:1059–1066
Voß B (2006) Structural analysis of aligned RNAs. Nucl Acids Res 34:5471–5481
Reeder J, Giegerich R (2005) Consensus shapes: an alternative to the Sankoff algorithm for RNA consensus structure prediction. Bioinformatics 21:3516–3523
Huang J, Backofen R, Voß B (2012) Abstract folding space analysis based on helices. RNA 18:2135–2147
Shapiro BA, Zhang KZ (1990) Comparing multiple RNA secondary structures using tree comparisons. Comput Appl Biosci 6:309–318
Flamm C, Fontana W, Hofacker IL, Schuster P (2000) RNA folding at elementary step resolution. RNA. 6:325–338
Flamm C, Hofacker IL, Maurer-Stroh S, Stadler PF, Zehl M (2001) Design of multistable RNA molecules. RNA 7:254–265
Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1:269–271
Wuchty S, Fontana W, Hofacker IL, Schuster P (1999) Complete suboptimal folding of RNA and the stability of secondary structures. Biopolymers 49:145–165
Huang J, Voß B (2014) Analysing RNA-kinetics based on folding space abstraction. BMC Bioinformat 15:60
Wolfinger MT, Svrcek-Seiler WA, Flamm C, Hofacker IL, Stadler PF (2004) Efficient computation of RNA folding dynamics. J Phys A Math Gen 37:4731
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Science+Business Media, LLC, part of Springer Nature
About this protocol
Cite this protocol
Voß, B. (2024). Classified Dynamic Programming in RNA Structure Analysis. In: Lorenz, R. (eds) RNA Folding. Methods in Molecular Biology, vol 2726. Humana, New York, NY. https://doi.org/10.1007/978-1-0716-3519-3_6
Download citation
DOI: https://doi.org/10.1007/978-1-0716-3519-3_6
Published:
Publisher Name: Humana, New York, NY
Print ISBN: 978-1-0716-3518-6
Online ISBN: 978-1-0716-3519-3
eBook Packages: Springer Protocols