AF: Small: Theory of Molecular Programming: Computability and Complexity

California Institute Of Technology, Pasadena CA

Investigators

Abstract

The ability of scientists and engineers to organize and control matter at the nanoscale is rapidly improving as ever more complicated molecular systems are being built. It is becoming clear that a systematic approach is needed to guide molecular engineers as to the kinds of systems that are useful to construct and are capable of interesting behavior. Consider the state of computer science in the 1940's, at the dawn of the information revolution. A handful of special-purpose, error-prone computers had been built. Alan Turing and others had just initiated the theoretical study of computability theory, which tells us what computers can do given unlimited resources. It was to be 20 years before the advent of computational complexity theory, the study of what computers can do given limited resources. Researchers find themselves in a similar position today in molecular computing. Experimental work in this area is becoming more and more sophisticated. DNA strand displacement has been used to construct a logic circuit, whose components are free-floating DNA strands and complexes, capable of computing square roots. DNA tile assembly has been used to implement cellular automata capable of growing into fractal patterns and counting in binary. DNA origami is enabling precise control and placement of a variety of molecular structures and systems. The PIs believe that molecular programming will ultimately allow fabrication and control of nanoscale and macroscopic artifacts whose nanoscale parts are arranged with nanoscale precision, that these artifacts will have complexity comparable to that of biological organisms, and that molecular fabrication paradigms will be inspired by biological growth and development. Investigation of precisely what feats are possible and impossible to implement with molecular systems, using rigorous mathematical models, is a primary aim in this proposal. Work will focus on the tradeoffs between various resource bounds that arise uniquely from molecular programming. These include number of distinct molecular species, number of bond types, amount of fuel molecules consumed, and time or volume required for assembly/computation. Molecular resources such as molecular motion, rigidity, randomness and nondeterminism will be studied. Today, a proper understanding of which tasks are efficiently executable by chemistry is totally absent. The major goals of this project are to develop this understanding and provide a theoretical foundation for the systematic development of molecular programming. The project includes funding for summer undergraduate students, and the PIs will act as advisees for senior-year undergraduate projects. Additionally, the PIs will be involved in teaching students that are not traditionally associated with computer science so that future molecular engineers can be exposed to methods and practices needed for designing complex nanoscale chemical systems. Students will learn the theory of molecular programming and be part of a new generation to work in this exciting field. The proposed research will be complemented by educational and outreach activities with underrepresented minorities from local K-12 schools.