Nondeterministic Seedless Oritatami Systems and Hardness of Testing Their Equivalence
| Autor: | Hwee Kim, Shinnosuke Seki, Yo-Sub Han, Makoto Ota |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
0301 basic medicine
Discrete mathematics 030102 biochemistry & molecular biology Computer science Existential quantification Model of computation Binary number Nondeterministic algorithm 03 medical and health sciences Turing machine symbols.namesake 030104 developmental biology symbols Logical formula |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783319439938 DNA |
| DOI: | 10.1007/978-3-319-43994-5_2 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|