title: Computing folding pathways between RNA secondary structures.
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.
authors.affiliation: Department of Computer Science, Brown University, PO Box 1910 Providence, RI 02912, USA.
authors.forename: Ivan
authors.initials: I
authors.lastname: Dotu
authors.forename: William A
authors.initials: WA
authors.lastname: Lorenz
authors.forename: Pascal
authors.initials: P
authors.lastname: Van Hentenryck
authors.forename: Peter
authors.initials: P
authors.lastname: Clote
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry*; D017423:Sequence Analysis, RNA; D012984:Software
chemical_list: D012313:RNA