Close window
Kopfgrafik

RNA structure and shape combinatorics

Background


Abstract shapes were introduced by Giegerich et al in


Combinatorics of abstract shapes were recently studied in


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
and write to us if that does not help.