Dynamic Programming on Secondary Structures

Dynamic Programming on RNA structures, among which the most successful has been the McCaskill Algorithm, forms the basis of modern RNA secondary structure prediction.

Let be the MFE structure for . For any pair , let be the corresponding secondary structure for . If is minimal then the corresponding must also be minimal for the subsequence between and . Thus the problem of finding the minimal MFE structure can be decomposed into determining the optimal structure for each subsequence of the sequence.

Let be the minimal possible value of (a secondary structure where and are paired). Note that it follows from energy summation that

where denotes the -cycle of bases closed by and is exactly the number of tuple of base pairs accessible from with the initial condition that and for any base pairs forbidden by secondary structure rules.

Let be the minimal possible energy value of all substructures of the sequence between and . Unlike , and are not necessarily paired. Then is given by

with the initial condition that . This follows as any secondary structure where and are not paired with each other can be divided into two regions and with not pairing between the two regions.

Then is the minimum free energy. Note that this is exactly the pseudocode used by ViennaRNA to identify the minimum energy structure.

However, in practice the recurrences for and respectively are impractical. Indeed, observe that the number of possible tuples between and (assuming ) is approximately equal to . Any algorithm would be expected to take exponential time. A practical implementation of this method is the McCaskill Algorithm.