Computation by origami-templated DNA walkers

Interactions between DNA molecules can be used to perform computation. These DNA computing systems often use DNA molecules as freely diusing reactants in a well-mixed solution. We demonstrate how DNA walkers tethered to an origami-templated track can perform computation. A DNA walker can block a track that intersects with its own, preventing another walker from stepping down this blocked track. These blockages are primitive operations that can be used to perform computation. This thesis demonstrates how blocking interactions between DNA walkers can evaluate formulae posed in propositional logic. When anchorages in the track are viewed as networked machines and the DNA walker is viewed as a coordinated message passed between them, DNA walker circuits can be modelled as a distributed system. Techniques from formal veri- cation can be used to check this system for errors, determining the probability with which the system will end up in a certain state. This forms the basis of a compiler that can automatically design a DNA walker circuit that evaluates a given propositional formula within a specied error tolerance. To show how DNA walker circuits can be simplied, we create a propositional logic system called blocking logic that is proven to be both sound and complete. DNA walker circuits can be implemented and measured experimentally by using fluorescence spectrophotometry to track the position of a walker on the track. To demonstrate proof of principle, circuits were built that implement NOT and NOR operators. To make these circuits operate with minimal error, dierent sources of possible error were investigated and quantied. Cumulatively, the novel contributions that this thesis makes to the eld are: • the experimental design and implementation of a DNA computing system that uses DNA walkers, • probabilistic model checking software that automatically designs these DNA walker circuits, • a propositional logic system that can simplify a DNA walker circuit to an equivalent circuit that uses fewer tracks.