nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Combinatorial RNA Design: Designability and Structure-Approximating Algorithm

verfasst von : Jozef Haleš, Ján Maňuch, Yann Ponty, Ladislav Stacho

Erschienen in: Combinatorial Pattern Matching

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this work, we consider the Combinatorial RNA Design problem, a minimal instance of the RNA design problem in which one must return an RNA sequence that admits a given secondary structure as its unique base pair maximizing structure.

First, we fully characterize designable structures using restricted alphabets. Then, under a classic four-letter alphabet, we provide a complete characterization for designable structures without unpaired bases. When unpaired bases are allowed, we characterize extensive classes of (non-)designable structures, and prove the closure of the set of designable structures under the stutter operation. Membership of a given structure to any of the classes can be tested in \(\varTheta (n)\) time, including the generation of a solution sequence for positive instances. Finally, we consider a structure-approximating version of the problem that allows to extend bands (stems). We provide a \(\varTheta (n)\) algorithm which, given a structure \(S\) avoiding two trivially non-designable motifs, transforms \(S\) into a designable structure by adding at most one base-pair to each of its stems, and returns a solution sequence.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding

Nächstes Kapitel Dictionary Matching with Uneven Gaps

Aguirre-Hernández, R., Hoos, H.H., Condon, A.: Computational RNA secondary structure design: empirical complexity and improved methods. BMC Bioinform. 8, 34 (2007)CrossRef

Avihoo, A., Churkin, A., Barash, D.: RNAexinv: an extended inverse RNA folding from shape and physical attributes to sequences. BMC Bioinform. 12(1), 319 (2011)CrossRef

Busch, A., Backofen, R.: INFO-RNA–a fast approach to inverse RNA folding. Bioinformatics 22(15), 1823–1831 (2006)CrossRef

Dai, D.C., Tsang, H.H., Wiese, K.C.: RNADesign: local search for RNA secondary structure design. In: IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology (CIBCB) (2009)

Esmaili-Taheri, A., Ganjtabesh, M., Mohammad-Noori, M.: Evolutionary solution for the RNA design problem. Bioinformatics 30(9), 1250–1258 (2014)CrossRef

Frid, Y., Gusfield, D.: A simple, practical and complete \(o(n^3/\log n)\)-time algorithm for RNA folding using the Four-Russians speedup. Algorithms Mol. Biol. 5, 13 (2010)CrossRef

Garcia-Martin, J.A., Clote, P., Dotu, I.: RNAiFOLD: a constraint programming algorithm for RNA inverse folding and molecular design. J. Bioinform. Comput. Biol. 11(2), 1350001 (2013)CrossRef

Griffiths-Jones, S., Bateman, A., Marshall, M., Khanna, A., Eddy, S.R.: RFAM: an RNA family database. Nucleic Acids Res. 31(1), 439–441 (2003)CrossRef

Höner Zu Siederdissen, C., Hammer, S., Abfalter, I., Hofacker, I.L., Flamm, C., Stadler, P.F.: Computational design of RNAs with complex energy landscapes. Biopolymers 99(12), 1124–1136 (2013)

10.

Hofacker, I.L., Fontana, W., Stadler, P., Bonhoeffer, L., Tacker, M., Schuster, P.: Fast folding and comparison of RNA secondary structures. Monatshefte für Chemie/Chem. Monthly 125(2), 167–188 (1994)CrossRef

11.

Levin, A., Lis, M., Ponty, Y., O’Donnell, C.W., Devadas, S., Berger, B., Waldispühl, J.: A global sampling approach to designing and reengineering RNA secondary structures. Nucleic Acids Res. 40(20), 10041–10052 (2012)CrossRef

12.

Lyngsø, R.B., Anderson, J.W., Sizikova, E., Badugu, A., Hyland, T., Hein, J.: FRNAkenstein: multiple target inverse RNA folding. BMC Bioinform. 13, 260 (2012)CrossRef

13.

Mathews, D.H., Sabina, J., Zuker, M., Turner, D.H.: Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure. J. Mol. Biol. 288(5), 911–940 (1999)CrossRef

14.

Nussinov, R., Jacobson, A.: Fast algorithm for predicting the secondary structure of single-stranded RNA. Proc. Natl. Acad. Sci. USA 77, 6903–6913 (1980)CrossRef

15.

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 29(13), i308–i315 (2013)CrossRef

16.

Rodrigo, G., Landrain, T.E., Majer, E., Daròs, J.-A., Jaramillo, A.: Full design automation of multi-state RNA devices to program gene expression using energy-based optimization. PLoS Comput. Biol. 9(8), e1003172 (2013)CrossRef

17.

Schnall-Levin, M., Chindelevitch, L., Berger, B.: Inverting the Viterbi algorithm: an abstract framework for structure design. In: Machine Learning, Proceedings of the Twenty-Fifth International Conference (ICML 2008), Helsinki, Finland, June 5–9, 2008, pp. 904–911 (2008)

18.

Takahashi, M.K., Lucks, J.B.: A modular strategy for engineering orthogonal chimeric RNA transcription regulators. Nucleic Acids Res. 41(15), 7577–7588 (2013)CrossRef

19.

Taneda, A.: MODENA: a multi-objective RNA inverse folding. Adv. Appl. Bioinform. Chem. 4, 1–12 (2011)

20.

Turner, D.H., Mathews, D.H.: NNDB: the nearest neighbor parameter database for predicting stability of nucleic acid secondary structure. Nucleic Acids Res. 38, D280–D282 (2010). (Database issue)CrossRef

21.

Wu, S.Y., Lopez-Berestein, G., Calin, G.A., Sood, A.K.: RNAi therapies: drugging the undruggable. Sci. Transl. Med. 6(240), 240ps7 (2014)CrossRef

22.

Zadeh, J.N., Wolfe, B.R., Pierce, N.A.: Nucleic acid sequence design via efficient ensemble defect optimization. J. Comput. Chem. 32(3), 439–452 (2011)CrossRef

23.

Zhou, Y., Ponty, Y., Vialette, S., Waldispuhl, J., Zhang, Y., Denise, A.: Flexible RNA design under structure and sequence constraints using formal languages. In: Proceedings of the International Conference on Bioinformatics, Computational Biology and Biomedical Informatics, BCB 2013, pp. 229–238. ACM (2013)

24.

Zuker, M., Stiegler, P.: Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Res. 9, 133–148 (1981)CrossRef

Titel: Combinatorial RNA Design: Designability and Structure-Approximating Algorithm
verfasst von: Jozef Haleš
Ján Maňuch
Yann Ponty
Ladislav Stacho
Verlag: Springer International Publishing
Buch: Combinatorial Pattern Matching
Print ISBN: 978-3-319-19928-3

Electronic ISBN: 978-3-319-19929-0

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-19929-0_20

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"