Spring 2016

Integer Linear Programming in Computational Biology

May 9, 2016

Add to Calendar


Dan Gusfield (UC Davis)

Location: Calvin Lab Room 116 

Confirmed Speakers:
Hu Ding (Michigan State University)
Mohammed El-Kebir (Brown University)
Yelena Frid (UC Davis)
Dan Gusfield (UC Davis)
Matthias Koeppe (UC Davis)
Julia Matsieva (UC Davis)
Ron Shamir (Tel-Aviv University)
Roded Sharan (Tel-Aviv University)
Fabio Vandin (University of Padova)
Yufeng Wu (University of Connecticut)

Integer Linear Programming is a versatile modeling and optimization technique that was developed for complex planning and operational decision making. However, it is increasingly used in computational biology in non-traditional ways, most importantly and inventively as a computational tool and language to model and study biological phenomena, to analyze biological data, and to extract biological insight from the models and the data. Integer linear programming is often very effective in solving *instances* of biological problems on realistic data of current importance, even for hard computational problems that lack a worst-case efficient solution method. Moreover, even if a worst-case efficient algorithm is possible for a particular problem, the time and effort needed to find and implement such an algorithm is typically much greater than the time and effort needed to find and implement an ILP formulation for the problem. Then, for any given problem instance, highly engineered ILP solvers can be used to solve the ILP formulation. The improvement of the best ILP solvers has been spectacular, with an estimate that (combined with faster computers) benchmark ILP problems can now be solved 200-billion times faster than twenty-five years ago.  The effectiveness of the best modern ILP solvers on problem instances of importance in biology opens huge opportunities -- broad exploitation of integer programming could have a truly transformative effect on computation in biology and perhaps medicine.  

This day-long workshop will start with a tutorial on ILP to introduce the area to people with no prior background in ILP, and to outline what is distinctive about ILP uses in computational biology. Then researchers will talk about past and current work, illustrating the wide range of applications of ILP in computational biology, and to explain formulation and solution techniques, experimental results, and open problems. Talks will range in length from 20 minutes to one hour. 

Please write to gusfield [at] cs [dot] ucdavis [dot] edu (Dan Gusfield) if you are interested in speaking.