Oritatami

Oritatami (折りたたみ, "folding") is a mathematical model describing cotranscriptional RNA folding.

Cotranscriptional RNA Folding

RNA is generated by the following process:

1. The enzyme RNAP (RNA polymerase) unzips a double-stranded DNA helix. 2. RNAP attaches to one of the unzipped strands at a promoting sequence of nucleotides. 3. RNAP travels linearly along the DNA strand from the promoter sequence, reading the DNA's nucleotides. As it does so, it adds the complementary ribonucleotides to the RNA strand. 4. RNAP releases the grown RNA strand upon reading a terminating sequence of nucleotides.

Cotranscriptional folding occurs as the folded RNA is elongated. In other words, hydrogen bonds form between ribonucleotides in the strand as new ones are added to it, not afterword. Hence, the form of the strand at the time of its release is not simply that which has the minimum energy. Rather, it is the one which has "stepwise" minimum energy. At any point in time only the last few ribonucleotides in the sequence may rearrange themselves; the rest must preserve their existing bonds.

Formal Definition of Model

An oritatami system, or OS, is a triple (c, R, delta) where:

1. C is the configuration of beads.

Let T = (Z^2, tilda) be a triangular lattice. A=(x0,y0) tilda B=(x1,y1) if and only if A-B UNION B-A in {(1,0),(1,1)}. Let L=(b_i) be a sequence of bead types from an alphabet B. L may be infinite in size. Then C is an injective function f : L -> Z^2 such that b_i ~ b_i+1 for all i.

In other words C is a laying out of a string of beads on a triangular lattice such that the string does not intersect itself.

PICTURE:

2. R subset B^2 is a symmetric relation defining which pairs of bead types are bondable to each other.

3. delta is the delay of the system.

Only the last delta beads in O's configuration may rearrange themselves. In real implementations delta is determined by RNAP's conscription rate.

Updating an OS O=(c,R,delta,a) with bead type b gives the new OS O'=(c',R,delta,a) such that:

Turing-Completeness

Given the history-dependent nature of the RNA strand's energy level, it is reasonalbe to guess that the oritatami model permits Turing-complete computation. Indeed, this has been confirmed by Geary, Meunier, Schnabel and Seki, whose paper showed that the oritatami model permits Turing-complete computation subject to only polynomial inflation in input size. This was shown as follows:

Oritatami -> Skipping Cyclic Tag Systems -> Cyclic Tag Systems -> Turing Machines

Shape-Folding

It has been shown[x] that there are shapes which unfoldable by all OSs (Oritatami Systems). It is NP-hard to answer the general question "Is this shape foldable by an OS?" However, it has been shown that every shape inflated 3 times is foldable by an OS with delay 1. Moreover, every shape inflated 2 times is foldable by an OS with some finite delay delta. In general, for any OS with delay delta>2, there are shapes which it can fold but which it cannot fold for any smaller delay delta' < delta.

References

@misc{geary2015proving,

   title={Proving the Turing Universality of Oritatami Co-Transcriptional Folding (Full Text)},
   author={Cody Geary and Pierre-Étienne Meunier and Nicolas Schabanel and Shinnosuke Seki},
   year={2015},
   eprint={1508.00510},
   archivePrefix={arXiv},
   primaryClass={cs.CG}

}

@misc{demaine2018know,

   title={Know When to Fold 'Em: Self-Assembly of Shapes by Folding in Oritatami},
   author={Erik D. Demaine and Jacob Hendricks and Meagan Olsen and Matthew J. Patitz and Trent A. Rogers and Nicolas Schabanel and Shinnosuke Seki and Hadley Thomas},
   year={2018},
   eprint={1807.04682},
   archivePrefix={arXiv},
   primaryClass={cs.DS}

}

@InProceedings{10.1007/978-3-319-94812-6_22, author="Masuda, Yusei and Seki, Shinnosuke and Ubukata, Yuki", editor="C{\^a}mpeanu, Cezar", title="Towards the Algorithmic Molecular Self-assembly of Fractals by Cotranscriptional Folding", booktitle="Implementation and Application of Automata", year="2018", publisher="Springer International Publishing", address="Cham", pages="261--273", abstract="RNA cotranscriptional folding has been just experimentally proven capable of self-assembling a rectangular tile at nanoscale in vivo (RNA origami). We initiate the theoretical study on the algorithmic self-assembly of shapes by cotranscriptional folding using a novel computational model called the oritatami system. We propose an oritatami system that folds into an arbitrary finite portion of the Heighway dragon fractal, also-known as the paperfolding sequence {$}{$}P = {\backslash}mathrm{\{}RRLRRLLR{\}} {\backslash}cdots {$}{$}P=RRLRRLLR⋯. The i-th element of P can be obtained by feeding i in binary to a 4-state DFA with output (DFAO). We implement this DFAO and a bit-sequence bifurcator as modules of oritatami system. Combining them with a known binary counter yields the proposed system.", isbn="978-3-319-94812-6" }