{"id":696,"date":"2017-03-24T07:57:41","date_gmt":"2017-03-24T07:57:41","guid":{"rendered":"http:\/\/math.utu.fi\/cie2017\/?page_id=696"},"modified":"2017-03-24T07:57:41","modified_gmt":"2017-03-24T07:57:41","slug":"dan-gusfield","status":"publish","type":"page","link":"https:\/\/math.utu.fi\/cie2017\/dan-gusfield\/","title":{"rendered":"Dan Gusfield"},"content":{"rendered":"

Tutorial on Integer Linear Programming in Computational Biology<\/em><\/h4>\n
Abstract:<\/h6>\n

Integer Linear Programming is a versatile modeling and optimization technique that was developed for complex planning and operational decision making.\u00a0 However, it is increasingly used in computational biology in non-traditional ways, most importantly and\u00a0 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.\u00a0 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.\u00a0 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.\u00a0 Then, for any given problem instance, highly engineered ILP solvers can be used to solve the ILP formulation.\u00a0 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.\u00a0 The effectiveness of the best modern ILP solvers on problem instances of importance in biology opens huge opportunities —\u00a0 broad exploitation of integer programming could have a truly transformative effect on computation in biology and perhaps medicine.<\/em><\/p>\n

The goal of the tutorial is to introduce and detail *modeling* and *solving* of real problems in computational biology using integer linear programming.\u00a0 This is in contrast to the goal of explaining the theory of linear programming or how integer programming or linear programming solvers work. We will use a commercial ILP solver, from Gurobi Optimization, to solve specific ILPs that we formulate. The tutorial starts with an introduction for people with no prior background in linear programming or integer linear programming.\u00a0We will discuss several problems, models and ILP solutions selected from network biology, phylogenetics, RNA and protein folding, clustering, SNP haplotyping, DNA sequence assembly, genome-wide association studies, sequence analysis, protein function analysis, etc.\u00a0 The ILP formulations will illustrate many different ILP “idioms” and their use.\u00a0 Finally, after studying several ILP examples in computational biology, we will discuss what is distinctive about the use of integer programming in computational biology, compared to more traditional uses of integer programming.<\/em><\/p>\n

Educational material will be provided. If you want some hands on experience, please install the Gurobi ILP solver (free for academics and researchers) on your laptop before the tutorial.\u00a0 <\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

Tutorial on Integer Linear Programming in Computational Biology Abstract: Integer Linear Programming is a versatile modeling and optimization technique that was developed for complex planning and operational decision making.\u00a0 However, it is increasingly used in computational biology in non-traditional ways, most importantly and\u00a0 inventively as a computational tool and language to model and study biological … Continue reading Dan Gusfield<\/span> →<\/span><\/a><\/p>\n","protected":false},"author":22,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-696","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/math.utu.fi\/cie2017\/wp-json\/wp\/v2\/pages\/696","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/math.utu.fi\/cie2017\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/math.utu.fi\/cie2017\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/math.utu.fi\/cie2017\/wp-json\/wp\/v2\/users\/22"}],"replies":[{"embeddable":true,"href":"https:\/\/math.utu.fi\/cie2017\/wp-json\/wp\/v2\/comments?post=696"}],"version-history":[{"count":5,"href":"https:\/\/math.utu.fi\/cie2017\/wp-json\/wp\/v2\/pages\/696\/revisions"}],"predecessor-version":[{"id":924,"href":"https:\/\/math.utu.fi\/cie2017\/wp-json\/wp\/v2\/pages\/696\/revisions\/924"}],"wp:attachment":[{"href":"https:\/\/math.utu.fi\/cie2017\/wp-json\/wp\/v2\/media?parent=696"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}