### DIMACS Mini-Workshop on Combinatorial Structures in Molecular Biology

#### November 11, 1994

DIMACS Center, Rutgers University

**Organizers:**
**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.

### Summary

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.

Workshop Index

DIMACS Homepage

Contacting the Center

Document last modified on November 2, 1998.