Figure 11

Pseudocode for RNAborMEA algorithm. Given RNA sequence s = s₁, .. ., s _n of length n, initial secondary structure S₀ of s, RNAborMEA computes for all values of 0 ≤ k ≤ n that structure S with base pair distance k from S₀, which maximizes the value $M\left(i,j,k\right)=\sum _{\left(i,j\right)\in S}2\alpha p_{i,j}+\sum _{i\text{unpaired in }s}\beta q_i$. The pseudocode actually computes only values M(i, j, k) for all i, j, k; the MEA structures are obtained by backtracing. This algorithm clearly runs in O(n³) time with O(n³) space.