Computing folding pathways between RNA secondary structures |
| |
Authors: | Ivan Dotu William A Lorenz Pascal Van Hentenryck Peter Clote |
| |
Institution: | 1.Department of Computer Science, Brown University, PO Box 1910 Providence, RI 02912, USA and 2.Department of Biology, Boston College, Chestnut Hill, MA 02467, USA |
| |
Abstract: | Given an RNA sequence and two designated secondary structures A, B, we describe a new algorithm that computes a nearly optimal folding pathway from A to B. The algorithm, RNAtabupath, employs a tabu semi-greedy heuristic, known to be an effective search strategy in combinatorial optimization. Folding pathways, sometimes called routes or trajectories, are computed by RNAtabupath in a fraction of the time required by the barriers program of Vienna RNA Package. We benchmark RNAtabupath with other algorithms to compute low energy folding pathways between experimentally known structures of several conformational switches. The RNApathfinder web server, source code for algorithms to compute and analyze pathways and supplementary data are available at http://bioinformatics.bc.edu/clotelab/RNApathfinder. |
| |
Keywords: | |
|
|