John Reif

Computer Science Department, Duke University

Biomolecular Computation (BMC) is an area of great potential due to the massive parallelism available at the molecular scale. A realistic assessment of the field must take into consideration its immaturity: there are as yet few practical demonstrations and uncertain applications beyond simply NP search problems. This talk surveys the results of BMC to date, and discusses the major challenges in the field, including the development of more realistic abstract models, software tools for simulation and design, new techniques to exploit the potential power of BMC, experimental demonstrations, and of useful applications. We then discuss some recent research results:

1. A hierarchical series of models for BMC that may be used for software simulations, including realistic models that take into account solution concentrations.
2. Efficient algorithms for key tasks in software simulations of BMC computations, including the hashing of DNA complexes.
3. Techniques which more fully exploit the potential power of BMC by taking advantage of local parallelism within a DNA molecule as well as distributed parallelism between molecules.
4. Biological applications of BMC such as the assembly of wet data bases directly from DNA in solution (without transformation to digital form via more traditional gene sequencing techniques) and execution of computation tasks such as searching within these wet data bases.

Friday, April 18, 1997 at 11am in Room 317 the Towne Building, located at 220 South 33rd Street at the University of Pennsylvania.