Nucleic acids (DNA/RNA) encode information digitally, and are currently the only truly
‘user-programmable’ entities at the molecular scale. They can be used to manufacture
nano-scale structures, produce physical forces, act as sensors and actuators, and do
computation in between. Eventually we will be able to interface then with biological
machinery to detect and cure diseases at the cellular level under program control. The
technology to create and manipulate them has existed for many years, but the imagination
necessary to exploit them has been evolving slowly. Recently, some very simple
computational schemes have been developed that are autonomous (run on their own once
started) and involve only short (easily synthesizable) DNA strands with no other complex
molecules.
We need programming abstractions and tools that are suitable for molecular programming.
Low-level molecular design is required to produce molecules that interact in the desired
controllable ways. On that basis one can then design various kinds of ‘logic gates’ and
‘computational architectures’, which is where much of the imagination is currently
needed. Then one needs programming languages both at the level of gate implementation
(Andrew Phillips at Microsoft Research Cambridge has built a strand-level DNA language
and simulator), and at the level of circuit implementation (I will describe a Strand
Algebra for implementing e.g. automata and Petri nets). Since DNA computation is
massively concurrent, some tricky and yet familiar issues arise: the need to formally
verify gate designs to avoid subtle deadlocks and race conditions, and the need to design
high-level languages that exploit concurrency and stochasticity.