Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Natural Computing
Erschienen in: Natural Computing 1/2011

01.03.2011

NP-completeness of the energy barrier problem without pseudoknots and temporary arcs

verfasst von: Ján Maňuch, Chris Thachuk, Ladislav Stacho, Anne Condon

Erschienen in: Natural Computing | Ausgabe 1/2011

Einloggen

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

search-config
loading …

Abstract

Knowledge of energy barriers between pairs of secondary structures for a given DNA or RNA molecule is useful, both in understanding RNA function in biological settings and in design of programmed molecular systems. Current heuristics are not guaranteed to find the exact energy barrier, raising the question whether the energy barrier can be calculated efficiently. In this paper, we study the computational complexity of a simple formulation of the energy barrier problem, in which each base pair contributes an energy of −1 and only base pairs in the initial and final structures may be used on a folding pathway from initial to final structure. We show that this problem is NP-complete.
Vorheriger Artikel DNA chips for species identification and biological phylogenies
Nächster Artikel Strand algebras for DNA computing

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
Literatur
Chen SJ, Dill KA (2000) RNA folding energy landscapes. Proc Nat Acad Sci 97(2):646–651
Flamm C, Fontana W, Hofacker IL, Schuster P (2000) RNA folding at elementary step resolution. RNA 6:325–338
Flamm C, Hofacker IL, Stadler PF, Wolfinger MT (2002) Barrier trees of degenerate landscapes. Zeitschrift für Physikalische Chemie 216:155–174CrossRef
Garey MR, Johnson DS (1979) Computers and Intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co., New York, NY, USAMATH
Graham R, Knuth D, Patashnik O (1989) Concrete mathematics: a foundation for computer science. Addison-Wesley, Reading, MA, USAMATH
Kameda A, Yamamoto M, Uejima H, Hagiya M, Sakamoto K, Ohuchi A (2005) Hairpin-based state machine and conformational addressing: design and experiment. Nat Comput 4:103–126MathSciNetCrossRef
Hagiya M, Yaegashi S, Takahashi K (2006) Computing with hairpins and secondary structures of DNA. In: Chen J, Jonoska N, Rozenberg G (eds) Nanotechnology: science and computation, natural computing series. Springer, Heidelberg, pp 293–308
Maňuch J, Thachuk C, Stacho L, Condon A (2009) NP-completeness of the direct energy barrier problem without pseudoknots. In: Proceedings of DNA 15, Fayetteville, Arkansas, USA, Lecture Notes in Computer Science, vol 5877:106–115
Morgan SR, Higgs PG (1998) Barrier heights between ground states in a model of RNA secondary structure. J Phys A Math Gen 31:3153–3170MATHCrossRef
Russell R, Zhuang X, Babcock H, Millett I, Doniach S, Chu S, Herschlag D (2002) Exploring the folding landscape of a structured RNA. Proc Nat Acad Sci 99:155–160CrossRef
Seelig G, Soloveichik D, Zhang DY, Winfree E (2006) Enzyme-free nucleic acid logic circuits. Science 314:1585–1588CrossRef
Shcherbakova I, Mitra S, Laederach A, Brenowitz M (2008) Energy barriers, pathways, and dynamics during folding of large, multidomain RNAs. Curr Opin Chem Biol 12(6):655–666
Tang X, Thomas S, Tapia L, Giedroc DP, Amato NM (2008) Simulating RNA folding kinetics on approximated energy landscapes. J Mol Biol 381:1055–1067CrossRef
Thachuk C, Maňuch J, Rafiey A, Mathieson LA, Stacho L, Condon A (2010) An algorithm for the energy barrier problem without pseudoknots and temporary arcs. In: Proceedings of Pacific symposium on biocomputing (PSB), Honolulu, Hawaii, USA, pp 108–119
Treiber DK, Williamson JR (2001) Beyond kinetic traps in RNA folding. Curr Opin Struct Biol 11:309–314CrossRef
Uejima H, Hagiya M (2004a) Analyzing secondary structure transition paths of DNA/RNA molecules. In: DNA computing. Lecture notes in computer science, vol 2943. Springer, Heidelberg, pp 86–90
Uejima H, Hagiya M (2004b) Secondary structure design of multi-state DNA machines based on sequential structure transitions. In: Proceedings of DNA9, Madison, WI, USA, Lecture notes in computer science, vol 2943. Springer, Berlin, pp 74–85
van Batenburg FHD, Gultyaev AP, Pleij CWA, Ng J, Oliehoek J (2000) Pseudobase: a database with RNA pseudoknots. Nucl Acids Res 28(1):201–204CrossRef
Wolfinger MT (2001) The energy landscape of RNA folding. Master’s thesis, University Vienna
Yin P, Choi H, Calvert C, Pierce N (2008) Programming biomolecular self-assembly pathways. Nature 451:318–322CrossRef
Yurke B, Turberfield AJ, Mills AJJ, Simmel FC, Neumann JL (2000) A DNA-fuelled molecular machine made of DNA. Nature 406:605–608CrossRef
Metadaten
Titel
NP-completeness of the energy barrier problem without pseudoknots and temporary arcs
verfasst von
Ján Maňuch
Chris Thachuk
Ladislav Stacho
Anne Condon
Publikationsdatum
01.03.2011
Verlag
Springer Netherlands
Erschienen in
Natural Computing / Ausgabe 1/2011
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI
https://doi.org/10.1007/s11047-010-9239-4

Weitere Artikel der Ausgabe 1/2011

Natural Computing 1/2011 Zur Ausgabe

OriginalPaper

On aggregation in multiset-based self-assembly of graphs

OriginalPaper

Strand algebras for DNA computing

OriginalPaper

An immune-inspired approach to qualitative system identification of biological pathways

OriginalPaper

Grammar-based immune programming

OriginalPaper

Towards a neighborhood simplification of tile systems: From Moore to quasi-linear dependencies

OriginalPaper

Evolutionary and population dynamics of 3 parents differential evolution (3PDE) using self-adaptive tuning methodologies

Premium Partner

    Bildnachweise