Designing and Fabricating Libraries for Combinatorial Chemistry

			Steven Skiena
			Department of Computer Science
			State University of New York
			Stony Brook, NY 11794-4400


Combinatorial chemistry is an exciting new technology for drug discovery.
A large library of distinct drug candidate molecules (say between 200,000
and 1,000,000) is fabricated in a laboratory, and simultaneously exposed
to a particular target.  The most strongly reacting molecules can then be
identified and evaluated as potential drugs.

In this talk, which requires no background in biology or chemistry, I
will present our recent work on designing and fabricating interesting
combinatorial libraries using a technology known as split synthesis.
We will introduce the fundamental laboratory technologies, and the
algorithmic and combinatorial ideas motivating our work.

We have developed algorithms which design efficient synthesis schedules
for an arbitrary library of compounds, thus giving biologists the ability
to build far more sophisticated libraries than they could before. We have
recently begun collaborating with Cold Spring Harbor Laboratory on the
design of a combinatorial library to target the cancer-causing RAS oncogene.

We will also present our related work on sequencing by hybridization (SBH),
a still-developing approach to DNA sequencing and expression analysis
whose core ideas revolve around graph algorithms and combinatorial properties
of strings. We propose a different approach to sequencing by hybridization,
which uses interaction to dramatically reduce the number of oligonucleotides
for de novo sequencing of large DNA fragments, while preserving the
parallelism which is the primary advantage of SBH.  We also propose an
alternate technology for fabricating oligonucleotide arrays, by using
combinatorial algorithms to program the Southern Array Maker apparatus
to fabricate strings via a sequence of row and column operations.

This is talk includes work with R. Bradley, B. Cohen, and D. Margaritis.