RNA thermometers (RNATs), also known as thermosensors, are cis-regulatory elements that change secondary structure upon temperature shift. Examples include (i) repression of heat shock gene expression (ROSE) elements (Nocker et al., 2001), which control the expression of small heat shock genes, such as hspA in Bradyrhizobium japonicum and ibpA in Escherichia coli; (ii) FourU elements (Waldminghaus et al., 2007b), such as the virulence factor LcrF in Yersinia pestis; and (iii) Hsp17 thermosensor (Kortmann et al., 2011; Torok et al., 2001), which controls membrane integrity of the cyanobacterium Synechocystis sp. PCC6803 under stress conditions, critical for photosynthetic activity. Additional examples are described in Kortmann and Narberhaus (2012). ROSE elements and FourU elements operate as temperature-sensitive, reversible zippers, while the Listeria monocytogenes prfA thermosensor (Johansson et al., 2002), phage λ cIII thermoswitch (Altuvia et al., 1989) and E.coli CspA cold shock thermometer (Bae et al., 2000) operate in a switch-like fashion. Here, the helix of a zipper melts gradually with increasing temperature, returning to the original structure when temperature is reduced, while a switch consists of two mutually exclusive structures determined by temperature.#R##N##R##N#Several bioinformatics search methods exist to identify and predict candidate RNA thermometers. In Waldminghaus et al. (2007a) the database RNA-SURIBA (Structures of Untranslated Regions In BActeria) was created; using regular expressions, particular structural motifs were detected in the minimum free energy (MFE) structure, as determined by mfold (Zuker, 2003). In contrast, the RNAtips web server (Chursov et al., 2013) and the RNAthermsw (Churkin et al., 2014) web server both rely on base pairing probabilities computed at different temperatures using RNAfold from the Vienna RNA Package (Lorenz et al., 2011).#R##N##R##N#For some time now, RNA thermosensors have been recognized as an attractive target for rational design (Waldminghaus et al., 2008; Wieland and Hartig, 2007). Indeed, within the broader context of synthetic biology, rationally designed thermometers could be used as a thermogenetic tool to control expression by temperature regulation (i.e. on-demand protein translation), or even as a multifunctional nanoscale devices to measure temperature in the context of hyperthermic treatment of cancer cells, imaging or drug delivery (Lee and Kotov, 2007).#R##N##R##N#In Neupert et al. (2008), synthetic (zipper) thermosensors were manually designed to sequester the Shine-Dalgarno sequence AAGGAG within a single stem-loop structure containing 4–9 base pairs, several of which contained 1–2 bulges of size 1. In Waldminghaus et al. (2008), synthetic (switch) thermosensors were computationally designed to switch between a single stem-loop structure that sequesters the Shine-Dalgarno sequence GGAGG, and two shorter stem-loop structures where the Shine-Dalgarno sequence is found in the apical loop of the second stem-loop. In particular, the 2-temperature inverse folding (adaptive walk) program SwitchDesign (Flamm et al., 2001) was used to obtain 300 candidate sequences; only two candidate sequences survived after the application of several computational filters including the computation of melting curves with RNAheat (Lorenz et al., 2011). Since neither of these sequence displayed any temperature-dependent control of a reporter gene (bgaB) fusion, the top candidate sequence was used as a template in two rounds of error-prone mutagenesis followed by selection, resulting in a successful thermosensor—see Figure 5 of Waldminghaus et al. (2008). In Ogawa (2011), a non-temperature-dependent riboswitch was manually designed, which promotes cap-independent translation in wheat germ cell lysate only upon binding of the ligand theophylline. In Wachsmuth et al. (2013), a synthetic theophylline riboswitch was designed by a computational pipeline including inverse folding and experimentally shown to perform transcriptional regulation in Escherichia coli Top10 cells. In Saragliadis et al. (2013), a thermozyme was created by fusing a Salmonella RNA thermometer (RNAT) to a hammerhead ribozyme, followed by in vivo screening—thus showing that naturally occurring hammerheads and RNATs appear to be modules that can be combined. In Hoynes-O’Connor et al. (2015) small, heat-repressible RNA thermosensors (zippers) were manually designed in E.coli, which at low temperature sequester a cleavage site for RNaseE, and at high temperatures unfold to allow mRNA degradation.#R##N##R##N#Despite these impressive results, Kortmann and Narberhaus (2012) state that: ‘RNATs have little, if any sequence conservation and are difficult to predict from genome sequences. … Therefore, the bioinformatic prediction and rational design of functional RNATs has remained a major challenge.’#R##N##R##N#In this article, we introduce the software RNAiFold2T, capable of solving the inverse folding problem for two or more temperatures, i.e. generating one or more RNA sequences whose MFE secondary structures at temperatures T1 and T2 (resp. T1,…,Tm) are user-specified target structures S1 and S2 (resp. S1,…,Sm), or which reports that no such solution exists. RNAiFold2T is unique in that it implements two different algorithms—Constraint Programming (CP) and Large Neighborhood Search (LNS). CP is an exact, non-heuristic method that uses an exhaustive yet efficient branch-and-prune process, and is the only currently available software capable of generating all solutions or determining that no solution exists (since there are possibly exponentially many solutions, a complete solution is feasible only for structures of modest size). LNS uses a local search heuristic, complemented with local calls of CP to explore solutions of substructures of the target structures. We use RNAiFold2T to rationally design two thermo-IRES elements, whose normalized cap-independent translation efficiency is approximately 50% greater at 42°C than 30°C, when tested in reticulocyte lysates. We then benchmark RNAiFold2T with the only two other programs that solve the 2-temperature inverse folding problem: the adaptive walk SwitchDesign (SD) (Flamm et al., 2001) and the genetic algorithm Frnakenstein (FRNA) (Lyngso et al., 2012). RNAiFold2T CP generates two orders of magnitude more solutions than either, when all programs are run for 24 h, while the number of distinct problem instances that can be solved by RNAiFold2T LNS within 30 (resp. 60) min for short (resp. long) target structures is roughly comparable for each program. Finally, by analyzing existent RNATs found in the Rfam 12.0 database (Nawrocki et al., 2014), we determine that naturally occurring RNATs appear not to be optimized for the cost function [Equation (7) of Flamm et al. (2001)], and that both SD and FRNA appear to generate solutions whose cost function value is substantially lower than that of naturally occurring RNATs, in contrast to solutions returned by RNAiFold2T.
['Juan Antonio Garcia-Martin', 'Ivan Dotu', 'Javier Fernandez-Chamorro', 'Gloria Lozano', 'Jorge Ramajo', 'Encarnación Martínez-Salas', 'Peter Clote']
RNAiFold2T: Constraint Programming design of thermo-IRES switches