SCS DISTINGUISHED LECTURE SERIES

Dr. Richard M. Karp
Professor of Computer Science & Engineering
and Adjunct Professor of Molecular Biotechnology
University of Washington

Combinatorial Optimization as a Tool for Molecular Biology

Thursday, 11 September 1997

4:00 pm, Wean Hall 7500

3:45 pm - Refreshments Outside Wean Hall 7500

ABSTRACT
The genome of an organism can be viewed as the source code for the programs that control the chemical processes of the cell.The genome also contains the hereditary endowment that an organism passes to its offspring. Large-scale computation is a crucial tool, both for sequencing a genome and for interpreting it once it has been sequenced. Applications of combinatorial optimization, statistical analysis, pattern recognition and computational learning are abundant. The speaker will describe some of these applications, with physical mapping, a key step in genome sequencing, as the principal example. He will then describe the important new technology of DNA arrays and describe some of the associated computational problems.

SPEAKER BIO
Richard M. Karp was born in Boston, Massachusetts in 1935 and was educated at the Boston Latin School and Harvard University, where he received the Ph.D. in Applied Mathematics in 1959. From 1959 to 1968 he was a member of the Mathematical Sciences Department at the IBM Thomas J. Watson Research Center. From 1968 to 1994 he was a Professor of Computer Science, Mathematics and Operations Research at the University of California, Berkeley. From 1988 to 1995 he was also associated with the International Computer Science Institute in Berkeley. In 1995 he became a Professor of Computer Science and Engineering and an Adjunct Professor of Molecular Biotechnology at the University of Washington. The unifying theme in Karp's work has been the study of combinatorial algorithms. His most significant work is the 1972 paper ``Reducibility Among Combinatorial Problems,'' which shows that many of the most commonly studied combinatorial problems are disguised versions of a single underlying problem, and thus are all of essentially the same computational complexity. Much of his subsequent work has concerned the development of parallel algorithms, the probabilistic analysis of combinatorial optimization problems,and the construction of randomized algorithms for combinatorial problems. His current research is concerned with strategies for sequencing the human genome, the physical mapping of large DNA molecules, the analysis of gene expression data, and other combinatorial problems arising in molecular biology. Karp has received the U.S. National Medal of Science, the Turing Award (ACM) the Fulkerson Prize(AMS and Math. Programming Society), the von Neumann Theory Prize(ORSA-TIMS), the Lanchester Prize (ORSA) the von Neumann Lectureship (SIAM) and the Distinguished Teaching Award (Berkeley). He is a member of the National Academy of Sciences, the National Academy of Engineering and the American Philosophical Society, as well as a Fellow of the American Academy of Arts and Sciences. He holds four honorary degrees.


SCS Distinguished Lecture Schedule
SCS Calendar of Events