title: RNAiFOLD: a constraint programming algorithm for RNA inverse folding and molecular design.
abstract: Synthetic biology is a rapidly emerging discipline with long-term ramifications that range from single-molecule detection within cells to the creation of synthetic genomes and novel life forms. Truly phenomenal results have been obtained by pioneering groups--for instance, the combinatorial synthesis of genetic networks, genome synthesis using BioBricks, and hybridization chain reaction (HCR), in which stable DNA monomers assemble only upon exposure to a target DNA fragment, biomolecular self-assembly pathways, etc. Such work strongly suggests that nanotechnology and synthetic biology together seem poised to constitute the most transformative development of the 21st century. In this paper, we present a Constraint Programming (CP) approach to solve the RNA inverse folding problem. Given a target RNA secondary structure, we determine an RNA sequence which folds into the target structure; i.e. whose minimum free energy structure is the target structure. Our approach represents a step forward in RNA design--we produce the first complete RNA inverse folding approach which allows for the specification of a wide range of design constraints. We also introduce a Large Neighborhood Search approach which allows us to tackle larger instances at the cost of losing completeness, while retaining the advantages of meeting design constraints (motif, GC-content, etc.). Results demonstrate that our software, RNAiFold, performs as well or better than all state-of-the-art approaches; nevertheless, our approach is unique in terms of completeness, flexibility, and the support of various design constraints. The algorithms presented in this paper are publicly available via the interactive webserver http://bioinformatics.bc.edu/clotelab/RNAiFold; additionally, the source code can be downloaded from that site.
authors.affiliation: CNB-CSIC, Darwin 3, Campus Cantoblanco, 28049 Madrid, Spain. ja.garcia@cnb.csic.es
authors.forename: Juan Antonio
authors.initials: JA
authors.lastname: Garcia-Martin
authors.forename: Peter
authors.initials: P
authors.lastname: Clote
authors.forename: Ivan
authors.initials: I
authors.lastname: Dotu
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D003198:Computer Simulation; D019143:Evolution, Molecular; D008958:Models, Molecular; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry* / Q000235:genetics; D059370:RNA Folding; D058928:Riboswitch; D012984:Software; D058615:Synthetic Biology; D013816:Thermodynamics
chemical_list: D058928:Riboswitch; D012313:RNA