Implicit Hitting Set Problems and Multi-Genome Alignment

Richard Karp
Department of Electrical Engineering and Computer Sciences
UC Berkeley

Wednesday, December 2, 2009
3:45 - 4:45 PM (***Please note the non-standard time***)
Terman Engineering Center, Room 453

Abstract:

A hitting set problem is specified by a finite ground set, a weight for each element, and a collection S of subsets of the ground set. A hitting set is a set having a nonempty intersection with each subset in S. We seek a hitting set of minimum total weight.
An implicit hitting set problem is one in which the collection S is not specified explicitly, but is accessible via a polynomial time membership oracle. Many NP-hard problems can be described as implicit hitting set problems.
We will present a general algorithmic scheme for solving implicit hitting set problems, and then customize the scheme for a problem of optimal alignment of several genomes. The resulting algorithm has been applied to a suite of 4096 problems arising in the alignment of multiple worm genomes. Our method produced provably optimal solutions to 4055 of these problems and provably near-optimal solutions to all the others.
The talk will conclude with some general observations about the construction and validation of heuristic algorithms for NP-hard problems, illustrated by further examples from biology.
This is joint work with Erick Moreno Centeno of the Berkeley IEOR Department.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html