Colloquium Speaker

Speaker:		John Kececioglu Department of Computer Science The University of Georgia
Topic:		Computing Optimal Maps of Chromosomes By Branch-and-Cut
Date:		Thursday, March 9, 2000
Time:		11:00 AM
Place:		Gould-Simpson, Room 701

ABSTRACT

One of the fundamental tasks in computational biology is physical mapping of chromosomes. A physical map specifies the order and relative location of a set of features along a linear chromosome. Maps are reconstructed from indirect observations that contain error; all known formulations of the reconstruction problem are NP-complete. To date the best approaches for reconstructing such maps from the most common type of data, so-called hybridization experiments, have relied on heuristics such as simulated annealing that attempt to find good maps but offer no performance guarantees.

We introduce a new combinatorial formulation of physical mapping from hybridization data. The formulation captures the problem of finding a maximum-likelihood reconstruction in the presence of false positive and false negative hybridization errors. We show that this formulation in turn can be expressed as a concise integer linear-programming problem which we solve using a relatively new technique from combinatorial optimization known as branch-and-cut. Experiments with a system we implemented applying our branch-and-cut algorithm to data from the fungal genome mapping project show that we can solve many instances to provable optimality in 30 minutes of computation, even though computing an optimal map in our formulation is NP-complete. Furthermore, the maps we compute are of significantly higher quality than previously possible.