(1) This multi-disciplinary project concentrates on developing computation at the molecular level, via manipulation of DNA strands on surfaces. An experimental demonstration of DNA-based computation by Adleman(a) has changed the view of what computation is, (b) offers the potential for unprecedented computing power at the molecular level, and (c) raises fundamentally new research problems in chemistry, computer science, and material science. This project represents a concerted attack on these problems which involves close collaboration between chemists, material scientists, and computer scientists.(2) This research will help answer two major questions on DNAcomputation. First, does computation at the molecular level have the potential to provide computing power that is orders of magnitude greater than foreseeable extrapolations of current technology? Second, is this type of computation suited to solving NP-hard problems (problems that are well beyond the limits of current technology?(3) The potential for huge computing power rests on the use of DNA strands to encode information and the manipulation of these strands in a massively parallel fashion, involving as many as 2^70 (2 to the 70th power) distinct strands. The premise of this project is that surface-based chemistry is a critical technology in approaching this scale. With this approach, DNA strands are immobilized on a surface, thus allowing a much greater degree of control in chemical processes that manipulate the DNA than is achievable via the test tube based methodology of Adleman. While surfacebased chemistry is the basis for recent strides in combinatorial chemistry, this project is the FIRST to fully exploit surface-based manipulation of DNA strands for the purposes of DNA computation.(4) Scaling up current surface chemistry to approach the requirements of DNA-based computation requires high-quality research at the interface of materials science and chemistry. Improvements in the nanoscale morph ology and chemical makeup of the surface is key to ensuring that a high density of information can be obtained and reliable chemical manipulations performed. Good surface attachment chemistry and control of chemical ``operations'' or enzymatic processes are also extensively developed. This project should result in significant advances in the state of- the-art in surface chemistry and should provide a solid basis for predicting the limits of surfacebased DNA computation.(5) An eventual goal of DNA-based computation is to perform massivelyparallel searches for optimal solutions of NPhard problems. However, the differences between DNAbased computation and conventional technology require that radically new algorithms be developed for this paradigm. Tempering the potential for unprecedented parallelism (up to 2^70 simultaneous operations) is extremely slow and errorprone nature of the operations themselves. Novel strategies for generating and searching solution spaces for NPhard problems are investigated. These strategies embody sound algorithmic principles that can be applied to a range of problems. Using a combination of analysis and simulations, the effectiveness of these strategies are tested on selected applications. This work provides new ways of attacking NPhard problems that, while designed for a hypothetical DNA based computer, are valuable for massively parallel computing paradigms, other than the DNA-based paradigm studied here.(6) Thus this comprehensive program will provide a deep understanding of the potential and limitations of DNAbased computation, from both the chemical and algorithmic viewpoints.***
