DNA computation


Sequence specific hybridization of DNA single strands makes DNA molecules a flexible programmable building block. By choosing the right sequences, DNA self-assembly behavior can be programmed to produce well defined nano-structures. In the pioneering work of Seeman et al., branched DNA constructs have been utilized to self-assemble into a variety of structures. With DNA origamis Rothemund invented a way to fold long DNA single strands into well defined planar structures by adding a large number of short stabilizing oligomer strands. Later it was demonstrated how to let the planar origamis self-assemble into 3D nano-structures such as a box [2]. Ever since the pioneering work of Adlemann in 1994, DNA has also been recognized as a massively parallel, versatile, and inexpensive computing substrate. In order for such substrate to be of practical interest, however, it is desirable that the computational framework is scalable and that individual computational elements can be combined to form circuits. Recently, a scalable approach to enzyme-free DNA computing has been proposed where circuits consist of relatively short DNA strands that communicate via strand displacement.

Some results

The figure shows simulations of the strand displacement process underlying Seelig et al.’s DNA computing approach. The top row shows the successful displacement of an initially hybridized 12 bead long signal strand from a 20 bead long template by a 20 bead long signal strand: once the signal strand diffuses to and binds to the toehold region, branch migration occurs quickly (during 300 time units) and the formerly bound signal strand is displaced irreversibly. The bottom row, on the other hand, shows how the displacement stalls in the presence of mismatches: here, a mismatch in the domain (last 10 beads) permits further hybridization of the signal strand. The newly binding and the original signal strand compete for matching bases in a random walk process until the nonmatching strand dehybridizes again and leaves the gate available for potential matching signals (not present in the simulation).

The following figure shows statistics of the displacement processes for several runs: the graphs depict hybridized bases of the original (red) and the newly binding signal strand (green), as well as the branch migration point (black). In the case of matching signals (top two simulations), it can be seen that displacement occurs quickly and essentially irreversible once the original strand is fully displaced. In the third simulation the signal strand and hybridized strand has the same length, and the interface is seen to diffuse forwards and backwards. A single dehybridization event is also observed for the original strand. In the case of mis- matching signals (bottom three simulations), the displacement cannot proceed further than nucleotide 10, and the interface randomly moves between posi- tions 8 and 10, until – occasionally – the mismatching signal dehybridizes from the toehold region (lack of green markers). In this case, the number of beads complementary to the toehold region (here 10, 8, and 5 beads) determines the equilibrium between hybridized and dehybridized configurations, and thus the performance and availability of the gate. Fig. 5 also depicts a source of potential failure in logical gates based on strand displacement, as the output signal can spontaneously dehybridize even in the absence of a matching input signal (as observed in the fourth simulation).



With these initial simulations, we have demonstrated that our coarse-grained DNA model can succesfully simulate DNA assembly as well as DNA strand displacement dynamics which form the basis of state-of-the-art DNA computing approaches. We have successfully simulated self-assembly of DNA tetrahedra and icosahedra from four and twelve branched DNA constructs, respectively. Simulations show that the constructs self-assemble into the expected target structures. We have further simulated successful displacement of an output strand when a matching input strand is present. In the presence of mismatches, we could demonstrate how the displacement process is prevented. Our simulations also capture potential failures of gates based on strand displacement, namely spontaneous release of the output strand in the absence of an input signal. These proof of concept simulations demonstrate how our coarse-grained model can be used to optimize the length and arrangement of toehold and domain structures in DNA computing approaches.

While such gate optimizations do not necessarily require spatially resolved models, our coarse-grained DNA model enables us to study systems that integrate DNA assembly and computing within a single framework. This enables us to use these simulations as a starting point for building and testing statistical mechanical theories describing these complex systems.