DNA computing is a new interdisciplinary research area that bridges the gap between computer science and biochemistry. The potential strength of DNA computing lies in the high memory capacity of DNA molecules and the intrinsic massive parallelism of biochemical operations. In 1994, it was demonstrated that it is possible to engage DNA in combinatorial computation through well-established biochemical techniques. The ultimate goal of this four-year project is to establish the foundations of DNA computing while tackling important issues through research and education activities. The following topics are investigated: Establishing theoretical models for DNA computing. Development of computational models, data structures and high-level operations for DNA Computing. Development of a complexity theory for DNA computing. including trade-offs among resources and reducibility. Development of DNA computers algorithms that are more efficient than algorithms on existing computers. Educational plan: An interdisciplinary undergraduate course on DNA computing. The course will be teamtaught. The objective of the course is to introduce students to the basic principles of liquid- phase DNA chemistry and to the relevant notions in computer science. In the last third of the course, students will be divided into teams to work on team projects based on research related problems.
