Department of Molecular Biotechnology
University of Washington, Seattle, WA 98195
Maps showing the coordinates of restriction sites (specific strings of nucleotides recognized by site-specific restriction enzymes) are simple, unbranched, one-dimensional data structures. Good experimental methods exist for over- determining these maps by measuring the sizes of the DNA fragments produced when DNA is cut by restriction enzymes at each occurrence-or a subset of the occurrences-of a particular restriction site. At first view, the problem of developing computer- based map- construction procedures is straightforward, although the combinatoric complexity of common variants of the problem requires attention to algorithmic detail. However, 25 years after the discovery of restriction enzymes and 20 years after "restriction maps" became ubiquitous tools in molecular biology, most restriction maps are still constructed by hand with notoriously unreliable results. This talk will examine the history of efforts to make computer-based map construction routine and also look to the future, where large-scale applications of restriction mapping in the Human Genome Project are driving continuing efforts to develop robust computer-based procedures. The critical role of close interplay between experimental and algorithmic design will be emphasized.