The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science


                            Computer Science Seminar

                                  Richard Karp
                   International Computer Science Institute 
                                      and
                      University of California at Berkeley


                                 will speak on


                      The Design of Universal Gene Chips:
                  A Combinatorial Problem in Molecular Biology

Abstract:
Two DNA sequences are called complementary if the nucleotides at corresponding
positions in the two sequences are complementary to each other, where the
nucleotides $A$ and $T$ are considered complementary, as are the nucleotides
$C$ and $G$. The DNA double helix consists of two complementary single strands
with chemical bonds between them.  Complementary or nearly complementary
single-stranded DNA sequences tend to stick together; this process is called
hybridization. A specific sequence within a complex mixture of DNA can be
detected by testing for hybridization to a complementary probe sequence. The
DNA microarray, an important technology for analyzing complex mixtures of DNA,
is based on this method of detection.


The design of DNA detection technologies based on hybridization leads to  the
following problem:  construct a large set of DNA molecules (called tags) such
that each tag hybridizes to its own complement, but not to the complement of
any other tag. We present the solution to this problem for a particular
mathematical model of hybridization, and present applications to genotyping,
biomolecular computing and DNA self-assembly.


The central combinatorial problem that we solve is the following. Define the
weight of a sequence over the alphabet $\{A,C,T,G\}$ as the number of
occurrences of $A$ and $T$ in the sequence, plus twice the number of
occurrences of $C$ and $G$. For a given positive integer $h$, construct a
circular sequence of maximum weight, subject to the constraint that all its
consecutive subsequences of weight greater than or equal to $h$ are distinct.


This is joint work with Amir Ben-Dor, Benno Schwikowski and Zohar Yakhini.





                      The lecture will take place in the 
                     Lecture Hall, Room 1, Ziskind Building
                           on Monday, April 16, 2001
                                    at 14:30