RNA structure and shape combinatorics

Background

Abstract shapes were introduced by Giegerich et al in

Giegerich R,Voss B, Rehmsmeier M: Abstract Shapes of RNA. in Nucleic Acids Res., 32(16) , Pages:4843-4851, 2004
Voß B, Giegerich R, Rehmsmeier M: Complete probabilistic analysis of RNA shapes in BMC Biology, 4(5) , 2006

Combinatorics of abstract shapes were recently studied in

Lorenz WA, Ponty Y, Clote P: Aymptotics of RNA shapes. J Comput Biol. 2008 Jan-Feb;15(1):31-63.
Nebel ME, Scheid A: On Abstract Shapes of RNA Preprint; submitted

This website allows for empirical studies of structure and shape combinatorics. It assumes you have some background in the framework of algebraic dynamic programming, which is used to implement these analyses. The website provides

a non-ambiguous RNA folding grammar,
level 1 to 5 shape abstraction algebras, as currently used in the RNAshapes tool
a limited way to describe user-defined shape abstractions
counting and printing algebras
base pair maximization and stacked pair maximization algebras
an algebra to compute expected numbers of structures. This new algebra is adapted from Giegerich R : Explaining and Controlling Ambiguity in Dynamic Programming in Proc. Combinatorial Pattern Matching, Pages:46-59 (Springer) , 2000

Modes of Operation

While each evaluation algebra serves a meaningful purpose by itself (see algebra explanation), the fun comes from using products of algebras. You can use up to three algebras in a product here, although theoretically, there is no limit. Note that the product is associative.
Simply speaking, a product algebra A *** B first evaluates the folding space of a sequence under algebra A, and thereafter, the candidates returned by A are evaluated under Algebra B. The product A *** B is always defined, but does not always satisfy Bellman's Principle of Optimality. If a product algebra returns something that looks weird, please check the formal definition of products in

Steffen, P. and Giegerich, R.: Versatile and declarative dynamic programming using pair algebras in BMC Bioinformatics, 6(224) , 2005

and write to us if that does not help.


RNA structure and shape combinatorics Background Abstract shapes were introduced by Giegerich et al in Giegerich R,Voss B, Rehmsmeier M: Abstract Shapes of RNA. in Nucleic Acids Res., 32(16) , Pages:4843-4851, 2004 Voß B, Giegerich R, Rehmsmeier M: Complete probabilistic analysis of RNA shapes in BMC Biology, 4(5) , 2006 Combinatorics of abstract shapes were recently studied in Lorenz WA, Ponty Y, Clote P: Aymptotics of RNA shapes. J Comput Biol. 2008 Jan-Feb;15(1):31-63. Nebel ME, Scheid A: On Abstract Shapes of RNA Preprint; submitted This website allows for empirical studies of structure and shape combinatorics. It assumes you have some background in the framework of algebraic dynamic programming, which is used to implement these analyses. The website provides a non-ambiguous RNA folding grammar, level 1 to 5 shape abstraction algebras, as currently used in the RNAshapes tool a limited way to describe user-defined shape abstractions counting and printing algebras base pair maximization and stacked pair maximization algebras an algebra to compute expected numbers of structures. This new algebra is adapted from Giegerich R : Explaining and Controlling Ambiguity in Dynamic Programming in Proc. Combinatorial Pattern Matching, Pages:46-59 (Springer) , 2000 Modes of Operation While each evaluation algebra serves a meaningful purpose by itself (see algebra explanation), the fun comes from using products of algebras. You can use up to three algebras in a product here, although theoretically, there is no limit. Note that the product is associative. Simply speaking, a product algebra A * B first evaluates the folding space of a sequence under algebra A, and thereafter, the candidates returned by A are evaluated under Algebra B. The product A * B is always defined, but does not always satisfy Bellman's Principle of Optimality. If a product algebra returns something that looks weird, please check the formal definition of products in Steffen, P. and Giegerich, R.: Versatile and declarative dynamic programming using pair algebras in BMC Bioinformatics, 6(224) , 2005 and write to us if that does not help.