Nondeterministic seedless oritatami systems and hardness of testing their equivalence

Yo Sub Han; Hwee Kim; Makoto Ota; Shinnosuke Seki

doi:10.1007/978-3-319-43994-5_2

Nondeterministic seedless oritatami systems and hardness of testing their equivalence

Yo Sub Han, Hwee Kim, Makoto Ota, Shinnosuke Seki

College of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Citations (Scopus)

Abstract

The oritatami system (OS) is a model of computation by cotranscriptional folding, being inspired by the recent experimental succeess of RNA origami to self-assemble an RNA tile cotranscriptionally.The OSs implemented so far, including binary counter and Turing machine simulator, are deterministic, that is, uniquely fold into one conformation, while nondeterminism is intrinsic in biomolecular folding.We introduce nondeterminism to OS (NOS) and propose an NOS that chooses an assignment of Boolean values nondeterministically and evaluates a logical formula on the assignment.This NOS is seedless in the sense that it does not require any initial conformation to begin with like the RNA origami.The NOS allows to prove the co-NP hardness of deciding, given two NOSs, if there exists no conformation that one of them folds into but the other does not.

Original language	English
Title of host publication	DNA Computing and Molecular Programming - 22nd International Conference, DNA 2016, Proceedings
Editors	Yannick Rondelez, Damien Woods
Publisher	Springer Verlag
Pages	19-34
Number of pages	16
ISBN (Print)	9783319439938
DOIs	https://doi.org/10.1007/978-3-319-43994-5_2
Publication status	Published - 2016
Event	22nd International Conference on Computing and Molecular Programming, DNA 2016 - Munich, Germany Duration: 2016 Sept 4 → 2016 Sept 8

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9818 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	22nd International Conference on Computing and Molecular Programming, DNA 2016
Country/Territory	Germany
City	Munich
Period	16/9/4 → 16/9/8

Bibliographical note

Publisher Copyright:
© Springer International Publishing Switzerland 2016.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-43994-5_2

Cite this

Han, Y. S., Kim, H., Ota, M., & Seki, S. (2016). Nondeterministic seedless oritatami systems and hardness of testing their equivalence. In Y. Rondelez, & D. Woods (Eds.), DNA Computing and Molecular Programming - 22nd International Conference, DNA 2016, Proceedings (pp. 19-34). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9818 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-43994-5_2

Han, Yo Sub ; Kim, Hwee ; Ota, Makoto et al. / Nondeterministic seedless oritatami systems and hardness of testing their equivalence. DNA Computing and Molecular Programming - 22nd International Conference, DNA 2016, Proceedings. editor / Yannick Rondelez ; Damien Woods. Springer Verlag, 2016. pp. 19-34 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{319bbd06374e4367bd42dca7ce30e857,

title = "Nondeterministic seedless oritatami systems and hardness of testing their equivalence",

abstract = "The oritatami system (OS) is a model of computation by cotranscriptional folding, being inspired by the recent experimental succeess of RNA origami to self-assemble an RNA tile cotranscriptionally.The OSs implemented so far, including binary counter and Turing machine simulator, are deterministic, that is, uniquely fold into one conformation, while nondeterminism is intrinsic in biomolecular folding.We introduce nondeterminism to OS (NOS) and propose an NOS that chooses an assignment of Boolean values nondeterministically and evaluates a logical formula on the assignment.This NOS is seedless in the sense that it does not require any initial conformation to begin with like the RNA origami.The NOS allows to prove the co-NP hardness of deciding, given two NOSs, if there exists no conformation that one of them folds into but the other does not.",

author = "Han, {Yo Sub} and Hwee Kim and Makoto Ota and Shinnosuke Seki",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 22nd International Conference on Computing and Molecular Programming, DNA 2016 ; Conference date: 04-09-2016 Through 08-09-2016",

year = "2016",

doi = "10.1007/978-3-319-43994-5_2",

language = "English",

isbn = "9783319439938",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "19--34",

editor = "Yannick Rondelez and Damien Woods",

booktitle = "DNA Computing and Molecular Programming - 22nd International Conference, DNA 2016, Proceedings",

address = "Germany",

}

Han, YS, Kim, H, Ota, M & Seki, S 2016, Nondeterministic seedless oritatami systems and hardness of testing their equivalence. in Y Rondelez & D Woods (eds), DNA Computing and Molecular Programming - 22nd International Conference, DNA 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9818 LNCS, Springer Verlag, pp. 19-34, 22nd International Conference on Computing and Molecular Programming, DNA 2016, Munich, Germany, 16/9/4. https://doi.org/10.1007/978-3-319-43994-5_2

Nondeterministic seedless oritatami systems and hardness of testing their equivalence. / Han, Yo Sub; Kim, Hwee; Ota, Makoto et al.
DNA Computing and Molecular Programming - 22nd International Conference, DNA 2016, Proceedings. ed. / Yannick Rondelez; Damien Woods. Springer Verlag, 2016. p. 19-34 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9818 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Nondeterministic seedless oritatami systems and hardness of testing their equivalence

AU - Han, Yo Sub

AU - Kim, Hwee

AU - Ota, Makoto

AU - Seki, Shinnosuke

PY - 2016

Y1 - 2016

N2 - The oritatami system (OS) is a model of computation by cotranscriptional folding, being inspired by the recent experimental succeess of RNA origami to self-assemble an RNA tile cotranscriptionally.The OSs implemented so far, including binary counter and Turing machine simulator, are deterministic, that is, uniquely fold into one conformation, while nondeterminism is intrinsic in biomolecular folding.We introduce nondeterminism to OS (NOS) and propose an NOS that chooses an assignment of Boolean values nondeterministically and evaluates a logical formula on the assignment.This NOS is seedless in the sense that it does not require any initial conformation to begin with like the RNA origami.The NOS allows to prove the co-NP hardness of deciding, given two NOSs, if there exists no conformation that one of them folds into but the other does not.

AB - The oritatami system (OS) is a model of computation by cotranscriptional folding, being inspired by the recent experimental succeess of RNA origami to self-assemble an RNA tile cotranscriptionally.The OSs implemented so far, including binary counter and Turing machine simulator, are deterministic, that is, uniquely fold into one conformation, while nondeterminism is intrinsic in biomolecular folding.We introduce nondeterminism to OS (NOS) and propose an NOS that chooses an assignment of Boolean values nondeterministically and evaluates a logical formula on the assignment.This NOS is seedless in the sense that it does not require any initial conformation to begin with like the RNA origami.The NOS allows to prove the co-NP hardness of deciding, given two NOSs, if there exists no conformation that one of them folds into but the other does not.

UR - http://www.scopus.com/inward/record.url?scp=84984887340&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84984887340&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-43994-5_2

DO - 10.1007/978-3-319-43994-5_2

M3 - Conference contribution

AN - SCOPUS:84984887340

SN - 9783319439938

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 19

EP - 34

BT - DNA Computing and Molecular Programming - 22nd International Conference, DNA 2016, Proceedings

A2 - Rondelez, Yannick

A2 - Woods, Damien

PB - Springer Verlag

T2 - 22nd International Conference on Computing and Molecular Programming, DNA 2016

Y2 - 4 September 2016 through 8 September 2016

ER -

Han YS, Kim H, Ota M, Seki S. Nondeterministic seedless oritatami systems and hardness of testing their equivalence. In Rondelez Y, Woods D, editors, DNA Computing and Molecular Programming - 22nd International Conference, DNA 2016, Proceedings. Springer Verlag. 2016. p. 19-34. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-43994-5_2

Nondeterministic seedless oritatami systems and hardness of testing their equivalence

Abstract

Publication series

Other

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this