  Tile displacement is a newly-recognized mechanism in DNA nanotechnology that
exploits principles analogous to toehold-mediated strand displacement but
within the context of self-assembled DNA origami tile arrays. Here, we
formulate an abstract model of tile displacement for the simplest case:
individual assemblies interacting with monomer tiles in solution. We give
several constructions for programmable computation by tile displacement, from
circuits to cellular automata, that vary in how they use energy (or not) to
drive the system forward (or not), how much space and how many tile types they
require, and whether their computational power is limited to PTIME or PSPACE
with respect to the size of the system. In particular, we show that tile
displacement systems are Turing universal and can simulate arbitrary
two-dimensional synchronous block cellular automata, where each transition rule
for updating the state of a 2 by 2 neighborhood is implemented by just a single
tile.

Emerging Technologies