Thermodynamically Favoured Scaffolded DNA Computing, published in Nature

Our Scaffolded DNA Computing system is now published in Nature, with an accompanying Research Briefing! The awesome SDC team:

This SDC system is a new way to compute with DNA molecules. The idea is simple enough: a long DNA strand acts as a supporting scaffold, and a collection of small DNA tile strands act as a program. The tile strands compete with each other to bind to the scaffold, and in doing so execute a computation.

The system is thermodynamically favoured, meaning that the intended output structure is designed to be the most favoured one of all. We can think of it as computing by rolling (energetically) downhill, or in physics/chemistry terms: relaxing to thermodynamic equilibrium. This is a bit different from classical silicon/molecular computation, as these cartoons illustrate (Fig 1 of the paper):

One amazing advantage over some previous approaches is that we can execute the computation by a simple anneal (heat it up! cool it down!), we don't need precise temperature control at all, we don't need to manually prepare special initial states (via gel purification or pre-forming complexes), and errors are naturally suppressed. The system is well suited to programming and program renewal (sequentially running the same test-tube with different inputs---just like on your laptop).

The work is a potentially new direction for DNA data storage, since any data stored on such a system would have natural in-built error correction properties.

We put a lot of work into developing the theory underlying the model. Why? Well, we believe that nothing is as practical as a good theory, and we use theory as the guiding light to tell us where to go. Through this paper, and two others, we developed theory of computation, thermodynamics and kinetics for the SDC:

Theory of computation

• Computational power: We showed the system can simulate a class of simple computers called finite state machines. In fact, we can do a bit more: a follow-up paper [Petrack, Evans et al., DNA32] showed that any so-called `logspace` computation can be implemented.
• Programming algorithms: The SDC is programmable: one set of DNA strands in the fridge, with finite state machines compiled “into” that set.

Thermodynamics

• High probability of the correct output: One concern for thermodynamically favoured computation comes from scale-up: as systems get larger, will the energy landscape be polluted by lots of off-target structures? The answer is no! We prove that no matter what the system size (scaffold length N), the intended/correct output has probability almost 1, i.e. the sum of probabilities of the exponentially many off-target structures is almost 0. To achieve high-probability of the correct answer we merely need domain strengths (or tile-strand length) to be logarithmic in system size “N”. When we first found this result, I was so excited that I almost didn't believe it! (Details in Supplementary Note S3.5.2, and in the above-mentioned theory paper)
• Programming the energy landscape: or controlling the energy landscape with program logic! One of my favourite results: we can use the logic of DNA programs to sculpt their energy landscape. An analogy might be having a compiler that compiles programs to run faster and better on the underlying hardware. For example, Addition of binary numbers in the SDC has a natural error-correcting property where errors are blocked from propagating along the scaffold and usually die away quickly. This helped us in scaling the system up to 25-bit addition, adding numbers in the 10s of millions. A more 'programmed' example was done with a simple wire-like BitCopy program: we designed the logic of the program (or tiles) to kill unwanted kinetic traps and sculpt away other problems in the energy landscape. In our later paper we found a way to generalise the concept to arbitrary SDC programs.

Kinetics

• Fast run time (for molecules that is!): In only quadratic time in system size (scaffold length N) the system reaches the correct answer. The version of this theorem in the SI holds for perfectly isoenergetic bonds/domains, but we later generalised to somewhat adversarial domains that increase in strength along the scaffold.

I feel there is a lot more theory to do here.

Finally, I should add that we built a bunch of algorithms and tools that greatly helped this project:

• Predicting the system on our laptops In an earlier paper by Shalaby, Thachuk and Woods, DNA29 we gave fast algorithms for predicting the probability of any SDC configuration and favoured states (i.e. polynomial-time partition function and minimum free-energy state prediction).
• qslib Amazing library for controlling our qPCR machines. We leverage qslib in many ways, the most spectacular was in demonstrating computations as fast as 1 minute on short 4-domain scaffolds. We also had cosmix, and riverine, for automatically making mixes with our liquid handler.
• kinetic simulator Constantine and Angel's rgrow-based SDC simulator for SDC kinetics helped with designing DNA sequences (along with nuad of course).

We are grateful to our funders: the work was mainly funded by the EIC DISCO project, and early ideas came out of the tail end of our earlier ERC project Active DNA.