Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Combinatorial RNA Design: Designability and Structure-Approximating Algorithm

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

Published in: Combinatorial Pattern Matching

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding
next chapter Dictionary Matching with Uneven Gaps
Literature
1.
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
2.
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
3.
Busch, A., Backofen, R.: INFO-RNA–a fast approach to inverse RNA folding. Bioinformatics 22(15), 1823–1831 (2006)CrossRef
4.
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)
5.
Esmaili-Taheri, A., Ganjtabesh, M., Mohammad-Noori, M.: Evolutionary solution for the RNA design problem. Bioinformatics 30(9), 1250–1258 (2014)CrossRef
6.
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
7.
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
8.
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
9.
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
Metadata
Title
Combinatorial RNA Design: Designability and Structure-Approximating Algorithm
Authors
Jozef Haleš
Ján Maňuch
Yann Ponty
Ladislav Stacho
Copyright Year
2015
Book
Combinatorial Pattern Matching

Print ISBN: 978-3-319-19928-3

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

Copyright Year: 2015

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

Premium Partner

    Image Credits