Skip to main content

Algebras and Languages for Molecular Programming

Luca Cardelli ( Microsoft Research, Cambridge )
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.

Share this: