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.