Multi-objective optimization for RNA design with multiple target secondary structures

BMC Bioinformatics

Akito Taneda¹ 

[1] Graduate School of Science and Technology, Hirosaki University, 3 Bunkyo-cho, Hirosaki, Aomori, Japan

关键词: Pseudoknot;    Multi-objective genetic algorithm;    Artificial riboswitch;    RNA switch;   

Others  :  1229472
DOI  :  10.1186/s12859-015-0706-x

 received in 2014-11-23, accepted in 2015-08-17,  发布年份 2015

【 摘 要 】

Background

RNAs are attractive molecules as the biological parts for synthetic biology. In particular, the ability of conformational changes, which can be encoded in designer RNAs, enables us to create multistable molecular switches that function in biological circuits. Although various algorithms for designing such RNA switches have been proposed, the previous algorithms optimize the RNA sequences against the weighted sum of objective functions, where empirical weights among objective functions are used. In addition, an RNA design algorithm for multiple pseudoknot targets is currently not available.

Results

We developed a novel computational tool for automatically designing RNA sequences which fold into multiple target secondary structures. Our algorithm designs RNA sequences based on multi-objective genetic algorithm, by which we can explore the RNA sequences having good objective function values without empirical weight parameters among the objective functions. Our algorithm has great flexibility by virtue of this weight-free nature. We benchmarked our multi-target RNA design algorithm with the datasets of two, three, and four target structures and found that our algorithm shows better or comparable design performances compared with the previous algorithms, RNAdesign and Frnakenstein. In addition to the benchmarks with pseudoknot-free datasets, we benchmarked MODENA with two-target pseudoknot datasets and found that MODENA can design the RNAs which have the target pseudoknotted secondary structures whose free energies are close to the lowest free energy. Moreover, we applied our algorithm to a ribozyme-based ON-switch which takes a ribozyme-inactive secondary structure when the theophylline aptamer structure is assumed.

Conclusions

Currently, MODENA is the only RNA design software which can be applied to multiple pseudoknot targets. Successful design results for the multiple targets and an RNA device indicate usefulness of our multi-objective RNA design algorithm.

【 授权许可】

   
2015 Taneda.

【 图 表 】

Fig. 1.

Fig. 2.

Fig. 3.

Fig. 4.

Fig. 5.

Fig. 6.

Fig. 7.

Fig. 8.

【 参考文献 】

• [1]Tang J, Breaker RR. Rational design of allosteric ribozymes. Chem Biol. 1997; 4:453-9.
• [2]Win MN, Liang JC, Smolke CD. Frameworks for programming biological function through RNA parts and devices. Chem Biol. 2009; 16:298-310.
• [3]Rodrigo G, Landrain TE, Jaramillo A. De novo automated design of small RNA circuits for engineering synthetic riboregulation in living cells. Proc Natl Acad Sci U S A. 2012; 109:15271-6.
• [4]Wachsmuth M, Findeiß S, Weissheimer N, Stadler PF, Mörl M. De novo design of a synthetic riboswitch that regulates transcription termination. Nucleic Acids Res. 2012; 41:2541-551.
• [5]Perreault J, Weinberg Z, Roth A, Popescu O, Chartrand P, Ferbeyre G et al.. Identification of hammerhead ribozymes in all domains of life reveals novel structural variations. PLoS Comput Biol. 2011; 7:1002031.
• [6]Chushak Y, Stone MO. In silico selection of RNA aptamers. Nucleic Acids Res. 2009; 37:87.
• [7]Kortmann J, Narberhaus F. Bacterial RNA thermometers: molecular zippers and switches. Nat Rev Microbiol. 2012; 10:255-65.
• [8]Lowe TM, Eddy SR. A computational screen for methylation guide snoRNAs in yeast. Science. 1999; 283:1168-71.
• [9]Zappulla DC, Cech TR. RNA as a flexible scaffold for proteins: yeast telomerase and beyond. Cold Spring Harb Symp Quant Biol. 2006; 71:217-24.
• [10]Schultes Ea. One sequence, two ribozymes: Implications for the emergence of new ribozyme folds. Science (80-.). 2000; 289:448-52.
• [11]Penchovsky R, Breaker RR. Computational design and experimental validation of oligonucleotide-sensing allosteric ribozymes. Nat Biotechnol. 2005; 23:1424-33.
• [12]Choi HMT, Chang JY, Trinh La, Padilla JE, Fraser SE, Pierce Na et al.. Programmable in situ amplification for multiplexed imaging of mRNA expression. Nat Biotechnol. 2010; 28:1208-12.
• [13]Hochrein LM, Schwarzkopf M, Shahgholi M, Yin P, Pierce NA. Conditional Dicer substrate formation via shape and sequence transduction with small conditional RNAs. J Am Chem Soc. 2013; 135:17322-30.
• [14]Dotu I, Garcia-Martin JA, Slinger BL, Mechery V, Meyer MM, Clote P et al.. Complete RNA inverse folding: computational design of functional hammerhead ribozymes. Nucleic Acids Res. 2014; 42:11752-62.
• [15]Liang JC, Smolke CD. Rational design and tuning of ribozyme-based devices. Methods Mol Biol. 2012; 848:439-54.
• [16]Hofacker IL, Fontana W, Stadler PF, Bonhoeffer LS, Tacker M, Schuster P et al.. Fast folding and comparison of RNA secondary structures. Monatshefte für Chemie - Chem Mon Chemie Chem Mon. 1994; 125:167-88.
• [17]Andronescu M, Fejes AP, Hutter F, Hoos HH, Condon A. A new algorithm for RNA secondary structure design. J Mol Biol. 2004; 336:607-24.
• [18]Busch A, Backofen R. INFO-RNA–a fast approach to inverse RNA folding. Bioinformatics. 2006; 22:1823-31.
• [19]Zadeh JN, Wolfe BR, Pierce NA. Nucleic acid sequence design via efficient ensemble defect optimization. J Comput Chem. 2011; 32:439-52.
• [20]Garcia-Martin JA, Clote P, Dotu I. RNAiFOLD: a constraint programming algorithm for RNA inverse folding and molecular design. J Bioinform Comput Biol. 2013; 11:1350001.
• [21]Esmaili-Taheri A, Ganjtabesh M, Mohammad-Noori M. Evolutionary solution for the RNA design problem. Bioinformatics. 2014; 30:1250-8.
• [22]Reinharz V, Ponty Y, Waldispühl J. A weighted sampling algorithm for the design of RNA sequences with targeted secondary structure and nucleotide distribution. Bioinformatics. 2013; 29:308-15.
• [23]Matthies MC, Bienert S, Torda AE. Dynamics in sequence space for RNA secondary structure design. J Chem Theory Comput. 2012; 8:3663-670.
• [24]Flamm C, Hofacker IL, Maurer-Stroh S, Stadler PF, Zehl M. Design of multistable RNA molecules. RNA. 2001; 7:254-65.
• [25]Lyngsø RB, Anderson JWJ, Sizikova E, Badugu A, Hyland T, Hein J. Frnakenstein: multiple target inverse RNA folding. BMC Bioinforma. 2012; 13:260. BioMed Central Full Text
• [26]Höner Zu Siederdissen C, Hammer S, Abfalter I, Hofacker IL, Flamm C, Stadler PF. Computational design of RNAs with complex energy landscapes. Biopolymers. 2013; 99:1124-36.
• [27]Deb K. Multi-objective optimization using evolutionary algorithms. John Wiley and Sons, Chichester; 2001.
• [28]Taneda A. MODENA : a multi-objective RNA inverse folding. Adv Appl Bioinforma Chem. 2011; 4:1-12.
• [29]Deb K, Pratap a, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput. 2002; 6:182-97.
• [30]Handl J, Kell DB, Knowles J. Multiobjective optimization in bioinformatics and computational biology. IEEE/ACM Trans Comput Biol Bioinform. 2007; 4:279-92.
• [31]Taneda A. Multi-objective pairwise RNA sequence alignment. Bioinformatics. 2010; 26:2383-390.
• [32]Taneda A. Multi-objective genetic algorithm for pseudoknotted RNA sequence design. Front Genet. 2012; 3:36.
• [33]Biebricher CK, Luce R. In vitro recombination and terminal elongation of RNA by Q beta replicase. EMBO J. 1992; 11:5129-135.
• [34]Dotu I, Lorenz Wa, Van Hentenryck P, Clote P. Computing folding pathways between RNA secondary structures. Nucleic Acids Res. 2010; 38:1711-22.
• [35]Zadeh JN, Steenberg CD, Bois JS, Wolfe BR, Pierce MB, Khan AR et al.. NUPACK: Analysis and design of nucleic acid systems. J Comput Chem. 2011; 32:170-3.
• [36]van Batenburg FH, Gultyaev AP, Pleij CW, Ng J, Oliehoek J. PseudoBase: a database with RNA pseudoknots. Nucleic Acids Res. 2000; 28:201-4.
• [37]Giegerich R, Voss B, Rehmsmeier M. Abstract shapes of RNA. Nucleic Acids Res. 2004; 32:4843-851.
• [38]Lee J, Kladwang W, Lee M, Cantu D, Azizyan M, Kim H et al.. RNA design rules from a massive open laboratory. Proc Natl Acad Sci U S A. 2014; 111:2122-127.
• [39]Win MN, Smolke CD. A modular and extensible RNA-based gene-regulatory platform for engineering cellular function. Proc Natl Acad Sci U S A. 2007; 104:14283-8.
• [40]Darty K, Denise A, Ponty Y. VARNA: Interactive drawing and editing of the RNA secondary structure. Bioinformatics. 2009; 25:1974-5.
• [41]Lorenz R, Bernhart SH, Höner Zu Siederdissen C, Tafer H, Flamm C, Stadler PF et al.. ViennaRNA package 2.0. Algorithms Mol Biol. 2011; 6:26. BioMed Central Full Text
• [42]Reuter JS, Mathews DH. RNAstructure: software for RNA secondary structure prediction and analysis. BMC Bioinforma. 2010; 11:129. BioMed Central Full Text
• [43]Hamada M, Kiryu H, Sato K, Mituyama T, Asai K. Prediction of RNA secondary structure using generalized centroid estimators. Bioinformatics. 2009; 25:465-73.
• [44]Asai K, Kiryu H, Hamada M, Tabei Y, Sato K, Matsui H et al.. Software.ncrna.org: web servers for analyses of RNA sequences. Nucleic Acids Res. 2008; 36:75-8.
• [45]Sato K, Kato Y, Hamada M, Akutsu T, Asai K. IPknot: fast and accurate prediction of RNA secondary structures with pseudoknots using integer programming. Bioinformatics. 2011; 27:85-93.
• [46]Markham NR, Zuker M. UNAFold: software for nucleic acid folding and hybridization. Methods Mol Biol. 2008; 453:3-31.
• [47]Reeder J, Giegerich R. Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinforma. 2004; 5:104. BioMed Central Full Text
• [48]Andronescu M, Aguirre-Hernández R, Condon A, Hoos HH. RNAsoft: A suite of RNA secondary structure prediction and design software tools. Nucleic Acids Res. 2003; 31:3416-422.
• [49]Voss B, Meyer C, Giegerich R. Evaluating the predictability of conformational switching in RNA. Bioinformatics. 2004; 20:1573-82.
• [50]Wakeman CA, Winkler WC, Dann CE. Structural features of metabolite-sensing riboswitches. Trends Biochem Sci. 2007; 32:415-24.
• [51]Mandal M, Boese B, Barrick JE, Winkler WC, Breaker RR. Riboswitches control fundamental biochemical pathways in bacillus subtilis and other bacteria. Cell. 2003; 113:577-86.