caa a22 4500 445842687 CHVBK 20180317145349.0 cr unu---uuuuu 170323e20110301xx s 000 0 eng 10.1007/s11047-010-9239-4 doi (NATIONALLICENCE)springer-10.1007/s11047-010-9239-4 NP-completeness of the energy barrier problem without pseudoknots and temporary arcs [Elektronische Daten] [Ján Maňuch, Chris Thachuk, Ladislav Stacho, Anne Condon] 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. Springer Science+Business Media B.V., 2010 Nucleic acids nationallicence Folding pathways nationallicence Energy barrier nationallicence NP-completeness nationallicence Maňuch Ján Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada aut Thachuk Chris Department of Computer Science, University of British Columbia, Vancouver, BC, Canada aut Stacho Ladislav Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada aut Condon Anne Department of Computer Science, University of British Columbia, Vancouver, BC, Canada aut Natural Computing Springer Netherlands 10/1(2011-03-01), 391-405 1567-7818 10:1<391 2011 10 11047 https://doi.org/10.1007/s11047-010-9239-4 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s11047-010-9239-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Maňuch Ján Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada aut NATIONALLICENCE 700 1- Thachuk Chris Department of Computer Science, University of British Columbia, Vancouver, BC, Canada aut NATIONALLICENCE 700 1- Stacho Ladislav Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada aut NATIONALLICENCE 700 1- Condon Anne Department of Computer Science, University of British Columbia, Vancouver, BC, Canada aut NATIONALLICENCE 773 0- Natural Computing Springer Netherlands 10/1(2011-03-01), 391-405 1567-7818 10:1<391 2011 10 11047 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer