Self-attraction Removal from Oritatami Systems

Abstract

RNA cotranscriptional folding refers to the phenomenon in which an RNA transcript folds upon itself while being synthesized (transcribed). Oritatami is a computational model of this phenomenon, which lets its transcript, a sequence of beads (abstract molecules) fold cotranscriptionally via interactions between beads according to its ruleset. In this paper, we study the problem of removing self-attractions, which lets a bead interact with another bead of the same kind, from a given oritatami system without changing its behavior. We provide an algorithm for that with overhead linear in the delay parameter, which should be considerably smaller than the length of its transcript. We also show that this overhead is tight.

Y.-S. Han—Supported by International Cooperation Program (2017K2A9A2A08000270) and Basic Science Research Program (2015R1D1A1A01060097) by NRF of Korea.

Kim was supported by NRF (National Research Foundation of Korea) Grant funded by the Korean Government (NRF-2013-Global Ph.D. Fellowship Program).

T.A. Rogers—This author’s research was supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-1450079, and National Science Foundation grants CAREER-1553166 and CCF-1422152.

S. Seki—In part supported by JST Program to Disseminate Tenure Tracking System No. 6F36 and JSPS KAKENHI Grant-in-Aid for Young Scientists (A) No. 16H05854.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Self-assembly is the process by which relatively simple components coalesce to form intricate and complex structures. Studying self-assembling systems can provide us with insights into everything from designing nanophotonic devices [11] to the origins of life [14]. A number of theoretical models of self-assembly have been proposed [2, 12, 15] and some models of self-assembly have been implemented in the laboratory to algorithmically build structures out of DNA [3, 6, 13]. One proposed model of self-assembly is called Oritatami (folding in Japanese) [8], which seeks to capture the fundamental dynamics of cotranscriptional folding. Transcription is the first step in gene expression in which an RNA polymerase attaches to a DNA sequence and sequentially produces RNA nucleotides (A, C, G, U) (see Fig. 1). Cotranscriptional folding refers to the folding of RNA during transcription. That is, as the RNA is transcribed, its nucleotides interact with each other via hydrogen bonds, resulting in the folding of the RNA.

Geary, Rothemund, and Andersen harnessed the power of cotranscriptional folding in order to self-assemble nanoscale tiles out of RNA (RNA origami [9]). Oritatami is a theoretical model to study the computational aspect of cotranscriptional folding. It models a single strand of RNA as a “strand” of abstract molecules, or beads. Each bead is of a certain type taken out of a finite alphabet $\varSigma$. The bead types along with a set of attraction rules specify which beads are attracted to one another. In addition, each oritatami system has a parameter called the delay $\delta$. It models the speed at which cotranscriptional folding occurs. The folding of an oritatami system proceeds by “looking ahead” at the next $\delta$ beads on the strand and folds them so as to create the largest number of bonds. We can see in [1] an oritatami system of delay 3 fold a motif called glider.

Fig. 1.

RNA origami [9]: the cotranscriptional folding of an RNA tile in a laboratory. The gray spiral is a DNA sequence (template), the orange molecule attaching is the RNA polymerase, and the blue output of the polymerase is the RNA transcript. (Color figure online)

The class of oritatami systems implementable in the laboratory by the cotranscriptional folding of RNA is limited by the properties of RNA. More specifically, the attraction rules of oritatami systems are limited by the types of allowable interactions between RNA nucleotides. Therefore, laboratory implementation may require to alter the system so that it fits certain criteria required for experimental implementation. For example, a physical implementation of oritatami systems might rely on the Watson-Crick complementarity (G-C and A-U). If we wanted to implement an oritatami system in this setting which had a rule specifying a bead type is attracted to itself, the self-attraction would need to be removed.

In addition to providing tools to make oritatami systems physically realizable, our results are the first set of results to show an oritatami system being “simulated” by another oritatami system with a different set of properties. Simulation has played an important role in determining the relative power of classes of systems in tile assembly and determining how classes of tile systems relate to each other [4, 7]. In addition, the notion of simulation in tile assembly has given rise to a rich study of intrinsic universality [5, 10, 16] which has provided us with a deeper understanding of tile assembly. The results in this paper are a first step towards using “simulation” to develop a better understanding of the model.

In this paper, we examine the removal of rules specifying that a bead type is attracted to itself, which we call self-attraction rules, from Oritatami systems. Given a system $\varXi$, the goal of self-attraction removal is to create another system $\varXi '$ such that $\varXi '$ behaves in the same way as $\varXi$, $\varXi '$ produces the same set of conformations as $\varXi$, and $\varXi '$ does not contain any self-attraction rules.

2 Preliminaries

Let $\varSigma$ be a finite set of bead types. A bead of type a is called an a-bead. By $\varSigma ^*$ (resp. $\varSigma ^\omega$), we denote the set of finite (one-way infinite) sequences of bead types in $\varSigma$. A sequence $w \in \varSigma ^*$ can be represented as $w = b_1 b_2 \cdots b_n$ for some $n \ge 0$ and bead types $b_1, b_2, \ldots , b_n \in \varSigma$, where n is the length of w and denoted by |w|. The sequence of length 0 is denoted by $\lambda$. For $1 \le i, j \le n$, the subsequence of w ranging from the i-th bead to j-th bead is denoted by $w[i \ldots j]$, that is, $w[i \ldots j] = b_i b_{i+1} \cdots b_j$; $w[i \ldots j] = \lambda$ if $i > j$. This notation is simplified as w[i] when $j = i$, referring to the i-th bead of w. For $k \ge 1$, $w[1 \ldots k]$ is called a prefix.

Fig. 2.

Triangular lattice.

Oritatami systems fold their transcript, a sequence of beads, over the triangular lattice (Fig. 2) cotranscriptionally by letting nascent beads form as many hydrogen-bond-based interactions (h-interactions) as possible according to their own interaction rules. Let $\mathbb {T} = (V, E)$ be the triangular grid graph. A directed path $P = p_1 p_2 \cdots$ in $\mathbb {T}$ is a possibly-infinite sequence of pairwise-distinct points $p_1, p_2, \ldots \in V$ such that $\{p_i, p_{i+1}\} \in E$ for all $i \ge 1$. Its i-th point $p_i$ is referred to as P[i]. Provided it is finite, by |P|, we denote the number of points in it.

A conformation instance, or configuration, is a triple (P, w, H) of a directed path P in $\mathbb {T}$, $w \in \varSigma ^* \cup \varSigma ^\omega$, and a set $H \subseteq \left\{ (i, j) \bigm | 1 \le i, i+2 \le j, \{P[i], P[j]\}\right.$ $\left. \in E \right\}$ of h-interactions. This is to be interpreted as the sequence w being folded in such a manner that its i-th bead w[i] is placed on the i-th point P[i] along the path and the i-th bead interacts with the j-th bead if and only if $(i, j) \in H$. Configurations $(P_1, w_1, H_1)$ and $(P_2, w_2, H_2)$ are congruent provided $w_1 = w_2$, $H_1 = H_2$, and $P_1$ can be transformed into $P_2$ by a combination of a translation, a reflection, and rotations by 60$^o$. Given a configuration (P, w, H), the set of all configurations congruent to it, denoted by [(P, w, H)], is called its conformation. We refer to w as its primary structure. A ruleset $\mathcal {H} \subseteq \varSigma \times \varSigma$ is a symmetric relation over the set of pairs of bead types, that is, for all bead types $a, b \in \varSigma$, $(a, b) \in \mathcal {H}$ implies $(b, a) \in \mathcal {H}$. An h-interaction $(i, j) \in H$ is called valid with respect to $\mathcal {H}$, or simply $\mathcal {H}$-valid, if $(w[i], w[j]) \in \mathcal {H}$. This conformation is $\mathcal {H}$-valid if all of its h-interactions are $\mathcal {H}$-valid. For $\alpha \ge 1$, this conformation is of arity $\alpha$ if the maximum number of h-interactions per bead is $\alpha$, that is, if for any $k \ge 1$, $\bigl |\{i \mid (i, k) \in H \} \bigr | + \bigl |\{j \mid (k, j) \in H\} \bigr | \le \alpha$ and the equation holds for some k. By $\mathcal {C}_{\le \alpha }$, we denote the set of all conformations of arity at most $\alpha$.

Oritatami systems grow conformations by elongating them under their own ruleset. For a finite conformation $C_1$, another finite conformation $C_2$ is an elongation of $C_1$ by a bead $b \in \varSigma$ under a ruleset $\mathcal {H}$, written as , if there exists a configuration (P, w, H) of $C_1$ such that $(P p, wb, H \cup H')$ is a configuration of $C_2$, where $p \in V$ is a point not along the path P and $H' \subseteq \left\{ (i, |P|+1) \bigm | 1 \le i \le |P|-1, \{P[i], p\} \in E, (w[i], b) \in \mathcal {H} \right\}$. This operation is recursively extended to the elongation by a finite sequence of beads as: for any conformation C, ; and for a finite sequence of beads $w \in \varSigma ^*$ and a bead $b \in \varSigma$, a conformation $C_1$ is elongated to a conformation $C_2$ by wb, written as , if there is a conformation $C'$ that satisfies and .

An oritatami system over an alphabet $\varSigma$ is a 6-tuple $\varXi = (\varSigma , w, \mathcal {H}, \delta , \alpha , \sigma )$, where $\mathcal {H}$ is a ruleset, $\delta \ge 1$ is a parameter called delay, and $\sigma$ is an $\mathcal {H}$-valid initial seed conformation of arity at most $\alpha$, upon which its transcript $w \in \varSigma ^* \cup \varSigma ^\omega$ is to be folded by stabilizing beads of w one at a time so as to minimize energy collaboratively with the succeeding $\delta -1$ nascent beads. The energy U(C) of a conformation $C = [(P, w, H)]$ is defined to be $-|H|$; the more h-interactions a conformation has, the more stable it becomes. The set $\mathcal {F}(\varXi )$ of conformations foldable by this system is recursively defined as follows: the seed $\sigma$ is in $\mathcal {F}(\varXi )$; and provided that an elongation $C_i$ of $\sigma$ by the prefix $w[1 \ldots i]$ is foldable (i.e., $C_0 = \sigma$), its further elongation $C_{i+1}$ by the next bead $w[i+1]$ is foldable if

(1)

The bead $w[i+1]$ and h-interactions it forms are said to have been stabilized according to $C_{i+1}$. A conformation foldable by $\varXi$ is terminal if none of its elongations is foldable by $\varXi$. The oritatami system $\varXi$ is deterministic if for all $i \ge 0$, there exists at most one $C_{i+1}$ that satisfies (1). Thus, a deterministic oritatami system folds into a unique terminal conformation.

Fig. 3.

Folding of a glider motif by a delay-3 deterministic oritatami system. (Color figure online)

Example 1

[1]. See Fig. 3 for a delay-3 oritatami system $\varXi$ to fold a motif called glider. Its transcript is a repetition of $a \bullet b b' \bullet a$ and its ruleset is $\{(a, a'), (b, b')\}$. Its seed is colored in red. The first 3 beads, $a \bullet b$, are transcribed and elongate the seed by the seed in all possible ways. The a-bead cannot form any h-interaction or the second bead is inert w.r.t. the ruleset. The third bead, b, can interact with the $b'$-bead in the seed but for that, the a-bead must be located to the east of the previous $a'$-bead; it is thus stabilized there. Then the next bead, $b'$, is transcribed. After the three steps, the third bead, b, is stabilized. It is not until then that its h-interaction with the $b'$-bead is also stabilized.

2.1 Self-attraction-free Oritatami System

A bead type $a \in \varSigma$ is self-attractive according to a ruleset $\mathcal {H}$ if $(a, a) \in \mathcal {H}$. An oritatami system is free from self-attraction, or self-attraction-free, if no bead type in its alphabet is self-attractive according to its ruleset.

We formulate the problem of removing self-attraction from a given oritatami system without changing the behavior in Problem 1. An isomorphism between conformations must be introduced. Conformations $C_1$ and $C_2$ are isomorphic if there exist an instance $(P_1, w_1, H_1)$ of $C_1$ and an instance $(P_2, w_2, H_2)$ of $C_2$ such that $P_1 = P_2$ and $H_1 = H_2$.

Problem 1

(Self-attraction removal). Let $\varXi$ be an oritatami system. Design a self-attraction-free oritatami system $\varXi '$ such that a conformation is foldable by $\varXi$ if and only if the isomorphic conformation is foldable by $\varXi '$.

Replacing the beads in the seed and transcript with pairwise distinct bead types provides a trivial solution, but is not desirable.

The following approach to Problem 1 called bead type modification is promising: When a bead type a is found self-attractive, it is modified as $a_1,a_2, \ldots , a_t$. The ruleset is then modified so as not to allow for any self-attraction but to let a bead interact with any of its modifications; for example, if we make three copies $a_1,a_2,a_3$ of a bead a, none of $(a_1, a_1), (a_2, a_2), (a_3, a_3)$ is in the ruleset but all of $(a_1, a_2)$, $(a_2, a_3)$, and $(a_3, a_1)$ are in it. Moreover, these modifications are to look to non-a beads as if they were identical, or the ruleset should be modified so. More precisely, for any $b \ne a$, the modified ruleset should include the rules $(a_1, b), (a_2, b), (a_3, b)$ if and only if (a, b) is in the original ruleset.

We propose a subproblem of Problem 1 based on this approach and establish the measure for the efficiency of the modification. It employs a subscript-erasing homomorphism $h: \varSigma ' \rightarrow \varSigma$ defined as $h(x_i) = x$ for $x \in \varSigma$ and $i \ge 1$.

Problem 2

(Self-attraction removal by bead type modification). Solve Problem 1 on an oritatami system $\varXi =(\varSigma , w, \mathcal {H}, \delta , \alpha , \sigma )$ so that the resulting self-attraction-free system $\varXi '=(\varSigma ', w', \mathcal {H'}, \delta , \alpha ,\sigma ')$ also satisfies the following properties:

• 1. $\varSigma '=\{x_i\mid x\in \varSigma , 1\le i\le c(x)\}$ for a positive integer c(x) for x.

• 2. $\mathcal {H'}=\{(x_i,y_j)\mid (x,y)\in \mathcal {H},x\ne y\}\cup \{(x_i,x_j)\mid (x,x)\in \mathcal {H},i\ne j\}$.

• 3. h maps the primary structure of $\sigma '$ to that of $\sigma$ and $h(w')=w$.

We use the copying ratio $c=\max c(x)$ to measure the efficiency of $\varXi '$.

3 Bead Type Modification Based on the Event Horizon

The bead stabilization is a local optimization. By definition, the stabilization of a bead in a delay-$\delta$ system is not affected by any bead outside the circle of radius $\delta +1$ centered at the bead stabilized previously. The circle is so called the event horizon. Beads on its circumference can affect the process not geometrically but energetically by interacting with the bead transcribed most recently. The event horizon can encompass at most $3(\delta +1)(\delta +2)$ beads.

The event horizon varies from step to step; in the i-th step is centered at the $i-1$-th bead $a_{i-1}$, which was stabilized previously. The nascent fragment $a_i a_{i+1} \cdots a_{i+\delta -1}$ folds so as to stabilize $a_i$ most stably inside the horizon. During this search, the bead $a_{i+\delta -1}$, which was just transcribed and hence is at the tip of the fragment, can observe every point in and on the horizon, if any, unless being hindered by other beads geometrically. The region observable by the bead $a_{i+\delta -1}$ is never widening but just narrowing as steps go by.

We use bead type modification along the transcript to remove self-attraction. Prior to the transcription of a bead of self-attractive type $a \in \varSigma$, an event horizon is queried for another a-bead, and if there is, then modified the bead to be transcribed into $a_1 \not \in \varSigma$. Later, if another a-bead is about to be transcribed inside a horizon provided with both an a-bead and an $a_1$-bead, then modify its type as $a_2 \not \in \varSigma$; without any $a_1$-bead around, the new type $a_2$ need not be introduced but an $a_1$-bead can be transcribed next. No more than $3(\delta +1)(\delta +2)+1$ modifications are needed per bead type due to the size of an event horizon.

Algorithm 1 is an implementation of the idea for deterministic oritatami systems that are finite in the sense that their transcript is finite. Transient systems need be simulated in line 16 so that auxiliary rules which let a subscripted bead bind to an unsubscripted one are introduced in line 10 but eliminated in the end.

Lemma 1

Let $C = [(P, u, H)]$ be a conformation that is not $\mathcal {H}$-valid. For any $v \in h^{-1}(u)$, the isomorphic conformation $C' = [(P, v, H)]$ is not $\mathcal {H}'$-valid.

Proof

Being $\mathcal {H}$-invalid means that an a-bead interacts with b-bead in C though $(a, b) \not \in \mathcal {H}$. Since $v \in h^{-1}(u)$, the corresponding interaction in $C'$ is between an $a_i$-bead and $b_j$-bead for some i, j. By definition, $(a_i, b_j) \not \in \mathcal {H}'$.    $\square$

Corollary 1

If an elongation of the seed $\sigma$ by $w[1\ldots i]$ is not $\mathcal {H}$-valid, then its isomorphic conformation obtained by elongating $\sigma '$ by $w'[1 \ldots i]$ is not $\mathcal {H}'$-valid.

The inverse of the statement in Lemma 1 is not always true. Imagine in the conformation C, an a-bead is bound with another a-bead. Providing these beads with the same subscript results in an $\mathcal {H}'$-invalid conformation. Preventing them from being subscripted identically actually yields a valid conformation.

Lemma 2

Let $C = [(P, u, H)]$ be an $\mathcal {H}$-valid conformation. For any $v \in h^{-1}(u)$, the conformation $C' = [(P, v, H)]$ is $\mathcal {H}'$-valid if for all $(i, j) \in H$, $h(v[i]) = h(v[j])$ implies $v[i] \ne v[j]$.

Now we show that the resulting system $\varXi '$ behaves as the given system $\varXi$ does. For $0 \le i \le |w|$, let $C_i = [(P_i, w_\sigma w[1 \ldots i], H_i)]$ be the unique conformation foldable by $\varXi$ among all the elongations of the seed $\sigma$ by the transcript’s prefix $w[1 \ldots i]$, where $w_\sigma$ is the primary structure of $\sigma$. That is, $C_0 = \sigma$. The seed $\sigma '$ of $\varXi '$ is obtained from $\sigma$ via the function 3-color, which gives subscripts 0, 1, or 2 to beads of a given conformation so as for adjacent beads not to share a common subscript based on the 3-colorability of the triangular grid graph. It is hence $\mathcal {H}'$-valid due to Lemma 2 so that it is foldable by $\varXi '$. As an inductive hypothesis, assume that $C_i'$ be the unique conformation foldable by $\varXi '$ among all the elongations of the seed $\sigma '$ by the subscripted transcript’s prefix $w'[1 \ldots i]$ and $C_i'$ be isomorphic to $C_i$. Corollary 1 justifies that the stabilization of the $(i+1)$-th bead in $\varXi '$ counts out any elongation of $C_i'$ by $w'[i+1\ldots i+\delta ]$ or by its prefix that is isomorphic to an $\mathcal {H}$-invalid elongation of $C_i$. On the contrary, an elongation of $C_i'$ by $w'[i+1 \ldots i+\delta ]$ or by its prefix isomorphic to an $\mathcal {H}$-valid elongation of $C_i$ is $\mathcal {H}'$-valid due to Lemma 2 because line 18 of Algorithm 1 prevents any nascent bead in $w'[i+1 \ldots i+\delta ]$ from being transcribed in the sight of another bead of identical type. Therefore, only the elongation of $\sigma '$ by $w'[1 \ldots i+1]$ that is isomorphic to $C_{i+1}$ is foldable by $\varXi '$. This concludes the inductive proof.

4 On Deterministic Finite Oritatami Systems

The quadratic copying ratio in Algorithm 1 can be reduced to linear. Algorithm 1 is overly cautious; it forbids an $a_i$-bead to be transcribed inside a horizon with an $a_i$-bead because an $a_i$-bead is not self-attractive while its original was. It suffices to guarantee that in at least one of the most stable elongations of each foldable conformation, not both of a beads interacting with each other are modified as $a_i$. The other elongations may get less stable but it does not affect the behavior of the resulting system because a given system is deterministic so that the next bead is to be stabilized uniquely point-wise and interaction-wise no matter which of the most stable elongations is referred to.

The modified algorithm is implemented as Algorithm 2. A given oritatami system $\varXi = (\varSigma , w, \mathcal {H}, \delta , \alpha , \sigma )$ is deterministic so that, for each $0 \le i \le |w|$, there exists at most one foldable elongation of the seed by the transcript’s prefix $w[1 \ldots i]$; let us denote it by $C_i$. After setting c rather linearly, Algorithm 2 runs as Algorithm 1 up to line 14. It then chooses arbitrarily for each k one representative elongation $E_k$ of $C_{k-1}$, according to which the next bead w[k] is stabilized in the given system. The i-th bead is transcribed at the $\max (1, i-\delta +1)$-th step and it is involved in the stabilization of the previous at most $\delta -1$ beads until it is stabilized at the i-th step. By the i-th execution of the outer for-loop in line 4, the first $i-1$ beads of w have been already subscripted somehow; the remaining beads have not been given subscripts yet. The inner for-loop examines how the i-th bead is bound to preceding (already-subscripted) beads in the j-th representative for all $\max (1, i-\delta +1) \le j \le i$ and chooses a proper subscript m out of the set I. All of the representatives $E_{\max (1, i-\delta +1)}, \ldots , E_j$ may have to be considered because the i-th bead may not be bound to the same bead in all of them. Note that the i-th bead can interact with 5 beads in the first representative but with at most 4 beads in the others. Therefore, $4\delta +2$ subscripts suffice.

Lemma 3

The following statements hold:

• For $1 \le i \le |w|+1$, the elongation $C_{i-1}'$ of $\sigma '$ by $w'[1 \ldots i-1]$ that is isomorphic to $C_{i-1}$ is foldable by $\varXi '$;

• For $1 \le i \le |w|$, the elongation $E_i'$ of $C_{i-1}'$ by $w'[i \ldots i+\delta -1]$ that is isomorphic to the i-th representative chosen in line 3 is $\mathcal {H}'$-valid.

Theorem 1

Given a deterministic finite oritatami system $\varXi$ of delay $\delta$, we can solve Problem 2 for $\varXi$ with the copying ratio $c = 4\delta + 2$.

5 Lower Bounds on Copying Ratio

Having established a linear upper bound on the copying ratio at least for deterministic oritatami systems, now we examine the lower bound. First, we propose a nondeterministic finite oritatami system $\varXi _{nd}$ such that removing self-attraction from it requires a number of new bead types linearly proportional to the length of its transcript (Theorem 2). Based on it, we will design a deterministic finite oritatami system $\varXi _{nd}$ of delay $\delta$, which requires a copying ratio linear in $\delta$ to free itself from self-attraction by bead type modification (Theorem 3). This lower bound asymptotically matches the upper bound established in Theorem 1.

Fig. 4.

Three examples of a part of $C^i_j$ for $\delta = 1$. (a) Illustration of a part of $C^i_i$. (b) The case when $i+j$ is even. (c) The case when $i+j$ is odd.

The transcript of $\varXi _{nd}$ is $w = (b \bullet ^{2\delta +1})^t$ for some $t \ge 1$ and the seed of $\varXi _{nd}$ is empty. Its ruleset is a singleton $\{(b, b)\}$, making b-beads self-attractive and $\bullet$-beads inert. By b[i], we denote the i-th b-bead in w. See Fig. 4 for some of the conformations $C_j^i$ foldable by this system, where $\delta$ is set to 1, in which b[i] is bound to b[j]. Starting from the first bead, b[1], this system can stretch its transcript straight rightward arbitrarily far and switch it back anywhere. The first $\delta +2$ inert beads after b[1] can be stabilized anyhow because it is not until they are stabilized that the next interactive bead, b[2], is transcribed. Stretching them straight rightward is just one possibility. Being stabilized thus, they keep b[1] out of the event horizon at the transcription of b[2]. Otherwise, b[1] can lie in the horizon and pull b[2] next to it and bind. Thus, for arbitrary $i \ge 1$ and $j > i$, this system can fold into a conformation $C_j^i$ in which b[i] is bound to b[j]. Consequently, in order to remove the self-attraction (b, b) by bead-type modification, these b-beads must be modified with pairwise-distinct indices, arising the need for the copying ratio $\lfloor |w|/(2\delta +2) \rfloor$.

Theorem 2

For a given delay $\delta$ and $n \in \mathbb {N}$, there exists a nondeterministic finite oritatami system $\varXi _{nd}$ of delay $\delta$ whose transcript is of length n such that any solution $\varXi '_{nd}$ to Problem 2 for $\varXi _{nd}$ requires a copying ratio $c \ge \lfloor |w|/(2\delta +2) \rfloor$.

The proof of Theorem 2 along with the fact that an oritatami system is only allowed a finite number of unique bead types yield the following result on the impossibility of removing self-attraction from infinite oritatami system.

Corollary 2

There exists an infinite oritatami system $\varXi$ such that there is no solution to Problem 2 for $\varXi$.

Now we give a lower bound for the copying ratio for deterministic systems.

Theorem 3

For a given delay $\delta$, there exists a deterministic finite oritatami system $\varXi _d$ of delay $\delta$ such that any solution $\varXi '_d$ to Problem 2 for $\varXi _d$ requires the copying ratio $c \ge \displaystyle \left\lfloor \delta /4 \right\rfloor$.

We use delay $\delta =4t$. The transcript of $\varXi _d$ is similar to the transcript of $\varXi _{nd}$ for Theorem , having periodic appearance of a self-attractive bead x. Note that conformations in $\varXi _{nd}$ forces the self-attractive bead to have interactions with all other beads of the same type. We want the same phenomenon to happen in $\varXi _d$. Unlike $\varXi _{nd}$, a deterministic system stabilizes each bead at a unique point, so it is not possible to force all possible x beads to interact in the final conformation, since the conformation is planar. Instead, we use the most stable elongations during transcription. First, we design elongations to geometrically force all possible x beads to interact. Second, we prove that these elongations are indeed the most stable elongations to stabilize each bead. Third, we prove that all (x, x) interactions in these elongations are necessary for the system.

When we use bead type modification to remove a self-attractive rule (x, x), one (x, x) interaction in the original system may be removed in the resulting system if we modify interacting beads to the same bead type. If we want to maintain the interaction in the resulting system, we need to modify the beads into distinct types, say $x_1$ and $x_2$. On the other hand, interactions that are not self-attractive cannot be modified by bead type modification. The fact that we cannot remove unnecessary rules freely makes it challenging to design $\varXi _d$.

For every $2i-2$nd bead, we assign an elongation $C_i$ that mimics behaviors of conformations of $\varXi _{nd}$—proceed straight right, make a single right turn and proceed straight left. In detail, the transcript has two parts: The first part $w_h$ of length $\delta$ with the repeated x every fourth bead, and the second part $w_t$ of length $\delta -5$ with distinct bead types for each bead. Given that x is repeated every fourth bead, it is straightforward to see that the set of these elongations is sufficient to force all possible x beads to interact. We need basic rules between the primary structure and the seed for the primary structure to proceed straight. In addition, we design the system so that the nascent beads for $2i-2$nd bead in $C_i$ has interaction strength $S_i=3t+i-1$. Figure 5 is an illustration of different elongations $C_1$ to $C_7$ when $\delta =16$ and $t=\delta /4=4$. The bead x[i] denotes the ith bead x in the transcript, and the bead y[i] denotes the ithe bead. To meet the required strength of interactions, we use beads at the very last of each elongation to have special interactions with the seed. Note that a special interaction in one elongation never appears in any other elongations, since the coordinate of a bead in $w_t$ is distinct for all elongations. The last elongation $C_{2t{-}1}$ is also the final conformation of the system.

Fig. 5.

A list of elongations when $t=4$ and $\delta =16$. The seed is given by three conformations $\sigma _b, \sigma _p, \sigma _r$, which are represented by brown, purple and red colors respectively. Two parts $w_h$ and $w_t$ of the transcript are represented by black and cyan colors respectively. The blue line represents beads already stabilized in the transcript. Thick dotted lines represent special interactions. (Color figure online)

First, we claim that each $C_i$ is the most stable elongation while stabilizing $y[2i{-}2]$. If we compare $C_i$ to $C_j$ where $j<i$, $S_j$ is less than $S_i$ and beads after the primary structure of $C_j$ cannot give additional special interactions. Thus, any elongation from $C_j$ is less attractive than $C_i$. If we compare $C_i$ to $C_j$ where $j>i$, special interactions at the end of the primary structure of $C_j$ makes $S_j$ greater than $S_i$, but these end beads are too far to allow interactions to stabilize $y[2i{-}2]$. Thus, the part of $C_j$ until the last bead of $C_i$ is less attractive than $C_i$, which makes $C_i$ most stable.

Second, we claim that all (x, x) interactions are necessary for $\varXi _d$ to fold into the last elongation $C_{2t{-}1}$. Suppose we compare $C_i$ to $C_{i{+}1}$ while stabilizing $y[2i{-}2]$. Note that the coordinate of $y[2i{-}2]$ differs in $C_i$ and $C_{i{+}1}$. Since $C_{2t{-}1}$ is the final conformation, $y[2i{-}2]$ should be stabilized following the coordinate in $C_{i{+}1}$. Now, since $S_i$ and $S_{i{+}1}$ differs just by 1, if we remove some (x, x) interactions in $C_{i{+}1}$, either $y[2i{-}2]$ is stabilized following the coordinate in $C_i$, or the system becomes nondeterministic. Thus, all (x, x) interactions are necessary. Since there are t different x beads, the lower bound of the copying ratio is $t=\delta /4$.