9:00 AM-10:00 AM
Chair: James Oxley, Louisiana State University
Room: Convocation Hall
Discrete mathematics has an important role to play in acquiring and understanding the human genome and the genomes of other organisms, and in inferring the regulatory pathways that govern the functioning of cells. The problems of sequence analysis, sequence assembly, physical mapping, phylogeny construction and analysis of gene expression data are fundamentally combinatorial in nature, although probabilistic considerations also play a role. Often the fundamental issue is the separation of signal from noise. In illustrating these themes our principal examples will be drawn from physical mapping, the process of inferring the positions of markers along a DNA molecule from physical measurements of fragments of the molecule. In particular, we will discuss combinatorial problems arising in radiation hybrid mapping, sequence-tagged-site mapping and restriction mapping. We will also discuss combinatorial problems arising in the analysis of gene expression data. The talk will be accessible to mathematical scientists without a background in molecular biology.
Richard M. Karp
Department of Computer Science
University of Washington