A New Algorithm for RNA Secondary Structure Design

The function of many RNAs depends crucially on their structure. Therefore, the design of RNA molecules with specific structural properties has many potential applications, e.g. in the context of investigating the function of biological RNAs, of creating new ribozymes, or of designing artificial RNA...

Full description

Saved in:
Bibliographic Details
Published in:Journal of molecular biology 2004-02, Vol.336 (3), p.607-624
Main Authors: Andronescu, Mirela, Fejes, Anthony P., Hutter, Frank, Hoos, Holger H., Condon, Anne
Format: Article
Language:English
Subjects:
Algorithms
Base Sequence
Computer Simulation
Databases, Genetic
Models, Genetic
Molecular Sequence Data
Nucleic Acid Conformation
RNA - chemistry
RNA design
RNA inverse folding
RNA structure
stochastic local search
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The function of many RNAs depends crucially on their structure. Therefore, the design of RNA molecules with specific structural properties has many potential applications, e.g. in the context of investigating the function of biological RNAs, of creating new ribozymes, or of designing artificial RNA nanostructures. Here, we present a new algorithm for solving the following RNA secondary structure design problem: given a secondary structure, find an RNA sequence (if any) that is predicted to fold to that structure. Unlike the (pseudoknot-free) secondary structure prediction problem, this problem appears to be hard computationally. Our new algorithm, “RNA Secondary Structure Designer (RNA-SSD)”, is based on stochastic local search, a prominent general approach for solving hard combinatorial problems. A thorough empirical evaluation on computationally predicted structures of biological sequences and artificially generated RNA structures as well as on empirically modelled structures from the biological literature shows that RNA-SSD substantially outperforms the best known algorithm for this problem, RNAinverse from the Vienna RNA Package. In particular, the new algorithm is able to solve structures, consistently, for which RNAinverse is unable to find solutions. The RNA-SSD software is publically available under the name of RNA Designer at the RNASoft website ( www.rnasoft.ca).
ISSN:0022-2836
1089-8638
DOI:10.1016/j.jmb.2003.12.041