Joint Penn-UDel Colloquium on the Nature of Computing


DNA Solution to the Maximal Clique Problem

Peter D. Kaplan

Department of Physics, University of Pennsylvania



DNA Computing Logo of the Libchaber Lab by Jun Zhang


The algorithm for solving computer problems with DNA is to
(1) encode all possible answers in strings of DNA and
(2) remove incorrect answers.
Focusing on the first step, we have developed the technique of Parallel Overlap Assembly to generate pools of molecules for computation and used one such pool to solve the NP complete maximal clique problem. Ideas for improving the current algorithm will be discussed.

Based on "DNA Solution to the Maximal Clique Problem," Science, 278, October 17, 1997.

Friday, November 21 at 4pm Room 209 of the Johnson Pavilion near Spruce and 36th Streets on the University of Pennsylvania campus. Travel Directions are found at http://www.upenn.edu/fm/map/dir.html

The Joint Penn-UDel Colloquium on the Nature of Computing meets on the third Friday of each month.
To receive future announcements, or make suggestions, send email to wood@cis.udel.edu or check our
Joint Colloquium home page, http://www.cis.udel.edu/~wood/DNA/colloquium
Prior colloquium
Next colloquium
Home Page of Joint Colloquium
Peter D. Kaplan: DNA Solution to the Maximal Clique Problem
Compiled by / wood@cis.udel.edu / Last revised November 13, 1997