| Home | Organizers | Proceedings Editors | Proceedings Contributors | Search | | ||
|
|
|||
|
||||
|
|
||||
| Title: | AN ALGORITHM FOR THE ENERGY BARRIER PROBLEM WITHOUT PSEUDOKNOTS AND TEMPORARY ARCS | |
| DOI No: | 10.1142/9789814295291_0013 | |
| Source: | BIOCOMPUTING 2010 (pp 108-119) | |
| Author(s): | CHRIS THACHUK
Department of Computer Science, University of British Columbia, Canada JÁN MAŇUCH School of Computing Science, Simon Fraser University, Canada ARASH RAFIEY School of Computing Science, Simon Fraser University, Canada LEIGH-ANNE MATHIESON Department of Computer Science, University of British Columbia, Canada LADISLAV STACHO Department of Mathematics, Simon Fraser University, Canada ANNE CONDON Department of Computer Science, University of British Columbia, Canada |
|
| Abstract: | We make two new contributions to the problem of calculating pseudoknot-free folding pathways with minimum energy barrier between pairs ( ,  ) of RNA secondary structures. Our first contribution pertains to a problem posed by Morgan and Higgs: find a min-barrier direct folding pathway for a simple energy model in which each base pair contributes -1. In a direct folding pathway, intermediate structures contain only base pairs in  and  and are of length  (the size of the symmetric difference of the two structures). We show how to solve this problem exactly, using techniques for deconstructing bipartite graphs. The problem is NP-hard and so our algorithm requires exponential time in the worst case but performs quite well empirically on pairs of structures that are hundreds of nucleotides long. Our second contribution shows that for the simple energy model, repeatedly adding or removing a base pair from  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 new 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. |
|
| Keywords: | RNA secondary structure; RNA folding pathways; energy barrier problem |
|
| Full Text: | View full text in PDF format (729KB) | |
| TOC: | Back to Table of Contents | |
|
||