Folding 3-Noncrossing RNA Pseudoknot Structures

Abstract

Abstract

In this article, we present the novel ab initio folding algorithm cross, which generates minimum free energy (mfe), 3-noncrossing, canonical RNA structures. Here an RNA structure is 3-noncrossing if it does not contain three or more mutually crossing arcs and canonical, if each of its stacks has size greater or equal than two. Our notion of mfe-structure is based on a specific concept of pseudoknots and respective loop-based energy parameters. The algorithm decomposes into three subroutines: first the inductive construction of motifs and their associated shadows, second the generation of the (rooted) skeleta-trees and third the saturation of the skeleta via context dependent dynamic programming routines.