University of Illinois at Urbana-Champaign
Department of Mathematics
Mathematics in Science & Society
Spring 1999
Orange & Blue Bar

4:00 p.m., Tuesday, May 4, 1999, 245 Altgeld Hall

Orange & Blue Bar

Computation as a Tool for Understanding Genomes

Richard M. Karp
Professor of Computer Science and Engineering
University of Washington, Seattle

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. Knowing the genome of an organism is a crucial aid in determining how it functions at the molecular level, and in tracking down the relation between genetic variation and disease. The genomes of yeast and several microorganisms have been sequenced, and the complete sequencing of the human genome is on the horizon.

Large-scale computation is a crucial tool in molecular biology and genomics, both for sequencing a genome and for interpreting it once it has been sequenced. Applications of combinatorial optimization, pattern recognition and computational learning theory are abundant. The speaker will describe some of these applications, drawing his examples from the areas of sequencing and mapping. He will then lay out an agenda for future research, based on DNA arrays, a new experimental tool that is crucial for understanding how genes correlate with disease and for elucidating the control mechanisms that determine how genes get turned on and off.


Biography

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 (ICSI)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. This summer he will return to Berkeley as a University Professor. His principal appointment will be in Computer Science, and he will also hold appointments in Mathematics and Bioengineering. In addition, he will again be a research scientist at ICSI.

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 Harvey Prize (Technion), the Turing Award (ACM), the Centennial Medal (Harvard University) 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.