Richard M. Karp is University Professor at the University of California at Berkeley, and one of the world's pre-eminent computer scientists. In 1985, he was awarded Computer Science's highest award, the ACM Turing Award, for his seminal work on reductions between NP-complete problems. In 1996 he received the National Medal of Science, the nation's highest scientific award bestowed annually by the President of the United States. He is a member of both the National Academy of Sciences and the National Academy of Engineering.

Abstract

Great successes in the sequencing of genomes and the identification of genes have advanced the field of genomics to a new level in which we have identified the players (primarily genes and proteins) and now wish to determine how they interact to form molecular machines and regulatory networks that carry out the functions of living cells. We shall describe several recent investigations along these lines. The talk will emphasize combinatorial algorithms, and all necessary biological background will be provided.

(1) We present algorithms for discovering protein complexes and regulatory pathways that are conserved in evolution, using protein sequence data and protein-protein interaction data for two or more organisms.

(2) The first step in the production of proteins is the transcription of the associated genes into messenger RNA. This process is regulated by proteins called transcription factors that bind to DNA near the genes. We present a new approach to the recognition of transcription-factor binding
sites, based on the principle that transcription factors within the same family of proteins have common features.

(3) We present an algorithm for finding sets of transcription factors that often bind to the same genomic regions and collectively enhance or inhibit the transcription of the corresponding genes.

(4) We present algorithm for minimizing the number of gene perturbation experiments required to reconstruct signal transduction pathways whose regulatory structures can be described within the mathematical framework of chain functions.

Back to Distinguished Lecture Series - Fall 2004 / Spring 2005 Schedule