review articles

Doi: 10.1145/2380656.2380675

The challenge of programming molecules
to manipulate themselves.
b Y DaViD Dot Y
theory of
algorithmic
self-assembly

seLF-asseMBLY is the process by which small components automatically assemble themselves into large, complex structures. Examples in nature abound: lipids self-assemble a cell’s membrane, and bacteriophage virus proteins self-assemble a capsid that allows the virus to invade other bacteria. Even a phenomenon as simple as crystal formation is a process of self-assembly. How could such a process be described as “algorithmic?” The key word in the first sentence is automatically. Algorithms automate a series of simple computational tasks. Algorithmic self-assembly systems automate a series of simple growth tasks, in which the object being grown is simultaneously the machine controlling its own growth.

Although large tracts of the theory presented in this article are applicable to non-molecular systems, much of the motivation arises from nanoscale self-assembly (as an engineering field, as opposed to the study of natural self-assembly systems). The broad goal of nanoscience is to manipulate molecules with nanoscale precision. Ambitious long-term applications

include microscopic, chemical-detect-ing robots that move toward and metabolize pollutants, or the integration of human tissue with an implanted medical device.

Why should computer science have anything to do with nanoscience, beyond the obvious role of developing software-modeling tools? Luca Cardel-li, in a panel discussion at the 2011 Conference on DNA Computing and Molecular Programming, observed that while the computing revolution was about the systematic manipulation of information, nanoscience is about the systematic manipulation of matter. Nanoscience provides a novel justification for studying computation. Many of the traditional forms of manual control are simply not possible at small scales. Automating the growth of molecular structures is not merely faster or more convenient than building such structures by hand. Our hands, and the machines they operate, are simply too large to manipulate individual molecules. We must learn to program molecules to manipulate themselves.

DNA is the molecule of choice in many labs, not for its biological properties but for its information-bearing properties. It is easy to synthesize, and its physical properties are well understood. DNA origami45 is currently the most successful laboratory technique for self-assembling DNA. A long scaffold DNA strand is folded into a shape by mixing it with hundreds of shorter staple strands, each of which binds to

key insights

the idea of “molecules that can perform computation” is transforming the way we engineer self-assembling molecular systems.

a small number of simple types of molecules can grow into large, sophisticated nanoscale structures automatically.

understanding the fundamental abilities and limitations of these systems is crucial for guiding experimental work. many known theoretical results have drawn on the theorems, techniques, and paradigms of computer science.