FoldRNA

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.

Program is provided with viewer.

Output example:


Program RNAfold (Softberry Inc.) version 3.0
Sequence_name: "At-MIR156a_Stem" Length: 183

::: structure # 1 :::
Energy: -82.9 kkal/mol 75% 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
)))

GCG format:
    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  171   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  155   27
   28 a      27   29    0   28
   29 c      28   30    0   29
   30 g      29   31    0   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  115   46
   47 a      46   48  114   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    0   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    0   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    0  113
  114 u     113  115   47  114
  115 u     114  116   46  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    0  153
  154 g     153  155    0  154
  155 u     154  156   27  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    0  170
  171 c     170  172   13  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    1  183


::: structure # 2 :::
Energy: -82.3 kkal/mol 65% 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
...

GCG format:
    1 g       0    2    0    1
    2 u       1    3    0    2
    3 g       2    4    0    3
    4 a       3    5   15    4
    5 a       4    6   14    5
    6 u       5    7   13    6
    7 g       6    8    0    7
    8 a       7    9    0    8
    9 a       8   10    0    9
   10 a       9   11    0   10
   11 g      10   12    0   11
   12 a      11   13    0   12
   13 g      12   14    6   13
   14 u      13   15    5   14
   15 u      14   16    4   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  155   27
   28 a      27   29    0   28
   29 c      28   30    0   29
   30 g      29   31    0   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
...