Crystals That Think About How They’re Growing (David Doty, UC Davis)

Spring 2021 Research Seminar: Molecular Programming
Biology offers inspiring examples of molecules that can store and process information to construct and control the sophisticated nanoscale devices that regulate the machinery of life. Yet biology offers few effective design principles for manufacturing such molecules ourselves. Much of synthetic biology relies on "alien technology": evolved proteins that, had evolution not furnished them, we would not know how to design ourselves.

DNA nanotechnology offers a different approach, enabling design of smart molecular systems from first principles. Theory that combines mathematical tiling and statistical-mechanical models of crystallization has shown that algorithmic behavior can be embedded within molecular self-assembly processes. Previous results had experimentally demonstrated algorithmic "tile" self-assembly with up to 22 tile types, creating algorithmically generated patterns such as Sierpinski triangles and binary counters. Despite that success, many information technologies exhibit a complexity threshold -- such as the minimum transistor count needed for a general-purpose computer — beyond which there is a qualitative increase in the power of a reprogrammable system, and it has not been clear whether the biophysics of DNA self-assembly would allow that threshold to be exceeded.

Here we report the design and experimental validation of a DNA tile set containing 355 single-stranded tiles, reprogrammable by tile selection to implement a wide variety of 6-bit algorithms, including copying, sorting, recognizing palindromes and multiples of 3, random walking, obtaining an unbiased choice from a biased random source, electing a leader, simulating Turing-universal cellular automata, generating deterministic and randomized patterns, and serving as a period 63 counter. The system is quite reliable: averaged across the 21 implemented circuits, the per-tile error rate is less than 1 in 3000.

Bio: David Doty is an assistant professor of Computer Science at the University of California, Davis. He is broadly interested in problems at the intersection of physics, chemistry, biology, and computation. This does not mean the traditional "computation in service of natural science" (e.g., bioinformatics, computational chemistry, or molecular dynamics simulation). Rather, certain molecular systems — such as a test tube of reacting chemicals, a genetic regulatory network, or a growing crystal — can be interpreted as doing computation themselves... natural science in service of computation. He seeks to understand the fundamental logical and physical limits to computation by such means.

More information is available at www.cs.washington.edu/events/colloquia.

This lecture was recorded on April 22, 2021 and is closed captioned.