Top

Natural Computing

Published in:

01-03-2011

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

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

Published in: Natural Computing | Issue 1/2011

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

search-config

AI-assisted search

Off

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.

previous article DNA chips for species identification and biological phylogenies

next article Strand algebras for DNA computing

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

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

Simmel FC, Dittmer WU (2005) DNA nanodevices. Small 1:284–299CrossRef

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

Title: NP-completeness of the energy barrier problem without pseudoknots and temporary arcs
Authors: Ján Maňuch
Chris Thachuk
Ladislav Stacho
Anne Condon
Publication date: 01-03-2011
Publisher: Springer Netherlands
Published in: Natural Computing / Issue 1/2011
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-010-9239-4

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 1/2011

Grammar-based immune programming

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

Computing transparently: the independent sets in a graph

A hybrid approach for learning concept hierarchy from Malay text using artificial immune network

A simple mass-action model for the eukaryotic heat shock response and its mathematical validation

Priming: making the reaction to intrusion or fault predictable

Premium Partner