LARGE-SCALE PHYSICAL GENOME MAPPING Anthony Bonner University of Toronto (Visiting Penn) A major step in understanding the genome of an organism is constructing a physical map, that is, an assignment of DNA fragments to their locations on the genome. Building complete maps of large genomes often requires integrating many kinds of experimental data, each with its own forms of noise, experimental error and anomalies, and with subtle relationships between the different forms of data. Unfortunately, the quantity and complexity of the data greatly complicate the map-assembly process, limiting the effectiveness and flexibility of many map-assembly algorithms. This talk outlines the biology of physical genome mapping, the computational problems involved, and our approach to solving them. This approach is based on abstracting the experimental data as a graph. Intuitively, each node in the graph represents a point on the genome, and each edge represents evidence that two points are close together on a chromosome. Many forms of physical mapping data can be abstracted in this way. The result is that genome map assembly becomes largely a problem of graph manipulation. Graph algorithms and graph visualization play key roles in our approach to the map-assembly problem. This talk represents joint work between researchers at the University of Toronto and the Jackson Laboratory.