Maximum expected accurate structural neighbors of an RNA secondary structure

Since RNA molecules regulate genes and control alternative splicing by allostery, that is, by switching between two distinct secondary structures, it is important to develop algorithms to predict RNA conformational switches. It has recently emerged that RNA secondary structure can be more accurately predicted by computing the maximum expected accurate (MEA) structure, rather than the minimum free energy (MFE) structure. The MEA structure S has maximum score 2 Σ _{(i, j)}ϵs P^{i, j} + Σ_i unpaired q_i, where first sum is taken over all base pairs (i, j) belonging to S, and the second sum is taken over all unpaired positions in S, and where p_{i, j} [resp. q_i] is the probability that i, j are paired [resp. i is unpaired] in the ensemble of low energy structures. Results: Given an arbitrary RNA secondary structure S₀, for an RNA nucleotide sequence a = a₁,. . . , a_n, we say that another secondary structure S of a is a k-neighbor of S₀, if the base pair distance between S₀ and S is k. Here we describe the algorithm RNAborMEA, which for an arbitrary initial structure So and for all values 0 ≤ k ≤ n, computes the secondary structure MEA(k), having maximum expected accuracy over all k-neighbos of S₀. We apply our algorithm to the class of purine riboswitches.