DIMACS Mini-Workshop on Combinatorial Structures in Molecular Biology

November 11, 1994
DIMACS Center, Rutgers University

Jerrold R. Griggs, Chair, griggs@math.scarolina.edu
Timothy F. Havel, havel@ptolemy.med.harvard.edu
Ron Shamir, shamir@math.tau.ac.il
Temple F. Smith, tsmith@darwin.bu.edu
Peter M. Winkler, pw@bellcore.com
Presented under the auspices of the Special Year in Mathematical Support for Molecular Biology

Goals of the Workshop

It is the aim of this one-day event to bring appropriate problems of current or continuing interest from molecular biology to the attention of experts in the structures of combinatorics and graph theory. Speakers will be biologists as well as mathematicians who do work relevant to biological problems. The other participants will be leading combinatorists who have an interest in learning about such problems. The emphasis will be on presenting open problems, which participants will continue to investigate after they leave, rather than on solutions to past problems.

We expect to have an ``Oberwolfach-type'' program, with all talks of roughly the same length (20-45 min), not too many talks crowded together, and ample time for participants to present and discuss problems.


Biology's connection to combinatorial mathematics has been solid since Mendel and rapidly expanding since Watson and Crick. Recent work in mapping the human genome, however, has underscored the problem of combinatorial explosion: even with today's vast computing power, many simple-sounding combinatorial tasks in molecular biology are beyond reach.

By understanding the biologists' problems, discrete mathematicians can hope to find practical algorithms for exact solution when possible and approximate solution where necessary. Experience has shown that it is not enough to abstract a problem and then classify it as NP-complete etc.; give-and-take between biologists and mathematicians is essential. We hope in this workshop to get past "language problems" and help biologists understand what the mathematicians can do while the mathematicians (and computer scientists) try to determine what is really needed. Often the mathematicians best able to solve the biologists' problems are not exposed to them. The workshop will be an opportunity to expose the mathematicians to such problems.

Among the principal mathematical subjects we plan to feature is the application of interval graphs and their generalizations, such as 2-unit-sphere graphs, to molecular biology. We should include string matching and algorithmic problems, although we don't want these topics to dominate, since they will already be featured in many of the other planned workshops.

The biological areas we should emphasize include sequence analysis, protein structure prediction, evolutionary tree reconstruction, phylogeny, RNA secondary structure, and certain questions in the fascinating area of popula- tion genetics, applied to prebiotic molecules a la Eigen.

Index Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on November 2, 1998.