Abstract:
We study the problem posed by Morgan and Higgs of calculating pseudoknot-free folding pathways with minimum energy barrier between pair (A, B) of RNA secondary structures of the same sequence. We use a simple energy model in which each base pair contributes −1. In a direct folding pathway, intermediate structures contain only base pairs in A and B and are of length |A| + |B|. We show that problem is NP-complete and develop an algorithm that solves this problem exactly, using techniques for deconstructing bipartite graphs. The algorithm requires exponential time in the worst case but performs quite well empirically on pairs of structures that are hundreds of nucleotides long. We also show that for the simple energy model, repeatedly adding or removing a base pair from A U B along a pathway is not useful in minimizing the energy barrier. Two consequences of this result are that (i) the problem of determining the min-barrier pseudoknot-free folding pathway from the space of direct pathways with repeats is NP-hard and (ii) our algorithm finds the min-barrier pathway not only from the space of direct folding pathways but in fact from the space of direct pathways with repeats.

This is a joint work with Chris Thachuk, Arash Rafiey, Leigh-Anne Mathieson, Ladislav Stacho and Anne Condon.