Mirela Damian

Professor of Computer Science

Villanova University

DNA Computing

I am intrigued by the following question: How can DNA molecules solve computational problems?

DNA computing uses DNA and molecular biology instead of the traditional silicon-based computer technology. The fundamental chemistry of DNA is based on the double helix and the principle of complementarity. Two long DNA strands entwine like vines in the shape of a double helix, which is stabilized primarily by the bonds between complementary bases (A bonds only with T, C bonds only with G). The two strands can come apart at high temperature.

Synthetic DNA molecules have been designed and shown to assemble into DNA double crossover (DX) molecules and triple crossover (TX) molecules. DX and TX molecules have been used to make programmable DNA tiles that act as Wang tiles and can self-assemble into a structure to perform any chosen computation. Each tile is represented by a synthetic DNA double-crossover (DX) molecule with four sticky ends whose sequences represent glues. Tile interactions are programmed by the design of the sticky ends.

Erik Winfree introduced an abstract mathematical model called tile assembly model, a formal model of self-assembly of molecules constrained to self-assemble on a square lattice yet capable of performing computations as a universal Turing machine. A "program" consists of a finite set of unit square tiles with glues on the sides. Each glue has a binding strength represented as an integer. Starting from a single seed tile, growth occurs by addition of single tiles. A tile joins a growing structure when the total binding strength with its neighbors exceeds a temperature parameter T. Tiles can translate but not rotate.

The Tile Assembly Model forbids splitting structures apart. The enzyme self-assembly model strengthns the tile self-assembly model by enabling partial disassembly of structures through the destruction of all tiles within a fixed tile class. In enzyme self-assembly, tiles are divided into two classes, DNA and RNA, and an existing structure can be partially disassembled via the addition of RNase, which destroys all RNA tiles.

The goal of this research project is to design tile systems that can solve various computing problems. We measure the complexity of a solution by the number of distinct tile types and the number of distinct glues.

Publications related to this project

Zachary Abel, Nadia Benbernou, Mirela Damian, Erik Demaine, Martin Demaine, Robin Flatland, Scott Kominers and Robert Schweller. Shape replication through self-assembly and RNase enzymes. In Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'10, pages 1045-1064, Austin, Texas, January 2010.