FoldRNA - RNA secondary structure prediction through energy minimization

Program for RNA secondary structure prediction based on dynamic programming (Nussinov and Jackonson, 1978, Zuker, 2005). For energy calculation nearest neighbor energy rules are used. Pseudoknots are not allowed.

FoldRNA uses energy parameters similar to mfold.
FoldRNA uses energy parameters mainly from:
Turner D.H. and Sugimoto N. (1988) RNA structure prediction Ann.Rev.Biophys.Biophys.Chem. 17, pp. 167-92; Table 1

METHOD DESCRIPTION:
FoldRNA predicts optimal and suboptimal secondary structures of RNA using dynamic algorithm for energy minimization .
Solution of a long sequence is decomposed into solutions of smaller problems:
Let's define E(i,j) = minimum energy for subchain starting at i and ending at j, and a(i,j) = energy of pair i,j.
If values E(i,j) are calculated for line which is maximally close to main diagonal of matrix LxL, where L = sequence length. (min. hairpin loop should have size not less than 3 nt), then we can find step by step this values for lines next after this, using the following recursion scheme (4 possible cases):

```   Recursion (iteration over length):

E(i,j)=min{
E(i+1,j),

E(i,j-1),

E(i+1,j-1)+a(i,j),

min  ( E(i,k) + E(k+1,j) )
i<k<j

}

```

When all matrix is filled, the programs searches for lowest value of E(i,j), and then restores by the matrix corresponding secondary structure and sends it to output.

```Output example

Program RNAfold (Softberry Inc.) | Version 1.0

FoldRNA Vienna format:
Length: 183 Energy: -80.0 78% in Helices

10        20        30        40        50        60
GUGAAUGAAAGAGUUGGGACAAGAGAAACGCAAAGAAACUGACAGAAGAGAGUGAGCACA
((((..((.(((((((((((((((((.(((..((((..(((((((((((((((((((((.
70        80        90       100       110       120
CAAAGGCAAUUUGCAUAUCAUUGCACUUGCUUCUCUUGCGUGCUCACUGCUCUUUCUGUC
(((((((((..((((......)))).))))))...))).))))))))).))))).)))))
130       140       150       160       170       180
AGAUUCCGGUGCUGAUCUCUUUGGCCUGUCUUCGUUCUCUAUGUCUCAAUCUCUCUCUAU
))....(((.(((((.....)))))))))))))))))))).))))))))).))).))..)
190
CAC
)))

FoldRNA GCG format:
Length: 183 Energy: -80.0

1 G       0    2  183    1
2 U       1    3  182    2
3 G       2    4  181    3
4 A       3    5  180    4
5 A       4    6    0    5
6 U       5    7    0    6
7 G       6    8  177    7
8 A       7    9  176    8
9 A       8   10    0    9
10 A       9   11  174   10
11 G      10   12  173   11
12 A      11   13  172   12
13 G      12   14  170   13
14 U      13   15  169   14
15 U      14   16  168   15
16 G      15   17  167   16
17 G      16   18  166   17
18 G      17   19  165   18
19 A      18   20  164   19
20 C      19   21  163   20
21 A      20   22  162   21
22 A      21   23  160   22
23 G      22   24  159   23
24 A      23   25  158   24
25 G      24   26  157   25
26 A      25   27  156   26
27 A      26   28    0   27
28 A      27   29  155   28
29 C      28   30  154   29
30 G      29   31  153   30
31 C      30   32    0   31
32 A      31   33    0   32
33 A      32   34  152   33
34 A      33   35  151   34
35 G      34   36  150   35
36 A      35   37  149   36
37 A      36   38    0   37
38 A      37   39    0   38
39 C      38   40  122   39
40 U      39   41  121   40
41 G      40   42  120   41
42 A      41   43  119   42
43 C      42   44  118   43
44 A      43   45  117   44
45 G      44   46  116   45
46 A      45   47  114   46
47 A      46   48  113   47
48 G      47   49  112   48
49 A      48   50  111   49
50 G      49   51  110   50
51 A      50   52  108   51
52 G      51   53  107   52
53 U      52   54  106   53
54 G      53   55  105   54
55 A      54   56  104   55
56 G      55   57  103   56
57 C      56   58  102   57
58 A      57   59  101   58
59 C      58   60  100   59
60 A      59   61    0   60
61 C      60   62   98   61
62 A      61   63   97   62
63 A      62   64   96   63
64 A      63   65   92   64
65 G      64   66   91   65
66 G      65   67   90   66
67 C      66   68   89   67
68 A      67   69   88   68
69 A      68   70   87   69
70 U      69   71    0   70
71 U      70   72    0   71
72 U      71   73   85   72
73 G      72   74   84   73
74 C      73   75   83   74
75 A      74   76   82   75
76 U      75   77    0   76
77 A      76   78    0   77
78 U      77   79    0   78
79 C      78   80    0   79
80 A      79   81    0   80
81 U      80   82    0   81
82 U      81   83   75   82
83 G      82   84   74   83
84 C      83   85   73   84
85 A      84   86   72   85
86 C      85   87    0   86
87 U      86   88   69   87
88 U      87   89   68   88
89 G      88   90   67   89
90 C      89   91   66   90
91 U      90   92   65   91
92 U      91   93   64   92
93 C      92   94    0   93
94 U      93   95    0   94
95 C      94   96    0   95
96 U      95   97   63   96
97 U      96   98   62   97
98 G      97   99   61   98
99 C      98  100    0   99
100 G      99  101   59  100
101 U     100  102   58  101
102 G     101  103   57  102
103 C     102  104   56  103
104 U     103  105   55  104
105 C     104  106   54  105
106 A     105  107   53  106
107 C     106  108   52  107
108 U     107  109   51  108
109 G     108  110    0  109
110 C     109  111   50  110
111 U     110  112   49  111
112 C     111  113   48  112
113 U     112  114   47  113
114 U     113  115   46  114
115 U     114  116    0  115
116 C     115  117   45  116
117 U     116  118   44  117
118 G     117  119   43  118
119 U     118  120   42  119
120 C     119  121   41  120
121 A     120  122   40  121
122 G     121  123   39  122
123 A     122  124    0  123
124 U     123  125    0  124
125 U     124  126    0  125
126 C     125  127    0  126
127 C     126  128  148  127
128 G     127  129  147  128
129 G     128  130  146  129
130 U     129  131    0  130
131 G     130  132  145  131
132 C     131  133  144  132
133 U     132  134  143  133
134 G     133  135  142  134
135 A     134  136  141  135
136 U     135  137    0  136
137 C     136  138    0  137
138 U     137  139    0  138
139 C     138  140    0  139
140 U     139  141    0  140
141 U     140  142  135  141
142 U     141  143  134  142
143 G     142  144  133  143
144 G     143  145  132  144
145 C     144  146  131  145
146 C     145  147  129  146
147 U     146  148  128  147
148 G     147  149  127  148
149 U     148  150   36  149
150 C     149  151   35  150
151 U     150  152   34  151
152 U     151  153   33  152
153 C     152  154   30  153
154 G     153  155   29  154
155 U     154  156   28  155
156 U     155  157   26  156
157 C     156  158   25  157
158 U     157  159   24  158
159 C     158  160   23  159
160 U     159  161   22  160
161 A     160  162    0  161
162 U     161  163   21  162
163 G     162  164   20  163
164 U     163  165   19  164
165 C     164  166   18  165
166 U     165  167   17  166
167 C     166  168   16  167
168 A     167  169   15  168
169 A     168  170   14  169
170 U     169  171   13  170
171 C     170  172    0  171
172 U     171  173   12  172
173 C     172  174   11  173
174 U     173  175   10  174
175 C     174  176    0  175
176 U     175  177    8  176
177 C     176  178    7  177
178 U     177  179    0  178
179 A     178  180    0  179
180 U     179  181    4  180
181 C     180  182    3  181
182 A     181  183    2  182
183 C     182  184    0  183
```