Search Results

RNA co-transcriptional folding is a process in which an RNA sequence, or transcript, folds upon itself while being synthesized nucleotide by nucleotide according to its DNA template. Geary, Rothemund, and Andersen have demonstrated how to program a rectangular tile-like shape into (the DNA template of) an RNA transcript that folds co-transcriptionally into the shape in vitro. Using the oritatami model of co-transcriptional folding, we launch the study on the verification of co-transcriptionally folding systems. Shapes are the primary verification target of practical signification; it is abstracted as a set S of points on the 2D triangular grid. Thus, the shape reachability problem asks if the transcript of a given oritatami system goes through all and only the points in S and halts. We demonstrate a logspace reduction from the circuit value problem (CVP), a well-known P-complete problem, into a subproblem of the shape reachability whose input oritatami system is promised to be deterministic and at delay 3 (abstraction of the relative speed of local optimization to that of transcription), thus concluding that this subproblem DSR(3) is also P-complete. What to be verified may specify not only which points to be visited, but also which route should be taken (path reachability), and, moreover, how abstract nucleotides (beads) along the transcript should bind with each other (conformation reachability). We show that as long as the delay is bounded from above by a constant, the conformation reachability can be solved in logspace, and to this problem, path reachability can be reduced in logspace under the promise that a given oritatami system lets beads form as many bonds as possible (maximum arity).