Events Calendar

CS Colloquium: Dennis Shasha (Courant Institute - NYU)

Speaker: Dennis Shasha , NYU

Talk Title: Storing Clocked Programs Inside DNA: A Simplifying Framework for Nanocomputing

Series: CS Colloquium

Abstract: In the history of modern computation, large mechanical calculators preceded computers. A person would sit there punching keys according to a procedure and a number would eventually appear. Once calculators became fast enough, it became obvious that the critical path was the punching rather than the calculation itself. That is what made the stored program concept vital to further progress. Once the instructions were stored in the machine, the entire computation could run at the speed of the machine.

This work shows how to do the same thing for DNA computing.
Rather than asking a robot or a person to pour in specific strands at different times in order to cause a DNA computation to occur (by analogy to a person punching numbers and operations into a mechanical calculator), the DNA instructions are stored within the solution and guide the entire computation. We show how to store straight line programs, conditionals, loops, and a rudimentary form of subroutines. We propose a novel machine motif which constitutes an instruction stack, allowing for the clocked release of an arbitrary sequence of DNA instruction or data strands. The clock mechanism is built of special strands of DNA called "tick" and "tock." Each time a "tick" and "tock" enter a DNA solution, a strand is released from an instruction stack (by analogy to the way in which as a clock cycle in an electronic computer causes a new instruction to enter a processing unit). As long as there remain strands on the stack, the next cycle will release a new instruction strand. Regardless of the actual strand or component to be released at any particular clock step, the "tick" and "tock" fuel strands remain the same, thus shifting the burden of work away from the end user of a machine and easing operation. Pre-loaded stacks enable the concept of a stored program to be realized as a physical DNA mechanism.

We demonstrate by a series of experiments conducted in Ned Seeman's lab that it is possible to "initialize" a clocked stored program DNA machine. We end with a discussion of the design features of a programming language for clocked DNA programming. There is a lot left to do.

Biography: Dennis Shasha is a professor of computer science at the Courant Institute of New York University where he works with biologists on pattern discovery for network inference; with computational chemists on algorithms for protein design; with physicists and financial people on algorithms for time series; on clocked computation for DNA computing; and on computational reproducibility. Other areas of interest include database tuning as well as tree and graph matching. Because he likes to type, he has written six books of puzzles about a mathematical detective named Dr. Ecco, a biography about great computer scientists, and a book about the future of computing. He has also written five technical books about database tuning, biological pattern recognition, time series, DNA computing, statistics, and causal inference in molecular networks. He has written the puzzle column for various publications including Scientific American.

Host: Shahram Ghandeharizadeh

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Assistant to CS chair