nach oben

Natural Computing

Erschienen in:

28.11.2019

Transcript design problem of oritatami systems

verfasst von: Yo-Sub Han, Hwee Kim, Shinnosuke Seki

Erschienen in: Natural Computing | Ausgabe 2/2020

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

RNA cotranscriptional folding refers to the phenomenon in which an RNA transcript folds upon itself while being synthesized out of a gene. Oritatami model is a computation model of this phenomenon, which lets its sequence (transcript) of beads (abstract molecules) fold cotranscriptionally by the interactions between beads according to its ruleset. We study the problem of designing a transcript that folds into the given conformation using the given ruleset, which is called the transcript design problem. We prove that the problem is computationally difficult to solve (NP-hard). Then we design efficient poly-time algorithms with additional restrictions on the oritatami system.

Vorheriger Artikel Preface

Nächster Artikel Self-assembly of 3-D structures using 2-D folding tiles

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

For the hardness proof, we use the decision variant of TDP, which determines whether or not such a transcript exists.

This definition does not consider any pair both of whose beads are included in \(C_\sigma \) because such a pair is already inert at the beginning of folding.

Bonnet É, Rzażewski P, Sikora F (2018) Designing RNA secondary structures is hard. In: Proceedings of the 22nd annual international conference on research in computational molecular (RECOMB), pp 248–250

Churkin A, Retwitzer MD, Reinharz V, Ponty Y, Waldispühl J, Barash D (2017) Design of RNAs: comparing programs for inverse RNA folding. Brief Bioinform 19(2):350–358

Demaine ED, Hendricks J, Olsen M, Patitz MJ, Rogers TA, Schabanel N, Seki S, Thomas H (2018) Know when to fold ’em: self-assembly of shapes by folding in oritatami. In: Proceedings of the 24th international conference on dna computing and molecular programming (DNA), pp 19–36

Garey MR, Johnson DS (1979) Computer and intractability: a guide to the theory of NP-completeness. W. H Freeman, New YorkMATH

Geary C, Rothemund PWK, Andersen ES (2014) A single-stranded architecture for cotranscriptional folding of RNA nanostructures. Science 345:799–804CrossRef

Geary CW, Meunier P, Schabanel N, Seki S (2016) Programming biomolecules that fold greedily during transcription. In: Proceedings of the 41st international symposium on mathematical foundations of computer science (MFCS), pp 43:1–43:14

Geary CW, Meunier P, Schabanel N, Seki S (2018) Proving the turing universality of oritatami co-transcriptional folding. In: Proceedings of the 29th international symposium on algorithms and computation (ISAAC), pp 23:1–23:13

Geary C, Meunier P, Schabanel N, Seki S (2019) Oritatami: a computational model for molecular co-transcriptional folding. Int J Mol Sci 20(9):2259CrossRef

Hales J, Héliou A, Manuch J, Ponty Y, Stacho L (2017) Combinatorial RNA design: designability and structure-approximating algorithm in Watson–Crick and Nussinov–Jacobson energy models. Algorithmica 79(3):835–856MathSciNetCrossRef

Han Y, Kim H (2017) Ruleset optimization on isomorphic oritatami systems. In: Proceedings of the 23rd international conference on DNA computing and molecular programming (DNA), pp 33–45

Han Y, Kim H (2018) Construction of geometric structure by oritatami system. In: Proceedings of the 24th international conference on DNA computing and molecular programming (DNA), pp 173–188

Han Y, Kim H, Rogers TA, Seki S (2017) Self-attraction removal from oritatami systems. In: Proceedings of the 19th international conference on descriptional complexity of formal systems (DCFS), pp 164–176CrossRef

Han Y, Kim H, Ota M, Seki S (2018) Nondeterministic seedless oritatami systems and hardness of testing their equivalence. Nat Comput 17(1):67–79MathSciNetCrossRef

Harel D, Sardas M (1998) An algorithm for straight-line drawing of planar graphs. Algorithmica 20(2):119–135MathSciNetCrossRef

Hofacker IL, Fontana W, Stadler PF, Bonhoeffer LS, Tacker M, Schuster P (1994) Fast folding and comparison of rna secondary structures. Monatshefte für Chemie / Chemical Monthly 125(2):167–188CrossRef

Ota M, Seki S (2017) Rule set design problems for oritatami system. Theor Comput Sci 671:16–35MathSciNetCrossRef

Xayaphoummine A, Viasnoff V, Harlepp S, Isambert H (2007) Encoding folding paths of RNA switches. Nucleic Acids Res 35(2):614–622CrossRef

Titel: Transcript design problem of oritatami systems
verfasst von: Yo-Sub Han
Hwee Kim
Shinnosuke Seki
Publikationsdatum: 28.11.2019
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 2/2020
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-019-09776-0

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"

Weitere Artikel der Ausgabe 2/2020

Forming tile shapes with simple robots

A survey of cellular automata: types, dynamics, non-uniformity and applications

Attractor landscapes in Boolean networks with firing memory: a theoretical study applied to genetic networks

Preface

Search space reduction of asynchrony immune cellular automata

CRN++: Molecular programming language

Premium Partner