Ashish Goel
Management Science and Engineering
Stanford University
" Algorithms at the Molecular Scale"
DNA Self-assembly has emerged as an important tool for molecular computation and nano-technology. Also, laboratory techniques have been developed for simple machines and circuits made out of large molecules such as DNA and RNA. The functionality of these nucleic acid molecules is determined chiefly by their base-sequence, making them amenable to algorithmic and combinatorial techniques. In this talk we will describe (a) the design of an error correction scheme for self-assembly, (b) the design of a robust, energy efficient universal Turing machine made out of DNA, and (c) the design of a molecular circuit that can continuously replenish itself. While these results are theoretical in nature, they offer useful insight into the design and analysis of practical molecular algorithms. We will also outline several open algorithmic problems in this field.
This represents joint work with Holin Chen, Anindya De, Morteza Ibrahimi, Chris Luhrs, Rebecca Schulman, and Erik Winfree.
Thursday, March 26, 2009
3:00 - 4:15
Wu & Chen
101 Levine Hall