A Coupled Reconfiguration Mechanism That Enables Powerful, Pseudoknot-Robust DNA Strand Displacement Devices with 2-Stranded Inputs

One of the more ambitious goals of molecular programming is to come up with a general framework to write programs for biocompatible molecules, possibly up to the complexity of modern silicon computers. Such a framework would likely involve an abstraction hierarchy, where human-understandable programs are written at higher levels and translated through the layers, eventually producing a set of molecules that physically execute the program. Over the past decades, one candidate pair of layers for such a hierarchy has emerged: the Chemical Reaction Network as an abstract model, and DNA strand displacement as a more physical description of molecules.

The Chemical Reaction Network (CRN) model describes abstract chemical species and the arbitrarily specified reactions they undergo. The stochastic CRN model, in particular, can compute semilinear functions in an “always eventually always” errorless sense [1, 2, 7, 13, 22, 27], and can simulate Turing machines with arbitrarily small probability of error [29]. Various extensions of the model to include polymers have been proposed, which can do Turing-universal computation much more robustly [6, 10, 19, 20, 24, 26, 32]. So a reliable and scalable general CRN implementation would be a good candidate for a general-purpose molecular computer, and an implementation of one of the polymer extensions even more so.

DNA strand displacement (DSD) refers to certain behaviors of DNA, involving parts of strands displacing bonds between other parts, that have been used to build many useful molecular devices [28]. Most such devices have been built out of simple toehold exchange motifs, which in Section 2 we call the $t{x}_3$ and $t{x}_4$ motifs. To help analyze these systems, reaction enumerators [3, 21] and formal models [16, 23] have been developed, turning DSD from a description of experimental reality into a formal system.

Many general implementation schemes for arbitrary CRNs have been designed in DSD, with various relative advantages and disadvantages [5, 8, 18, 24, 30, 31]. Figure 1 gives an example. Such a system will generally involve signal strands, representing the formal species of the CRN, and fuel complexes, assumed “always present” and consumed to drive the CRN’s reactions. While some have been implemented experimentally [8, 31], even 3 species and 3 reactions in a formal CRN is enough to have problems scaling up robustly [31]. There have been attempts to address this, including a design that would be “leakless” on a theoretical level [33, 35]. However, these have not yet led to effective scalable implementations.

We have recently been trying to explore the space of possibilities in DSD, beyond the $t{x}_3$ and $t{x}_4$ motifs that make up most existing DSD systems. This is partly out of theoretical interest, and partly from a more practical motivation: CRN implementation schemes use fuels with at least 3 strands, and have issues scaling up [31]. Meanwhile seesaw gates and some other systems, though they can’t implement arbitrary CRNs, have been made with 2-stranded inputs and scaled up well to larger systems [9, 25, 34]. Therefore we investigated whether arbitrary CRN implementations could be made with 2-stranded inputs (i.e., fuels and signals), with an additional set of desirable conditions: reversible, systematic implementation, uses $O(1)$ orthogonal toehold domains, correct according to modular CRN bisimulation, and built out of bimolecular reactions [16]. We found two systems that can implement arbitrary CRNs, but each with one undesirable condition: one uses $O(n)$ toehold domains, while one requires trimolecular reactions [18]. Both of these conditions would cause issues with experimental implementations. This was not satisfying, so we kept searching.

Existing DSD implementations often implement $A+B\to \mathrm{\dots }$ logic in a way that requires a fuel with at least 3 strands: one strand to bind the reactants $A$ and $B$, one strand to be released in the reaction that binds $A$, and one to be released in the reaction that binds $B$ [30, 31]. The mechanism shown in Fig. 1, for example, represents the binding of $A$ by opening a shared toehold that allows the binding of $B$, but this required kicking off an $A$-specific strand. Recently we found a mechanism we called coupled reconfiguration, where instead of binding one strand and releasing another, two strands can reconfigure each other and split apart. Thus the $A$ signal strand can reconfigure into an “off” state, and the fuel strand can reconfigure into a “bound $A$” state, allowing us to implement arbitrary CRNs with 1-stranded inputs [15]. However, our mechanism depended on a common assumption in DSD models that certain structures called pseudoknots don’t form, and would have undesired pathways if pseudoknots could occur. Specifically, it represented the binding of $A$ by changing which of an $A_1$ or $A_2$ domain was bound to its complement, such that the interaction with $B$ would be non-pseudoknotted only in the “bound $A$” state. While our mechanism was great on paper in the pseudoknot-free model, that model is based not on the belief that pseudoknots actually don’t occur in reality, but the belief that they’re too complex and we don’t want to deal with them. If implemented in reality, it’s likely that the mechanism would simply fail due to pseudoknotted undesired pathways. We again found this unsatisfying, and wondered if coupled reconfiguration could be done without depending on the no-pseudoknots assumption.

Here in Section 3 we present a mechanism we call $C{R}_4$, based on 4-way branch migration, that does coupled reconfiguration without relying on the no-pseudoknots assumption. In particular, the $C{R}_4$ mechanism changes which toeholds are open and closed, meaning we can compose $A$ and $B$ with the same shared toehold logic used in Fig. 1 and most similar systems; but as a coupled reconfiguration mechanism, it does so without requiring an additional strand. In Section 4 we show how this mechanism can implement arbitrary CRNs with 1-stranded inputs, with all the other desirable conditions as well. The $C{R}_4$ mechanism is based on a $2t{x}_4$ motif, which turns out to be useful for implementing polymer CRNs, and in Section 5 we give mechanisms for stack push and pop reactions and for bimolecular surface CRN reactions, all with 1- and 2-stranded inputs. These mechanisms could be slotted in to the existing theory for stacks [24] and surface CRNs [26] without changing the higher abstraction layers, if desired. Our mechanisms are sufficiently far from existing experimentally tested mechanisms that there will likely be challenges implementing them, but we suspect it would be possible. In Section 6 we give some speculation on what challenges may arise and how to overcome them, as well as further theoretical implications.

We work with a formal model of DNA strand displacement systems, and are trying to explore the limits of that model. The more abstract Chemical Reaction Network model is both an important use case for DSD systems and a good way to test the computational power of a class of DSD systems. In this section we give some definitions of Chemical Reaction Networks, DSD systems, and the definition of a correct implementation that we use. Some more formal definitions were omitted for space, and can be found in Appendix A.

Often reactions will be given as a triple $(R,P,k)$, written $R\stackrel{𝑘}{\to }P$, where $k$ is a rate constant. For our purpose we care only what can happen, not how fast it can happen, so we use only $R\to P$. The reversible reaction $R\rightleftharpoons P$ means $R\to P$ and $P\to R$.

Basic steps are meant to be applied to complexes, producing reactions (also called steps) whose reactants and products are complexes. A step between complexes is reversible if its reverse is also one of the steps. $b$ is reversible if the resulting bond meets the conditions for $u$ (short domain and not anchored); $u$ is always reversible by $b$; $m_3$ is reversible by $m_3$ if the initial $(x,x^{\ast })$ bond was anchored; and $m_4$ similarly to $m_3$.

Often when working with DSD systems we want to require that all complexes involved are non-pseudoknotted. This greatly simplifies analysis without too much loss in potential, as pseudoknots are not well understood and thus not reliable for use in engineered systems.

The process of generating the enumerated CRN is often called reaction enumeration, and can be done automatically by tools such as Visual DSD [21] and Peppercorn [3].

While many sequences of steps are in theory possible, the designs in this paper are built out of the same sequence of steps used repeatedly. We often call these motifs [18]. Figure 3 shows the $t{x}_4$ (toehold exchange with 4-way branch migration) and $2t{x}_4$ motifs we use.

Following models such as Peppercorn, we often assume that once two complexes combine and start interacting, no third complex can bind to the result until it’s finished all meaningful unimolecular steps. This is based on a low-concentration assumption where bimolecular steps are slow relative to unimolecular steps, making that assumption realistic. Peppercorn calls this a “condensed reaction”, and gives a proper definition [3]. We use this to implicitly exclude certain complicated and unlikely undesired pathways, but don’t mention it much.

When a DSD system is made to implement CRNs, its initial complexes will generally be made of signals and fuels. Signals represent the formal species of the CRN, while fuels are assumed to be “always present” (left as an exercise to the experimentalist) so they can drive the reactions they’re meant to enable. Once an implementation CRN is enumerated from the DSD system, the fuels are removed (so e.g. $A+f\to B$ becomes $A\to B$ for $f$ a fuel), and we consider an implementation correct if the result meets the conditions of CRN bisimulation [17]. These are, approximately, “anything that can happen, should” and “anything that should happen, can”, where “can” refers to the DSD implementation and “should” to the formal CRN. When we discuss the number of strands in the inputs of a CRN implementation, we mean the signals and fuels. Experimentally, these are the complexes that have to be created externally, one way or another, to make the system run.

One concept we wish to explore here is pseudoknot-robustness, defined in terms of the correctness of CRN implementations. Most DSD systems don’t involve pseudoknots, and many analysis algorithms [3, 4, 12] assume they can’t happen. However, that assumption is based less on a belief that they’re actually physically impossible, and more on a desire not to deal with them. We are therefore interested in systems that are correct whether pseudoknots are possible or not. Formally, this is defined by checking the “anything that can happen, including pseudoknots, should” condition in the anchored, pseudoknot-allowed model, and checking the “anything that should happen, can even without using pseudoknots” condition in the anchored, pseudoknot-free model.

Our (first) goal with this mechanism is to implement generic $A+B\rightleftharpoons C+D$ logic, which is sufficient to implement arbitrary CRNs. However, the method we use is built out of smaller parts, namely the four-way coupled reconfiguration ($C{R}_4$) mechanism; and is best explained by first defining the $C{R}_4$ mechanism and how that mechanism can be abstracted into inputs and outputs, then showing how the general $A+B\rightleftharpoons C+D$ implementation is built out of the abstracted $C{R}_4$ mechanism. So Fig. 4 shows the configurations that a $C{R}_4$ mechanism reconfigures between, and how the toeholds serve as abstractable inputs and outputs; Fig. 5 shows the actual $C{R}_4$ mechanism; and Fig. 6 shows how two $C{R}_4$ mechanisms can be connected by a shared toehold. Ultimately in Fig. 7 we end up implementing $A+B\rightleftharpoons C+D$ as $A+B\rightleftharpoons in{t}_r$, $C+D\rightleftharpoons in{t}_r$ for $in{t}_r$ an intermediate specific to this reaction; this is the same strategy implemented in e.g. the $t{x}_3$-based CRN implementation [5, 8] in Fig. 1.

In our previous work, we designed a $t{x}_3$-motif-based mechanism where two strands come together, reconfigure each other, and split apart; such that neither strand can reconfigure on its own, and when the two strands come together, they can split apart only if both reconfigure or neither does [15]. We named this property coupled reconfiguration, and it allowed us to design arbitrary CRN implementations using only 1-stranded inputs, as opposed to 3- or more-stranded complexes. To our knowledge, this was the first DSD mechanism designed with this property; others had relied on different combinations of strands to get different configurations. However, it was very reliant on the assumption that pseudoknots couldn’t happen, with the strands able to reconfigure on their own via pathways involving pseudoknots. This makes the mechanism theoretically interesting, but likely not to work in reality, and thus unsatisfactory. So the core of the result of this paper is a $C{R}_4$ mechanism, based on the $2t{x}_4$ motif, that does coupled reconfiguration in a pseudoknot-robust way.

Within the pseudoknot-robust anchored model, there are two ways we’re aware of for one $t{x}_3$ or $t{x}_4$ motif to depend on a previous one. (That is, for two motifs in a sequence to be meaningfully in that order, as opposed to two independent motifs that just happened to happen in that order.) First, specific to $t{x}_4$ motifs, one ($t{x}_3$ or $t{x}_4$) motif can put together the combination of two toeholds necessary for a (second) $t{x}_4$ motif to happen. For example, in the $2t{x}_4$ motif in Figure 3, the first $t{x}_4$ motif puts together the $(\mu ,{\lambda }^{\ast })$ combination necessary for the second to happen. This generally involves both motifs acting on the same long domains, so it’s good for creating dependencies within the same long domain identity, but not between independent long domain identities. In the $C{R}_4$ mechanism in Figure 5, all the dependencies between the three $2t{x}_4$ motifs are of this type.

Second, the two motifs can have a shared toehold. By “shared toehold” here we mean a toehold flanked by two long domains, where a motif acting on one long domain opens the toehold, allowing it to be used in a motif acting on the other long domain. The opening of toeholds in most previous DSD implementations is of this type, as in Figure 1.

The $C{R}_4$-based CRN implementation will use both. Within a single long domain identity associated with a given formal species, a specific arrangement of toehold identities allows a sequence of $2t{x}_4$ motifs between a “gate” strand and a “signal” strand in an “on” configuration, after which the signal strand is in the “off” configuration and the gate strand has also reconfigured. The arrangement of toeholds ensures that at any point in the process there are at most two reactions available, the intended forward and reverse reactions, even if pseudoknots are allowed. The gate strand will have different toeholds open and closed before and after the reconfiguration, which allows composition if any of those toeholds is shared with another copy of the $C{R}_4$ mechanism. Opening and closing shared toeholds with coupled reconfiguration means we don’t need the extra strands that most DSD CRN implementations use. While we use 7 (or 6, or possibly less with optimization) orthogonal toehold identities, we can reuse those same 6-7 sequences throughout, which is what we mean by $O(1)$ toeholds.

For one motif to enable another motif via a shared toehold, the first motif should transform the toehold from “unavailable” to “available”, from a state where it can’t do the second motif to a state where it can. In the pseudoknot-robust paradigm, “can” is measured in the pseudoknot-free model, so a toehold is available if it is both unbound and not nested inside another bond. But “can’t” is measured in the model with pseudoknots allowed, so a toehold is unavailable if it is bound. A toehold that is unbound but nested inside another bond can’t be pseudoknot-robustly said to be either available or unavailable.

Our mechanisms involve various $2t{x}_4$ motifs with the same long domain identity eventually opening up a shared toehold, which will then enable more motifs with a different long domain identity. Figure 4 shows, for 3 pairs of alternating long domains $A$ and $A^{\ast }$, the possible configurations, and the availabilities of their toeholds. The “one nested” configurations are particularly useful. A strand that switches between them will have the toehold pair between domains 2 and 3 switch availabilities in one direction, while the pair between 4 and 5 switches in the other. We use 3 pairs because 2 alternating copies of a long domain and its complement have only two configurations, and not enough toeholds that change availability.

We can then describe the $C{R}_4$ mechanism, shown in Figure 5. The mechanism involves two strands, one (“left strand”, purple) reconfiguring between the two one-nested configurations in Figure 4, one (“right strand”, blue) reconfiguring between a one-nested configuration and the linear two-nested configuration. So while the left strand has a pair of toeholds that changes from available to unavailable and a pair that does the reverse, the right strand only has a single toehold that changes from available to unavailable and none that do the reverse. There are multiple regions, indicated by dotted lines, that can contain any sequence without affecting the mechanism unless that sequence somehow interacts with the domains involved in the mechanism. This will be particularly useful for composing copies of the $C{R}_4$ mechanism.

The $C{R}_4$ mechanism as presented is physically reversible, with each step as well as the overall mechanism being fully reversible in the model. It can be made irreversible in either direction by removing a single toehold. Removing either of the two ${\omega }^{\ast }$ toeholds on the left strand will make the reaction irreversible in the direction towards which that ${\omega }^{\ast }$ ends up unbound. (Removing the ${\rho }^{\ast }$ or ${\nu }^{\ast }$ toehold can also do so, but those are used for composition.) Similarly on the right strand, in each direction one of the three $\sigma$ toeholds changes from bound to unbound, and removing it will make the reaction irreversible in that direction.

To implement CRNs, we first need to figure out how to compose modules of the $C{R}_4$ mechanism. Ideally, we would like what we call a systematic, $O(1)$ toeholds implementation, which we defined in our previous work [16]. This means that the “signal strands” for formal species e.g. $A$ and $B$ have the same structure and the same toehold domains, differing only in the identity of their long domain(s), which should be species-specific. To get interaction between independent long domains we want to use a shared toehold, where one of the toeholds that changes availability in one mechanism is the same as one of the ones that changes availability in the other. Given the properties of the mechanism, we need to use the left strand for this, and equate the ${\rho }^{\ast }$ of one mechanism with the $\nu$ of the other. So while Figure 5 had $\rho$ be a unique toehold, for the CRN implementation $\rho ={\nu }^{\ast }$ and ${\rho }^{\ast }=\nu$; the $C{R}_4$ mechanism still works with this replacement. The composition is shown in Figure 6.

Now that we can connect multiple $C{R}_4$ modules, we can use this to make CRN implementations. Similar to our previous mechanism [15], we use left strands as gates and right strands as species strands, where one of the two configurations of a species strand is the “on” state and the other is the “off” state. The on state of a species strand represents the actual species, while the off state is a fuel that represents nothing, unless something turns it on. Then a gate strand will in sequence turn each reactant species off then turn each product species on, each time reconfiguring itself in a way that enables the next interaction.

In contrast to the previous mechanism, this one has a polarity issue: one could not, for example, equate the $\rho$ of one $C{R}_4$ mechanism in Figure 5 with the $\nu$ of another, because the $\rho$ is 5’ of a long domain in its mechanism while the $\nu$ is 5’ of a different long domain in its mechanism. Nor can one connect a $C{R}_4$ mechanism that turns a $B$ off with one that turns a $C$ on, if signals $B$ and $C$ are from the same template. So instead of implementing $A+B\rightleftharpoons C$ in one gate, we implement $A+B\rightleftharpoons in{t}_r$. Here $in{t}_r$ is an intermediate, specific to reaction $r$, and while the species strands use the one-nested state as on and the linearly nested state as off, $in{t}_r$ uses one-nested as off and linearly nested as on. Figure 7 shows this gate. The intermediate strand would then be shared with a second gate for the products, so $A+B\rightleftharpoons C+D$ would be implemented as $A+B\rightleftharpoons in{t}_r$ and $C+D\rightleftharpoons in{t}_r$. For irreversible reactions, ${\omega }^{\ast }$ toeholds should be removed from the gates to make the $in{t}_r$ module of the reactant gate, and all modules of the product gate, irreversible as described in Section 3.

We coded this implementation as a translation scheme in the Nuskell language [4], and ran it in that program to check whether it works. In fact it does on two simple CRNs we tested. At least, it works in the pseudoknot-free model; Nuskell does not calculate pseudoknots, and thus cannot check whether our system is pseudoknot-robust. In general, our argument for correctness is that the same combination of two open toeholds and a long domain does not appear in our system except in the desired reactions, namely the forward and reverse reactions at any given step. Thus no $m_4$ step can happen except for the intended $t{x}_4$ motifs. This can be observed from the figures.

While well-mixed CRNs can do many interesting tasks, they are provably less powerful than classical computers [2, 22, 27, 29]. Adding some form of geometry, such as unbounded polymerization or a surface grid, makes up the difference in computational power. To that end, there have been designs for DSD implementations of polymer CRN-like systems, such as stack machines [24] and surface CRNs [10, 26], and some general polymer models [6, 19].

It turns out that the $2t{x}_4$ motif is convenient for polymerization mechanisms: of the three sequences of 2 long domains (plus flanking toeholds) involved, the motif takes one of them from bound to the second to bound to the third. This can be used to add or remove strands from a polymer. For example, Figure 8 shows a mechanism for adding an additional unit to a linear stack polymer. If necessary this mechanism can be made irreversible by removing appropriate ${\sigma }^{\ast }$ toeholds, but this is not usually desirable for stack machines. It is worth noting that this mechanism is not, technically, a coupled reconfiguration mechanism, since there is no strand or complex that has multiple configurations for the same set of strands.

The four non-stack complexes could be considered fuels, but if instead their presence is controlled by some other system, they can control whether or what gets added to the stack. For example, if their composition toeholds are shared with a species strand from the well-mixed CRN mechanism, that would make a CRN augmented by controllable stacks. Note that the toehold identities here have no correlation to those in Figure 7, so they can be renamed as necessary to be compatible with that mechanism. The stack machine implementation from [24] is, on the formal level, a CRN augmented by controllable stacks, and their implementation could be replaced by ours with no change to the formal augmented CRN. Thus our mechanism can make stack machines with only 2-stranded input complexes.

Another type of polymer system is surface CRNs, given in the same notation as CRNs but where the species are understood to occupy points on a grid [26]. Then a reaction $A+B\to C+D$ means that an $A$ and $B$ at adjacent points to each other interact and become a $C$ and $D$ in the respective same points on the surface. Implementing this generally requires a “replacement-in-place” mechanism, where a species strand bound to a generic base strand is identified by an incoming fuel, and then replaced on the same base strand by a different strand. Though complex, this is possible with the $2t{x}_4$ motif, as shown in Figure 9. Specifically, that figure shows the $B\rightleftharpoons I_r$ half of a $B\rightleftharpoons C$ reaction; the $C\rightleftharpoons I_r$ half is symmetric. Multiple involved strands have toeholds suitable for composition, so the replacement could be controlled by e.g. an $A$ species in a well-mixed CRN.

Strands in Figure 9 are identified by their long domains: the species-specific domain $B$, the reaction-specific domain $r$, and the universal attachment domain $X$. The $rX$ strand has no species-specific domains, so it can interact with the reactant $B$ or the product $C$. The $rB$ and (not shown) $rC$ strands then mediate between the $rX$ strand and the species strands.

To implement the bimolecular $A+B\rightleftharpoons I_r$ surface CRN half-reaction, one could just put together two copies of this mechanism. However, the $rX$ strand would then either have to be in a 3-stranded fuel complex with the $rA$ and $rB$ strands, or start out with the $rA$ strand and have the $rB$ strand enter later. But the second case would not let it remember, halfway through a reaction, whether it’s interacting with the reactants or the products; and what should be $A+B\rightleftharpoons C+D$ could become $A+B\rightleftharpoons A+D$ or any of a few other combinations. Instead, we use a variant mechanism where a $qrX-qrAB$ 2-stranded fuel causes the $A$ strand to be released on its own, rather than attached to the $qrAB$ strand. (We use $q$ as a second reaction-specific long domain to minimize crosstalk potential.) This mechanism is shown in Figure 10. The ${\tau }^{\ast }$ domain at the 5’ end of the $qrAB$ strand is a shared toehold, the same as the ${\tau }^{\ast }$ at the 3’ end of the $rB$ strand as shown in Figure 9. Thus in the full reaction, a $qrAB-qrX$ fuel will find an $AX-X$ complex on the surface, displace the $A$ according to Fig. 10, at which point the newly opened half of those strands will interact with and displace a neighboring $BX-X$ complex on the surface, releasing a $qrAB-BX$ reverse fuel complex and leaving a $qrX-X$ complex on the surface to receive the products.

In our previous work on theoretical polymer systems, we showed that all “single-locus” polymer networks could be implemented by the following five types of reaction schema [19]:

Of those, the stack mechanism in Fig. 8 implements ${\ast }_1\rightleftharpoons {\ast }_{1}E$ and, with modifications, $F{\ast }_1\rightleftharpoons {\ast }_1$. The surface mechanism in Fig. 9 implements ${\ast }_{1}A{\ast }_2+B\rightleftharpoons {\ast }_{1}C{\ast }_2$ when combined with the well-mixed CRN mechanism, and with the mechanism in Fig. 10 implements ${\ast }_{1}AB{\ast }_2\to {\ast }_{1}CD{\ast }_2$ (reversibly or irreversibly). The last of those reactions is only necessary for reactions that look like it, but might be doable by a variant of the stack mechanism.