Computer-Theoretic Abstractions for Molecular Programming

1:30 – 2:20pm, Tuesday, January 26, 2010
CSE 305
David Soloveichik, UW Seelig Lab


Learning how to effectively program complex biochemical systems may one day enable the creation of such engineering marvels as houses that grow from a seed, nanoscale robots that recycle trash by decomposing it into reusable components, and molecular automata that seek out and destroy cancerous cells. The young field of Molecular Programming believes that computer-theoretic abstractions will prove invaluable for understanding and controlling complex chemical and biological systems.

I give an overview of the "Computer Science" of Molecular Programming, focusing on algorithmic self-assembly and formalized chemical reaction networks. Algorithmic self-assembly abstracts the process of crystallization and relates it to Wang tiling. I will describe the connection between the minimal number of types of tiles that assemble into a shape and the shape's Kolmogorov complexity. In formalized chemical reactions, molecules change state upon interacting with each other in a well-mixed solution. I will cover some decidability/undecidability results, a surprising connection to primitive recursive functions, the computational complexity of computing reachability, and other questions.