Inverse folding of RNA pseudoknot structures

Gao, James ZM; Li, Linda YM; Reidys, Christian M

Before considering an inverse folding algorithm into specific RNA structures one has to have at least some rationale as to why there exists one sequence realizing a given target as mfe-configuration. In fact this is, on the level of entire folding maps, guaranteed by the combinatorics of the target structures alone. It has been shown in [31] , that the numbers of 3-noncrossing RNA pseudoknot structures, satisfying the biophysical constraints grows asymptotically as c 3 n -5 2.03 n , where c 3 >0 is some explicitly known constant. In view of the central limit theorems of [32] , this fact implies the existence of extended (exponentially large) sets of sequences that all fold into one 3-noncrossing RNA pseudoknot structure, S. In other words, the combinatorics of 3-noncrossing RNA structures alone implies that there are many sequences mapping (folding) into a single structure. The set of all such sequences is called the neutral network of the structure S [33, 34] , see Figure 7 . The term "neutral network" as opposed to "neutral set" stems from giant component results of random induced subgraphs of ncubes. That is, neutral networks are typically connected in sequence space.