DIMACS 1994-00 Special Year on Molecular Biology

Discrete structures have been used to formulate some of the most fundamental concepts of molecular biology. It is now well-known that information storage within a cell is by means of long nucleic molecules which can be thought of as long strings of smaller units called nucleotides. Some of the most important problems of modern molecular biology involve combinatorial and algorithmic questions about these strings. Models of proteins, DNA, and RNA molecules as sequences form a basic tool of molecular biology.

Throughout its history, molecular biology has interacted with methods of discrete mathematics and theoretical computer science. The first nucleic acid sequence was determined in 1965 by R.W. Holley and his co-workers at Cornell University (it contained 77 bases). The method used was the fragmentation stratagem, which involved the combinatorial problem of reconstructing an unknown sequence from fragments obtained by certain enzyme decompositions. Graph-theoretical methods, using eulerian chains, were developed by Hutchinson to give algorithms for implementing the fragmentation stratagem. Of course, these methods are not used any more, and indeed were used only for a short time before other, more efficient methods were adopted. However, they played an important role in the development of molecular biology.

Overlap data arising from the study of mutations led Cal Tech geneticist Seymour Benzer in the late 1950's to pose a graph-theoretical question that led to the study of interval graphs. Characterizations of interval graphs led Benzer to conclude that his overlap data was consistent with the hypothesis of linear gene structure, and played a basic role in establishing the idea that DNA or RNA molecules can be viewed as linear words over a 4-letter alphabet. Interval graphs continue to be important today in connection with the study of restriction maps of DNA chains. Their generalizations to higher dimensions, in particular the 2-unit sphere graphs, arise in biochemistry in problems of macro-molecular conformation.

Because much of modern molecular biology is concerned with information transmission, it should be no surprise that the mathematical methods that have been most useful in the development of information science are perhaps the most useful in the development of molecular biology. It is no accident that DIMACS was founded as a consortium whose two industrial members, AT Bell Laboratories and Bellcore, are concerned with information transmission.

The fundamental premise of our special year is that some of the most central problems in molecular biology are essentially problems involving the combinatorial and algorithmic questions that DIMACS-type researchers are good at solving. It is a basic scientific objective of the year to create partnerships between biological scientists and discrete mathematicians/theoretical computer scientists so that some very important questions of molecular biology can be properly and precisely formulated as mathematical problems. It is the hope of the special year organizers that, by bringing together some of the world's leading discrete mathematicians/theoretical computer scientists, some major progress can be made on these problems. Inevitably, some of this ``progress'' will be purely of a mathematical nature. However, it is our hope that we can establish and nurture lines of communication and collaboration so that the mathematical results that arise from the special year will then be modified and revised so that many of them will be quickly communicated to biological scientists and so that biological data and biological questions will continue to play a central role in refinements of the mathematics.

In planning special years, DIMACS has had a tradition of maintaining flexibility so that as the special year progresses, the scientific focus can change. Still, it is necessary to set an agenda before the year begins, and we try to do that by planning some major activities that give the year focus. In this special year, there are two major activities of this kind, the workshops and the algorithm implementation challenge. We have chosen the workshop topics in areas with a proven history of biological relevance and discrete mathematical structure. We will use a series of mini-workshops to be more exploratory, leaving many of them until later to be planned.

We are planning five main workshops of three to five days duration. The fifth will be the culmination of our algorithm implementation challenge, and is a bit different from the others. Generically speaking, the goals for each of our other four main workshops are similar: Get biologists and mathematical scientists together to try to establish long-term collaborations, have them work together to identify mathematical and algorithmic problems that are of interest to biology, and get mathematical scientists with existing or potential interest in those problems together to work on them, together with biologists, both at the workshop and afterwards. In order to achieve these goals, we have involved both mathematical scientists and biological scientists as chief organizers or principal advisors of each of the main workshops and the organizing committees for these workshops will consist of both leading mathematical scientists and leading biological scientists. The organizing committees will be or have been in on the planning of the workshops and their members will be participating as speakers and discussants.

The first three workshops have all been chosen to reflect biological areas with existing important underlying combinatorial themes.

• First Workshop: Combinatorial Methods for Mapping and Sequencing DNA Mapping the human genome would require localizing each of its genes and sequencing it would require determining the exact order of the nucleotides making up each gene. Even the intermediate goal of mapping the genome presents significant computational challenges. The workshop will be concerned with algorithmic problems arising from mapping and sequencing, for example problems involving fragment assembly, particularly in the presence of noisy data, and approximate string matching. We expect to have sessions on the double digest and partial digest problems, large-scale DNA physical mapping, DNA sequence assembly, DNA sequencing by hybridization and the shortest superstring problem, new approaches to DNA mapping and sequences, computational support of large sequencing projects (databases, sequence accuracy, automation), and open problems in DNA mapping and sequencing. The topics of the workshop were chosen to be closely tied to the issues being considered in our Algorithm Implementation Challenge. The workshop will be used to kick off the Challenge and we will devote considerable time in the workshop to implementation issues.

• Second Workshop: Sequence Alignment This workshop will deal with string alignment problems in which one wishes to gain information about a newly sequenced piece of DNA by comparing, or aligning it, with a sequence of known function or structure. Detection of similarity between two different molecular sequences has led to the discovery of shared phenomena. (We have already referred to the discovery that the sequence for platelet derived factor, which causes growth in the body, is 87 identical to the sequence for v-sis, a cancer-causing gene, which led to the discovery that v-sis works by stimulating growth.) The quality of a match between two sequences can be determined by a scoring matrix and a charge for introducing gaps in one of the sequences to get a better match, and then a dynamic programming algorithm can be used to determine the largest number of places where two sequences (gaps added) agree. The theory of random graphs can be used to compare two random sequences and predict how good a match one can expect. Work on determining similarity between pairs of sequences can be expanded to work on detecting matches among a whole cluster of such sequences, and then algorithms or heuristics for determining clique-like structures in corresponding graphs can be useful for finding patterns. In this workshop, we will explore all of these ideas. We will investigate dot-matrix methods, global alignments, local alignments and hash coding methods, multiple alignments, measures of aminoacid similarity, and statistical significance of alignments. This workshop will also be closely coordinated with our Algorithm Implementation Challenge.

• Third Workshop: Phylogeny The study of evolution has become rather more quantitative since the recombinant DNA revolution. The phylogeny of a set of species is a model of the evolutionary relationship of that set. Almost all such models in use can be described as trees or tree-like structures that are among the most basic structures of discrete mathematics. The study of phylogenetic tree construction is an important area of biology, with significant statistical and algorithmic components. These two facets play off each other since one is often forced into a tradeoff between the statistically relevant and the computationally tractable. The workshop will be concerned with combinatorial, algorithmic, and statistical aspects of phylogenetic tree construction. We will be interested in finding parsimonious phylogenies (using either Steiner minimal trees or minimal spanning trees), with searches through phylogenetic solution space, with modeling operational taxonomic units as either nodes of trees or both nodes and branches, with cophenetic correlation measures of how well a particular tree matches raw data, and with discrete Fourier methods. We will investigate tree reconstruction based on genome orders, speciation, fossil record and inference about divergence times, non-tree structures like those proposed by Dress and others, and the effects of recombination. We will discuss the methods vthat are available for tree reconstruction with many different sorts of molecular data all at the same time -- a very important practical issue. It is our goal to address strengths and weaknesses of construction methods (distance methods, parsimony, statistical (such as maximum likelihood), and invariants); computational issues involving software and supercomputing applications; and algorithmic issues; and to set an agenda for future work in computational phylogeny.

• Fourth Workshop: HIV Sequence Analysis Although the generic goals of the fourth workshop are similar to those of the first three, this fourth workshop is different in character because it will be devoted to a specific applied topical area rather than a general one. It is concerned with HIV sequence data, and will have several days devoted to presentations of experimental data and a much shorter time devoted to methodological issues. Studies of HIV sequence variation involve global variation, local variation across individuals, tissue or cell tropism, variation of the transmitted virus between sexual partners or mothers and infants, variation of the quasi-species within an infected individual, and covariation of different sites along the virus. Current methods for analyzing the available information are not fully understood. Combinatorial methods have started to play an important role in the analysis and modeling of HIV sequence data. Among the combinatorial issues involved here are the theory of random trees, the development of measures of variability for trees, the study of measures of distance between trees, and the study of statistical confidence in a constructed phylogeny. Thus, techniques investigated in our first three workshops will have some bearing on the subject matter of the fourth workshop.

• Algorithm Implementation Challenge Throughout the special year, we will be emphasizing the development of algorithmic methods for the solution of problems of molecular biology. One of the central activities will be an Algorithm Implementation Challenge, in which researchers will be developing algorithmic methods for a series of benchmark problems developed in conjunction with molecular biologists. All of the specifics of the Challenge have not yet been worked out. However, we have decided that at least part if not all of it will be devoted to problems of DNA sequence determination from shotgun sequence data. There are several features to the shotgun sequencing problem that make it appropriate for the special year. Most important is that it is very relevant to molecular biology and the genome projects. Scores of groups around the world are working on this problem, from both theoretical and applied points of view. Shotgun sequence assembly encompasses aspects of sequence comparison and multiple sequence alignment and is closely related to the first two workshops on Mapping and Sequencing and on Sequence Alignment. Issues of implementation will be stressed at these two workshops, which will be used to lay the groundwork for the Challenge. The goal will be to involve a wide variety of computer scientists in the development of algorithms for carefully defined problems developed between mathematical scientists and biological scientists. Intermediate feedback to algorithm developers will be provided during the course of the year, with comments about both computational aspects and biological relevance.

• Fifth Workshop: Algorithm Implementation Challenge Workshop The ``Challenge'' will culminate in a workshop in September of the second year of our project. Participants will describe their algorithmic approaches to the challenge problems, implementation issues which arose will be debated and discussed, and new directions and further requirements for improvement will be developed.

  While our workshops and algorithm implementation challenge will provide the main scientific focus for the year, a series of one-day mini-workshops will give us the opportunity to explore a variety of additional topics. We do not intend to specify in advance all of the mini-workshop topics. Indeed, we hope that during the course of the planning for the special year and even during the year, we will find that some topics are of special importance and merit a mini-workshop. Mini-workshops can be used to explore topics that might not be as clearly well advanced in the field of computational biology or math/cs topics that are of potential but not proven significance for molecular biology. Also, they can be used to explore molecular biological topics where the payoff to molecular biology of math/cs methods may not be so clear.

• Mini-workshop on Combinatorial Structures in Molecular Biology We are planning on two mini-workshops to be organized by mathematical scientists and to center around mathematical methods. One is on combinatorial structures in molecular biology, and will simply explore a variety of combinatorial questions that relate to or come from molecular biology. Although biologists will be involved in the organization of this mini, it is mostly directed at enticing mathematicians to get involved with the interesting mathematical problems that arise.

• Mini-workshop on Antibody Sequence and Structure A second mini organized around mathematical topics will emphasize combinatorial problem areas in the study of antibody sequence and structure. This mini will be different from the other mathematical one in its emphasis on problems arising from a more narrow area of molecular biological application.

• Mini-workshop on Gene Finding and Gene Prediction A third mini that is already planned emphasizes methods for gene finding and gene prediction. It will be concerned with the increasingly important activity in computational biology of discovering protein-encoding genes in otherwise uncharacterized primary sequence data. This has traditionally been done by discriminating likely coding regions based on a variety of statistical analyses and to a lesser extent by detection of landmark sequences such as splice junctions. The methods to be explored will center around methods of artificial intelligence such as syntactic pattern recognition (which has recently been useful in the problem of assembly of exonic regions into plausible genes) and neural nets. There will also be considerable attention paid to methods of information theory, signal processing, and dynamic programming. This mini will explore methods that are perhaps somewhat peripheral to those described in our summary of the major workshops, but are of increasing interest to those in the computational biology community. We will discuss the most recent efforts to discriminate compositional and signal cues from sequence data and to convey them to integrators, and we will be comparing frameworks and algorithms for gene assembly and combination of evidence.

• Mini-workshop on DNA Topology and Regulation We have planned a mini-workshop on DNA topology and regulation. DNA in living systems is held by other molecules in a sequence of loops, within each of which a topological constraint is imposed. This constraint is the constancy of the linking number, the number of times either strand of the DNA double helix links through the loop formed by the other strand. Enzymes regulate the imposed linking number by actions which involve the transient cutting of one or both strands, followed by strand passage or rotation and reclosure. Changes of linking number modulate virtually all the important biological activities of DNA, including the initiation of gene expression and of DNA replication. Understanding this phenomenon in detail is an essential part of elucidating the content and the functions of the genomic message. The workshop will focus on topologically constrained DNA and study topological and geometric properties of DNA loops and computational strategies to analyze and predict the response of a DNA loop to alterations of its linking number. Mathematical methods to be explored will include Monte Carlo techniques and calculation of partition functions, methods somewhat different than those emphasized in our main workshops, but yet which are becoming increasingly important.

• Mini-workshop on Global Minimization of Nonconvex Energy Functions In addition to the Mini-Workshop on Antibody Sequence and Structure, we are planning several other mini-workshops in the general areas of protein structural analysis and prediction. While these have been a major area of computational biology for years, most approaches to them have used numerical analysis rather than combinatorial methods. These numerical methods have been applied to models of the protein at the atomic level with an attempt to optimize for the minimum energy state. Even within this traditional approach, some optimization methods related to those of discrete mathematics have been finding increasing application. Since in almost all cases the potential energy function is nonconvex and therefore has many local minimizers, the minimization of the potential energy function is a very hard problem. For many years, this has been a field of chemists and physicists, but in recent years, many researchers from optimization and computer science have paid close attention since potential energy minimization problems are ideal as test problems for global minimization algorithms. A mini-workshop on the topic of global minimization of nonconvex energy functions will give us an opportunity to create a dialogue between the theoretical computer scientists developing global minimization algorithms and the structural biologists (some of whom are in the Rutgers Chemistry Department) who are interested in protein folding.

• Mini-workshops on Geometrical Methods for Conformational Modeling and on Sequence-Based Methods for Protein Folding In the last several years, the focus on protein structure and folding has begun to shift from physical modeling to pattern matching. What has happened is that, against initial expectation, the structure of enough proteins has been learned that there are definite patterns that are observable and that have great predictive value both for structure and function. For instance, recently, some researchers have started exploring some subtasks in protein structure prediction from a discrete algorithmic point of view. Investigators have had some initial success on some problems of protein geometry, e.g., three-dimensional surface matching, and in predicting or detecting structure from sequence data, e.g., motif recognition from sequence data. Thus, the study of protein structure is becoming much more the study of sequence and critical conserved features from sequence, and that makes this topic very much a topic where discrete mathematicians can make contributions. These ideas are far from mature and their long-term relevance is unclear. Still, a mini-workshop or two will give us an inexpensive way to explore the area and interchange ideas.

• Possible Mini-workshop on Database Aspects of Biological Data As we have observed earlier, the existence of libraries of DNA and protein sequences allows researchers to attempt a variety of important tasks such as seeking genes that may be similar to a newly determined sequence. There are many potentially complicated and daunting problems raised by biological databases. Access problems, error correction and detection problems, and file management all present issues of traditional importance in theoretical computer science. We are exploring the possibility of a mini-workshop on the topic of database aspects of biological data.

• Possible Mini-workshop on RNA Structure The three dimensional conformation assumed by RNA is crucial to the functioning of the cell. In contrast with proteins, RNA bases pair up to form double stranded helixes, and so much of the three dimensional structure of RNA can be described by the two dimensional information about base pairings. There has therefore been a long tradition of attacking this problem via discrete algorithmic approaches, since the secondary structure is discrete -- a list of paired bases -- rather than continuous -- real coordinates of specific molecules. We are considering a mini-workshop that would explore the traditional dynamic programming approaches to this problem, as well as looking at novel algorithmic approaches.

  We hope that this discussion has provided an overview of the scientific topics upon which the special year will concentrate. Previous DIMACS special years have shown that when we mix different communities of researchers, we don't know exactly where we will end up. However, we hope that we have organized the year, given it sufficient focus, and involved both mathematical and biological communities in its planning, so that we have a good chance of attaining the kinds of successes earlier DIMACS special years have attained.

Return to Special Year in Mathematical Support for Molecular Biology Home Page

Return to DIMACS Home Page