Download Untitled - CLC bio

CHAPTER 19. RNA STRUCTURE
294
paper is to describe a very popular way of doing this, namely free energy minimization. For an
in-depth review of algorithmic details, we refer the reader to [Mathews and Turner, 2006].
19.5.1
The algorithm
Consider an RNA molecule and one of its possible structures S1 . In a stable solution there
will be an equilibrium between unstructured RNA strands and RNA strands folded into S1 . The
propensity of a strand to leave a structure such as S1 (the stability of S1 ), is determined by the
free energy change involved in its formation. The structure with the lowest free energy (Smin ) is
the most stable and will also be the most represented structure at equilibrium. The objective of
minimum free energy (MFE) folding is therefore to identify Smin amongst all possible structures.
In the following, we only consider structures without pseudoknots, i.e. structures that do not
contain any non-nested base pairs.
Under this assumption, a sequence can be folded into a single coherent structure or several
sequential structures that are joined by unstructured regions. Each of these structures is a union
of well described structure elements (see below for a description of these). The free energy
for a given structure is calculated by an additive nearest neighbor model. Additive, means that
the total free energy of a secondary structure is the sum of the free energies of its individual
structural elements. Nearest neighbor, means that the free energy of each structure element
depends only on the residues it contains and on the most adjacent Watson-Crick base pairs.
The simplest method to identify Smin would be to explicitly generate all possible structures, but
it can be shown that the number of possible structures for a sequence grows exponentially with
the sequence length [Zuker and Sankoff, 1984] leaving this approach unfeasible. Fortunately,
a two step algorithm can be constructed which implicitly surveys all possible structures without
explicitly generating the structures [Zuker and Stiegler, 1981]: The first step determines the free
energy for each possible sequence fragment starting with the shortest fragments. Here, the
lowest free energy for longer fragments can be expediently calculated from the free energies of
the smaller sub-sequences they contain. When this process reaches the longest fragment, i.e.,
the complete sequence, the MFE of the entire molecule is known. The second step is called
traceback, and uses all the free energies computed in the first step to determine Smin - the exact
structure associated with the MFE. Acceptable calculation speed is achieved by using dynamic
programming where sub-sequence results are saved to avoid recalculation. However, this comes
at the price of a higher requirement for computer memory.
The structure element energies that are used in the recursions of these two steps, are derived
from empirical calorimetric experiments performed on small molecules see e.g. [Mathews et al.,
1999].
Suboptimal structures determination
A number of known factors violate the assumptions that are implicit in MFE structure prediction.
[Schroeder et al., 1999] and [Chen et al., 2004] have shown experimental indications that
the thermodynamic parameters are sequence dependent. Moreover, [Longfellow et al., 1990]
and [Kierzek et al., 1999], have demonstrated that some structural elements show non-nearest
neighbor effects. Finally, single stranded nucleotides in multi loops are known to influence
stability [Mathews and Turner, 2002].
These phenomena can be expected to limit the accuracy of RNA secondary structure prediction