What does it mean to optimize a molecular system? One particular field in molecular programming is currently faced with that question. The Chemical Reaction Network (CRN) model is often used to describe systems of interacting molecules. The model can either describe real systems, to analyze their behavior and computational function, or describe hypothetical systems, with known computational function but perhaps no known physical
In terms of robust DSD systems and their fuels, we can take a lesson from experiments with seesaw gates [28,40]. For a two-reactant two-product reaction, the Soloveichik et al. translation scheme uses 3-stranded fuels [34], the Cardelli scheme 4-stranded fuels [4], and the Qian et al. scheme [27] (in the corrected version) a 5-stranded or a 7-stranded fuel. The seesaw gates compute logic gates which are less complex than chemical reactions, but they do so with only single strands and 2-stranded complexes [28]. Possibly because of this, they have been used to build larger circuits and to be robust to experimental imperfections, such as unpurified strands [40].
For this purpose, we have been investigating implementing CRNs using only 2-stranded fuels. Simple DSD systems, such as detecting a desired sequence [5] or AND gates [16], are often 2-stranded, in addition to the seesaw gates mentioned above. There is even a class of hairpin-based systems that construct larger structures from single-stranded initial complexes [44], including the Hybridization Chain Reaction often used in imaging [11], and a design for hairpin-based logic circuits [12]. However, none of these are a full Chemical Reaction Network implementation, or even an equivalently powerful dynamical system -while logic gates are universal for computing functions, CRNs have a dynamical behavior that logic gates in general do not.
We focus in this work on DSD systems using only 2-stranded fuels and where all mechanisms are physically reversible. We focus on 2-stranded fuels for the robustness concerns above, as well as the theoretical question of whether 2-stranded complexes are sufficient for complex behavior (as discussed further in [18]). We focus on physical reversiblility because it reduces the quantity of fuel consumed by reversible reactions. Many interesting computations and dynamical behaviors require reversible reactions. For example, logically reversible operations allow computation with arbitrarily low energy if they are implemented with physically reversible reactions [2,3], such as DSD implementations of stack machines [27], Gray code counters [9], and space-bounded computations [37]. DNA buffers [29] use reversible reactions to maintain stable [30] and dynamical [31] spatial patterns. DNA circuits can be reset to process new input signals when reversible reactions are used for restoring fuel molecules in response to reset signals [14,13,12]. (Existing implementations often are or can be made physically reversible; Qian et al. [27] demonstrate it explicitly, while simple methods to make other existing schemes [34,4] physically reversible is an exercise for the interested reader.)
In this work, we discuss ways of implementing CRNs using only 2-stranded fuels and where all mechanisms are physically reversible. We discuss four known 2-stranded DSD motifs that can serve as building blocks for such implementations, and we present a new cooperative 4-way strand exchange motif that starts with 2-stranded complexes. We discuss two ways of implementing general CRNs with these motifs, and tradeoffs between the two schemes. Finally, we show how, using CRN bisimulation, these schemes can be proven correct assuming the assumptions of the formal DSD model reflect real DSD systems.
We believe that having abstract descriptions of simple motifs will help the design of complex DSD systems. Whatever complex behavior is desired, it may be easier to implement by combining the simple logical operations of known motifs. To demonstrate this, we first discuss the 5 motifs and their behavior on an abstract level, then show how various CRN implementations can be constructed and comprehended by combining those abstract behaviors.
We identify five "motifs", or simple condensed reactions, out of which we build two-stranded CRN implementations. Four of these motifs have been previously studied, while one is new. We discuss the properties of each motif in itself, while in Section 3 we will discuss how
2:4
Simplifying CRN Implementations with Two-Stranded DNA Building Blocks those properties interact when building larger circuits. For building two-stranded CRNs, key questions about a given motif are what logical operation it represents, whether its outputs have the form of its inputs and/or the inputs of the other motifs, and whether its outputs and reverse gates are 2-stranded.
A reversible 3-way strand displacement exchanges which of two strands is bound to a gate (Figure 1 (a)). [34], seesaw gates [28], and various others [47].
Cooperative Hybridization (symmetric) [8]. This mechanism, like the two other cooperative motifs, is "cooperative" in the sense that it requires two inputs to simultaneously, "cooperatively", displace parts of the gate complexes for a productive reaction to happen.
Two 3-way strand displacement reactions occur simultaneously on either side of a gate complex, meeting in the middle and releasing an output strand only if both inputs are present (Figure 1 (c)). The input strands are unbound toehold-long domain combinations, while the output strand has those two long domains in combination with a different toehold; but with only one toehold, barring complex mechanisms either one but only one of them can react. However, even if both inputs are single strands the reverse gate is a 3-stranded complex, so this motif is not "reversible with 2-stranded fuels". Introduced and tested by Zhang [46]. Experimentally tested by Dabby [10]. Various mechanisms, simple and complex, based on 4-way strand exchange have been used experimentally in a number of devices [41,24,5,16].
Two 4-way branch migrations happen on either side of a gate, meeting in the middle and separating into two intermediate complexes (Figure 2). Observe that the "top" toeholds (t and t) on the initial X and Y complexes end up on one of the two products, while the "bottom" toeholds (s * and v * ) end up on another. That is, each of the two products carries only half of the information of the original reactants, and products of different instances of this reaction can interact in the reverse reaction. If for example the (t, t) top half of this reaction interacted with a (v * , s * ) bottom half from a different instance, while the (s * , v * ) bottom half interacted with an (a, a) top half, the result would be X and Y complexes with the same form as the original reactants but different toehold combinations. The effect of such a quadruplet of reactions is strand exchange between one pair of complexes coupled to strand exchange between the other, simultaneously changing the open toehold combinations on distinct long domains. This is important because affecting distinct long domains in a coupled manner was the one thing that, under a set of additional restrictions that this mechanism satisfies, our previous work [18] showed that uncooperative 4-way strand exchange could not do.
While the other four mechanisms discussed have been experimentally demonstrated to work, cooperative 4-way branch migration has not yet been tested. In particular, the final dissociation step requires 3 toeholds separated by two 4-way junctions to dissociate. We think this is plausible, based on Dabby's observation that 2 toeholds separated by one 4-way junction can dissociate [10]; or, if this is not the case, that there is some 0 < Length(l) ≤ 6 for which that dissociation is possible and reversible. It is possible that Length(l) = 0 (i.e. no third toehold) will give the desired behavior, but from Dabby's results, "closed" (both toehold lengths at least 2) 4-way branch migration seems to proceed much faster than "open" 4-way branch migration. Thus we suspect that Length(l) = 0, and in particular Length(l) ≥ 2, will give the desired fast and reversible reaction kinetics.
Common to both uncooperative and cooperative 4-way strand exchange is a basic signal complex: two strands, one long domain bound to its complement flanked by one bound pair of complementary toeholds and one open pair of non-complementary toeholds, as seen repeatedly in Figures 1 (d) and 2. As both types of 4-way strand exchange transform complexes of this form into complexes of the same form with different domain combinations, we find an abstract description of this type of molecule useful. For example, we write the molecule with long domain X, open 3' (end of the DNA) toehold t, open 5' toehold s * , and bound toehold m as X(t, s; m). Note that the semicolon distinguishes open toeholds t, s * available for interaction from the closed (m, m * ) toehold pair that cannot interact with other complexes, but can be opened for interaction by a reaction. When the long domain is unimportant or universal, such as a system composed entirely of uncooperative 4-way strand exchange, we omit it and write simply (t, s; m). For experimental reasons we prefer to have strands made up of only non- * or only * domains, and design non- * and * domains to have distinct sequence properties (for example, using a three-letter code [28]). Then X(t, s; m) unambiguously describes the top reactant of Figure 1 (d), with s understood to mean an open s * toehold. With that assumption, the top product in Figure 1 (d) would be X(m, n; s) * , with the first toehold listed still being on the 3' end of its strand, but now understood to mean an open m * toehold. Without that assumption, we might use a more general notation where those molecules are X(t, s * ; m) and X * (m * , n; s * ) respectively. The circle abstraction shown in said figures is also useful to illustrate strand exchange reactions. Each circle represents a strand with one long domain and two toeholds, where half-faded circles represent strands made of * domains. Thin connections (both figures) represent strands bonded directly, requiring matching domains; thick connections labelled with a toehold domain (horizontal in Figure 2) represent strands connected by gate strands from a cooperative 4-way strand exchange reaction, which can be between any domains so long as the appropriate gate exists. Figure 2 A cooperative 4-way branch migration mechanism. Initial X and Y complexes combine with a gate that matches their open toehold combinations, producing two 3-stranded complexes each with one of the strands of X and one of the strands of Y . These complexes can recombine with each other or with the corresponding products of a similar reaction, which in the latter case will produce X and Y complexes with different toehold combinations. On the right, this reaction is shown in abstracted form. The cooperative 4-way CRN is based on groups of four of these reactions, two in the reverse of the direction shown, where in the reverse reactions each product of one forward reaction interacts with the corresponding product of the other forward reaction. Complexes are labeled with names in the abstract notation if applicable, and their role in the cooperative 4-way CRN implementation scheme. "Signal" and "fuel" complexes have 2 strands as desired; stable "intermediate" complexes can have any number of strands; and "transient" complexes will quickly decay to one side or the other of the reaction. The marking of X(t, s, m) as signal and Y (v, t, n) * as fuel is based on the CRN implementation scheme presented in Section 3, but in general the two can be any combination of signal and fuel, or could be intermediates of a more complex pathway.
In Figure 2 we introduce a similar notation for the "intermediate" products of a cooperative 4-way strand exchange reaction, in that case (m, l * , n; X : t, Y * : t * ) and (n * , l, m * ; Y * : v * , X : s). Again the semicolon distinguishes the three open toeholds, listed from 5' to 3' end, from the bound long domain-toehold pairs; each of those pairs is listed as the domains that appear first in 5' to 3' order. Thus the full reaction is
assuming the appropriate fuel (top center), which we do not give a notation to and omit from the reaction, is present.
The above motifs can be combined in various ways to construct implementations of arbitrary Chemical Reaction Networks. To implement arbitrary CRNs, the reaction [26]. From a logical perspective, "join" and "fork" operations are sufficient; the above reactions represent those logics.
We take modular CRN bisimulation [19] as the definition of a "correct" CRN implementation scheme. Given that a scheme is correct, there are a number of other conditions that would be useful to satisfy for various reasons, theoretical and practical. CRN implementations typically have signal complexes that are the primary form of a given formal species, and fuel complexes that are assumed to be always present and drive the reactions. For a CRN to have "only 2-stranded inputs", as desired in this work, means that all signal complexes and fuel complexes are single strands or 2-stranded. We implicitly assume that we are discussing systematic CRN implementations, where we give a template for a generic reaction and construct larger CRNs by combining independent copies of the template with different domain identities. In such a case we can ask how the number of toehold domains scales, i.e. whether different reactions can use the same toeholds or have to create new ones; as toeholds are limited in length by thermodynamics, a system with O(n) toeholds may be able to implement small CRNs but a system with O(1) toeholds is better if possible. Whether a scheme requires cooperative mechanisms is worth noting. Finally, it is desirable for reversible reactions (A + B C + D) to be implemented with physically reversible mechanisms, so that going forward and backward multiple times does not consume fuel; to be truly reversible, the 2-stranded fuel criterion should include the reverse fuels as well. For further discussion and formal definitions of these criteria, see [18], which also contains a proof that no CRN implementation scheme using only 4-way branch migration can satisfy all of them.
Existing CRN implementations [34,27,4] are often based on toehold exchange mechanisms where e.g. A + B → C is implemented by a toehold exchange reaction with A opening a toehold on the gate for a reaction involving B. These schemes can be understood in light of the motifs previously discussed: the property of toehold exchange that a different toehold on the gate is opened allows join and fork logic. The property that the released strand has a different long domain/toehold combination is used to pass signals between gates. The same shared-toehold logic could also be used with 4-way branch migration instead of toehold exchange, similar to the 4-way-based AND gate [16] (although that gate itself uses a toehold hidden in a loop rather than a toehold shared between adjacent long domains, which is a line of investigation to be explored elsewhere).
Such a shared-toehold mechanism seems to require a 3-stranded complex for the gate molecule to achieve join logic, so it does not meet the goal of this paper, but is worth mentioning as the current state of the art. Another relevant mechanism using toehold exchange is the seesaw gate [28], where transduction logic combines with threshold logic to check whether the total amount of signal is more than either A or B can produce by itself. This achieves join logic for macroscopic signals but cannot satisfy criteria such as CRN bisimulation for individual molecules.
The symmetric cooperative hybridization is A + B C + D logic, if we consider the same long domain in a different toehold context to be a different signal. Since toehold exchange reactions depend on the combination of long domain and toehold, this is valid. Thachuk et al. use a combination of symmetric cooperative hybridization and toehold exchange to implement leakless A + B → C + D reactions in exactly this manner [38,39,42]).
From our perspective, the only problem is that symmetric cooperative hybridization with 1-stranded inputs produces 2-stranded products, and toehold exchange with a 2-stranded input signal produces a 3-stranded reverse gate. For physically reversible reactions, this 3-stranded gate would be considered a reverse fuel, and the system would not be made with entirely 2-stranded fuels. Thus this mechanism meets all our criteria for irreversible CRNs, but not reversible CRNs.
The two-toehold-mediated 4-way strand exchange mechanism effectively exchanges toeholds on a common long domain; note that while the inputs both have t and s toeholds, the outputs have one with only t and one with only s. When a signal complex goes through multiple copies of this reaction with different fuels, it can turn any combination of toeholds into any other combination. When two signals with complementary pairs of toeholds meet in this reaction, it produces two signals with different combinations in A + B C + D logic. So for example, we can turn (a 1 , a 2 ; a 3 ) into (r 1 , r 2 ; r 3 ) and (b 1 , b 2 ; b 3 ) into (r 2 , r 1 ; r 4 ), which will react and produce (r 3 , r 4 ; r 2 ) * and (r 4 , r 3 ; r 1 ) * , which can be turned into (c 1 , c 2 ; c 3 ) and (d 1 , d 2 ; d 3 ) respectively. Thus two-toehold-mediated 4-way strand exchange alone can implement arbitrary reversible CRNs if we allow O(n) toeholds.
A list of all species involved is given in Table 1. Note that fuels (r 2 , r 1 ; r 5 ) and (r 1 , r 2 ; r 6 ) can interact, but the products can do nothing but reverse the reaction, and the same is true for (r 4 , r 3 ; c 2 ) * with (r 3 , r 4 ; d 2 ) * .
The cooperative 4-way strand exchange motif in Figure 2, when its products recombine with products of a different instance of the reaction, simultaneously exchanges the toehold combinations on a complex with long domain X and a complex with long domain Y . If A(t, s; m) is the signal molecule for A, then simultaneously breaking the (t, s) combination on A and putting together a (u, v) combination on some long domain R is effectively converting A(t, s; m) R(v, u; n) * if all other molecules involved are considered fuels. Where R is unique to the reaction A + B C + D, we can convert the four signal species from their own long domains to the R domain, then use a two-toehold-mediated 4-way strand exchange reaction to implement the reaction itself. In contrast to the previous implementation scheme, that each reaction has a different long domain allows the toeholds (u, v, etc.) to be universal, using O(1) toeholds at the expense of requiring cooperative hybridization. In the notation used in Figure 2, this quadruplet of reactions (with the appropriate top-center fuels assumed present but not written) is As this scheme is based on the O(n)-toehold scheme, we reuse the mechanism from Table 1. Assume all complexes in that list have long domain R, unique to the reaction A + B C + D. To the toeholds listed, add toeholds t, s, m, n, l, and let a 3 = b 3 = c 3 = d 3 = n * , with u and v in the above quadruplet renamed appropriately. Then use cooperative 4-way strand exchange to convert A(t, s; m) (R * (a * 1 , a * 2 ; n)) * = R(a 1 , a 2 ; n * ) (the fuel will have R * on the "top" strand with A), B(t, s; m) R(b 1 , b 2 ; n * ), C(t, s; m) R(c 1 , c 2 ; n * ), and D(t, s; m) R(d 1 , d 2 ; n * ). This gives a mechanism with one long domain per species, one long domain per reaction, and a total of 19 toeholds. Because the long domains now indicate species/reaction identity, the toeholds can be shared between all species and reactions without crosstalk.
The correctness of the schemes can be verified by CRN bisimulation, a formal definition of correctness of a CRN implementation that implies several desirable properties [19]. Below we give an intuitive explanation of why the schemes are correct that parallels the definition of CRN bisimulation; readers familiar with CRN bisimulation can fill in the details of the formal proof. Intuitively, CRN bisimulation consists of interpreting each DNA complex as zero or more formal species, then confirming that the behavior of the formal system and the interpreted DSD system are the same from any initial state. That is to say, any reaction of the DNA complexes should be interpreted as a reaction of formal species that is either valid or trivial ("anything that can happen, should"), and any reaction of the formal interpretation of a set of DNA complexes should be possible, perhaps after some trivial reactions, starting from that set of DNA complexes ("anything that should happen, can"). Table 1 is effectively a proof of the correctness of the O(n)-toehold 4-way-based scheme according to CRN bisimulation [19]. For each A + B C + D reaction, construct a copy of this mechanism with unique r i domains, but any a i domains in common with other reactions using the same formal species; reactions with fewer reactants or products can have one of A, B, C, or D as a fuel; reactions with more reactants or products should D N A 2 6
Simplifying CRN Implementations with Two-Stranded DNA Building Blocks be broken into steps with at most 2 of each [26]. DNA complexes in columns labeled A, B, C, or D are interpreted as one copy of the corresponding species, while complexes in columns labeled ∅ are fuels. Formally, fuels are assumed always present and removed from the enumerated implementation CRN before bisimulation verification; so for example the physical pathway (r 2 , a 2 ; r 3 ) + (a 2 , r 2 ; r 5 ) (r 5 , r 3 ; r 2 ) * + (r 3 , r 5 ; a 2 ) * would be represented as (r 2 , a 2 ; r 3 ) (r 5 , r 3 ; r 2 ) * , and then interpreted as the trivial reaction A A. Using the abstraction for 4-way strand exchange notation, the table is structured such that each non-fuel species can interact with the (usually two) fuel species in the same row, producing the corresponding fuel+non-fuel pair above or below it; that the final A + B forms react to produce the final C + D forms, while their fuels also have a spurious-but-harmless reaction with each other; and that, given the uniqueness of the domains, no other intramodule or inter-module reactions exist. In CRN bisimulation, we say that a reaction interpreted as, for example, A
A is "trivial", and in this case all reactions are trivial except (r 1 , r 2 ; r 3 ) + (r 2 , r 1 ; r 4 ) (r 3 , r 4 ; r 2 ) * + (r 4 , r 3 ; r 1 ) * which is interpreted as the desired reaction A + B C + D. With (a 1 , a 2 ; a 3 ) etc. as the signal species, one can see that the signal species can implement the formal reaction, and any intermediate species can turn into the common species with the same interpretation by interacting with only fuels. Intuitively this is a good argument for correctness, and readers familiar with CRN bisimulation will recognize the above as a sufficient condition for modular CRN bisimulation with respect to the signal species as common species.
For the cooperative 4-way scheme, the same bisimulation logic applies. In the notation used in Figure 2 and Section 3, in e.g. A(t, s; m) R(a 1 , a 2 , n * ) the signal complex A(t, s; m), output complex R(a 1 , a 2 , n * ), and intermediate (m, l * , n; A : t, R : a 2 ) all interpreted as A, while the other three intermediates and all the fuels will each be interpreted as nothing. From there the bisimulation proof follows the O(n)-toeholds case. In this case the lack of crosstalk between modules is assured by the distinct long domains; even if toehold combinations are identical, different long domains will make the reaction unproductive. The remaining caveat is with the cooperative 4-way mechanism itself. We designed the system so that the toeholds along the cooperative reaction are always m, l, n. Thus, we assume that intermediates of the cooperative pathway will all have the matching m, l, n toeholds, and all three toeholds will bind and dissociate as a unit. Whether this is actually true or not will be determined experimentally; if not, there may be problematic crosstalk between, for example, an (A, R 1 ) and (A, R 2 ) pair of long domains which leads to temporarily duplicated signals. If it is true, however, then the result of such a crosstalk will be a release of one side with the other suspended, one of which carries the signal, and the system will be correct according to bisimulation.
We discussed the use of DNA Strand Displacement to implement Chemical Reaction Networks, and the desire to create larger, more robust DSD CRN implementations. We then presented 2-stranded DSD motifs which we used to build 2-stranded CRN implementations, in the hope that they would be more robust than those which rely on 3-or-more-stranded complexes.
There is some indication that 2-stranded DSD systems in general are more robust (as we briefly reviewed in the introduction), but whether these particular systems are more robust than the current state-of-the-art CRN implementations is an open question. We can compare Soloveichik et al.'s original CRN scheme [34,36] (which is reasonably representative of other toehold exchange schemes), our O(n)-toehold 4-way strand exchange scheme, and our (O(1)-toehold) cooperative 4-way strand exchange scheme. While 3-and 4-stranded complexes may be less robust, in other aspects the toehold exchange scheme is simpler than our two schemes: it uses one long domain per formal species, one long domain per reaction, and can be done with a single, universal toehold. To go from reactant signal species to product signal species in the toehold exchange scheme (as implemented experimentally [36]) takes 4 toehold exchange steps in an A + B → C + D reaction, and generalizes naturally to n + m steps in an n-reactant m-product reaction. In contrast, while the cooperative 4-way scheme also uses one long domain per formal species and reaction, as described above it uses 19 universal toeholds and takes 30 reactions for A + B → C + D. (By "reaction" we mean roughly one condensed reaction as described in Peppercorn [17], generalized to include trimolecular reactions. So one toehold exchange or one 2-toehold-mediated 4-way strand exchange is one reaction, as is the cooperative 4-way strand exchange shown in Figure 2; note that using that mechanism to exchange e.g. A(t, s; m) R(a 1 , a 2 ; n * ) takes 4 such reactions.) The O(n)-toeholds scheme takes only 14 reactions for A + B → C + D, but with one universal long domain it takes 3 toeholds per species and 6 per reaction, which may run out of design space for large CRNs. Also, 14 reactions is still much more than 4. These pathways are not provably optimal; we suspect they can be reduced to less than 14 and 30, but still more than 4.
The increase in number of reactions to implement A + B → C + D may just be a cost of using 2-stranded complexes. The fundamental question is, given a complex of a certain size, how much information can it store? How can complexes meant to represent A, C, and an E from another reaction all present different enough open and bound domains that none can undergo a reaction meant for a different one? With 3-stranded complexes and toehold exchange, the long domain identity and open toehold does this very efficiently. With 2-stranded complexes and 4-way strand exchange, we use pairs of toehold identity to represent signal identity, which means we need extra reactions to (a) change the toehold identity one strand at a time, and (b) ensure that intermediates of different pathways don't try to pass through the same toehold combination. This question, then, connects to another work of ours. The final result of that work was a proof that a systematic CRN implementation that satisfies certain desirable conditions, including using only 2-stranded inputs and the other conditions discussed at the beginning of Section 3, cannot be done with DSD using only 4-way branch migration [18]. The steps taken to prove that result involve questions of what sort of transformations are possible with DSD reactions, and how and whether the possibility of certain transformations can depend on the features of the strands. This "dependence" is in the sense that the release of a strand in toehold exchange "depends on" the incoming strand having the correct toehold and long domain identities, or the way we have to structure our CRN implementations so that production of the output species depends on the inputs having the correct toehold identity pairs. Thus, further exploration of that line of investigation might help answer some of the questions suggested by the mechanisms in this paper, of whether 2-stranded complex based CRN implementations inherently require longer pathways, and quantitatively how much longer. Moreover, the investigation could be expanded to include other CRN implementations involving enzymes. For example, transcriptional circuits [20,21], PEN-DNA toolbox [23,1], primer exchange reaction cascades [22], and strand-displacing polymerase systems [35,32,33] all have elementary reactions that can be abstracted as motifs and are candidates for formal analysis. In these systems, it is possible to start with fewer and simpler fuel molecules (e.g. single strands only) while more complex molecules can be generated by DNA polymerase to carry out desired reactions. In addition to 3-way and 4-way strand displacement with standard toeholds, other mechanisms could also be investigated, D N A 2 6
Simplifying CRN Implementations with Two-Stranded DNA Building Blocks including remote [15], associative [6], and allosteric [43] toeholds. These mechanisms may allow further simplification of the implementations as they enrich the design space with alternative representations of signals.
It is also worth discussing how we discovered the cooperative 4-way strand exchange motif and associated CRN implementation in the process of working out the impossibility proof in [18]. We give an intuitive list of those conditions at the beginning of Section 3, but readers desiring a formal list of conditions should see [18]. Two of the conditions are using only O(1) toeholds and not using cooperative mechanisms, so both the O(n) toeholds uncooperative 4-way strand exchange based scheme and the O(1) toeholds cooperative 4-way strand exchange based scheme satisfy all but one of the conditions, each failing to satisfy a different one. Thus in some sense this paper is the positive counterpart to the previous negative result, forming a tight upper and lower bound on the complexity of DSD implementations of CRNs. But this pair of results also has implications for design of DSD systems. The cooperative 4-way strand exchange motif and the process by which we came up with it is potentially a proof of concept that, in systematically eliminating possibilities in DSD systems, we can find new motifs in whatever remains. How exactly this can be generalized we do not know, but if it can be, it may make the process of designing DSD systems faster and more systematic.
Another aspect worth mentioning is the focus on motifs before building up CRN implementations. We argued that each of the 5 motifs has certain abstract behaviors, and that larger systems such as CRN implementations can be thought of in terms of those behaviors. When building large systems, it is much easier if one can build mid-sized building blocks out of the fundamental units, then build larger systems out of the mid-sized building blocks. Motifs take that role between fundamental DSD steps (bind, unbind, 3-way branch migration, 4-way branch migration) and systems on the scale of CRN implementations. To the extent that we were able to describe our CRN implementations in terms of the motifs rather than in terms of the underlying DSD steps, this approach should be considered for future DSD system design.