SGER: Algorithmic Issues at the Nano Scale

Stanford University, Stanford CA

Investigators

Abstract

Project Summary Self-assembly is the process by which small "components" follow simple combination rules to form intricate structures. DNA Self-assembly is widely believed to be a key tool for nano-technology, nano-robotics, and molecular computation. DNA self-assembly in particular, and nano-technology in general, offer significant algorithmic challenges. This project will explore two exciting directions in this field: 1. Error correction at the nano scale. 2. Models and algorithms for molecular machines. Intellectual merit: Error correction at the nano scale appears to require tools and techniques that are significantly different from those required for error correcting codes. For instance, errors and error correction mechanisms are bound by thermodynamic laws at the nano scale, as well as by the constraint that any "computation" required to correct an error must be carried out using the same underlying error prone physical mechanism. While specific error correction mechanisms are now known in certain cases, a general understanding has been elusive. Many experimental groups have developed rudimentary (but very promising) DNA based molecular machines. Modeling of these machines is in a preliminary stage. Exploratory research in modeling these machines is likely to lead to interesting and challenging algorithmic questions. Broad impact: Error correction at the nano scale will facilitate sophisticated tasks such as counting, growing crystals of pre-specified sizes (no larger, no smaller), shape recognition etc. with great precision using inherently error-prone DNA self-assembly (or other technologies). This would be a new engineering primitive, somewhat like the engine and the semiconductor, with important immediate as well as unforeseen uses. Also, molecular machines may act as sensors, signal carriers, actuators, or drug delivery mechanisms. Undoubtedly, much of the hard work in achieving these goals will be done (and is being done) by experimentalists. But the PI believes that algorithmic techniques will also play an important supporting role. The PI will organize an informal reading seminar where students will explore this area in depth. The PI hopes that this seminar will provide a valuable educational experience. The PI also plans to write an article in a book intended for scientifically literate readers who are not experts in this field; the article will highlight algorithmic issues at the nano scale. 1