Carl Kingsford
Many
optimization problems in biology can be modeled as integer programming
problems. While general integer programming is a hard computational problem,
many real-world problems do not obey this worst-case analysis. Modern linear
and integer programming solvers often can quickly find solutions to real
problems with hundreds of thousands of variables.
After
introducing integer programming, I will present integer programming approaches
for two biological problems. The first is a problem in protein structure design
and prediction in which we want to find the lowest energy orientation of side
chains hanging off a fixed backbone. The second is the problem of finding where
transcription factor proteins bind to DNA.
Various
parts of the presented work will be joint work with Mona Singh, Bernard Chazelle, and Elena Zaslavsky.