### CIS Distinguished Lecture Series, Sep 28, 2011, 11:00AM - 12:00PM, Walk Auditorium, Ritter Hall

### Heuristic Algorithms in Computational Molecular Biology and Genetics

### Richard M. Karp, University of California, Berkeley

In many practical situations heuristic algorithms reliably give
satisfactory solutions to real-life instances of optimization
problems, despite evidence from computational complexity theory that
the problems are intractable in general. Our long-term goal is to
contribute to an understanding of this seeming contradiction, and to
put the construction of heuristic algorithms on a firmer footing. In
particular, we are interested in methods for tuning and validating
heuristic algorithms by testing them on a training set of "typical"
instances. As a step in this direction we describe the evolution and
validation of three heuristic algorithms motivated by problems in
computational molecular biology and genetics:

(1) A generic algorithm for the class of implicit hitting set
problems, which includes feedback vertex set and feedback edge set
problems, the max-cut problem, the Steiner tree problem, the problem
of finding a maximum feasible subset of a set of linear inequalities,
matroid intersection problems and a problem of global genome alignment
(joint work with Erick Moreno Centeno).

(2) The Colorful Subgraph Problem: given a graph in which each vertex
is assigned a color from a set S, find the smallest connected subgraph
containing at least one vertex of each color in S. (joint work with
Shuai Li)

(3) The problem of clustering the vertices of a graph into small
near-cliques. (joint work with Shuai Li).

The speaker will briefly explain the biological motivation for each problem.

Richard M. Karp was born in Boston, Massachusetts on January 3, 1935.
He attended Boston Latin School and Harvard University, receiving the
Ph.D. in 1959. From 1959 to 1968 he was a member of the Mathematical
Sciences Department at IBM Research. From 1968 to 1994 and from 1999
to the present he has been a Professor at the University of
California, Berkeley, where he held the Class of 1939 Chair and is
currently a University Professor. From 1988 to 1995 and 1999 to the
present he has been a Research Scientist at the International Computer
Science Institute in Berkeley. From 1995 to 1999 he was a Professor at
the University of Washington. During the 1985-86 academic year he was
the co-organizer of a Computational Complexity Year at the
Mathematical Sciences Research Institute in Berkeley. During the
1999-2000 academic year he was the Hewlett-Packard Visiting Professor
at the Mathematical Sciences Research Institute.

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. He has supervised thirty-nine Ph.D. dissertations.

His honors and awards include: U.S. National Medal of Science, Turing
Award, Kyoto Prize, Fulkerson Prize, Harvey Prize (Technion),
Centennial Medal (Harvard), Dickson Prize (Carnegie Mellon),
Lanchester Prize, Von Neumann Theory Prize, Von Neumann Lectureship,
Distinguished Teaching Award (Berkeley), Faculty Research Lecturer
(Berkeley), Miller Research Professor (Berkeley), Babbage Prize and
ten 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.