Computational Discovery of Genetic Regulatory Networks

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 some recent investigations along these lines, emphasizing how new biological insights can be gained by finding patterns in biological databases using combinatorial algorithms and statistical analyses. We will focus on two areas:

1) The discovery of 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. We also give methods for finding regulatory modules. These are sets of transcription factors that bind to the same regions of DNA and function collectively to enhance or inhibit the transcription of genes.

Biography – Richard M. Karp attended Boston Latin School and Harvard University, receiving the Ph.D. in 1959. He is currently University Professor at the University of California- Berkeley.

The unifying theme in Karp’s work has been the study of combinatorial algorithms. His 1972 paper “Reducibility Among Combinatorial Problems’ showed that many of the most commonly studied combinatorial problems are NP-complete, and hence likely to be intractable. Much of his work has concerned parallel algorithms, the probabilistic analysis of combinatorial optimization algorithms and the construction of randomized algorithms for combinatorial problems. His current activities center around algorithmic methods in genomics and computer networking.

His honors and awards include: U.S. National Medal of Science, Turing Award, Fulkerson Prize, Harvey Prize (Technion), Centennial Medal (Harvard), Lanchester Prize, Von Neumann Theory Prize, Von Neumann Lectureship, Distinguished Teaching Award (Berkeley), Faculty Research Lecturer (Berkeley), Miller Research Professor (Berkeley), Babbage Prize and eight honorary degrees. He is a member of the U.S. National Academies of Sciences and Engineering, the American Philosophical Society and the French Academy of Sciences, and a Fellow of the American Academy of Arts and Sciences, the American Association for the Advancement of Science, the Association for Computing Machinery and the Institute for Operations Research and Management Science.