Mixed Integer Linear Programming and its applications in bioinformatics

Location: 
HS03
Organizers: 

Marcus Oswald⁽¹, ²⁾ and Rainer König⁽¹, ²⁾
1 Integrated Research and Treatment Center, Center for Sepsis Control and Care (CSCC), Jena University Hospital, Germany
2 Network Modeling, Leibniz Institute for Natural Product Research and Infection Biology - Hans Knöll Institute Jena, Germany.

Description of the tutorial:

Mixed Integer Linear Programming is a versatile tool from Discrete Optimization. It is all about solving so-called Mixed Linear Integer Programs (MILP). Vast numbers of algorithmic problems from all kinds of application areas can be modeled as MILPs. More importantly, over the last decade or two, the solvers, the software which solve MILPs, have progressed so considerably that Integer Programming is often superior to developing dedicated algorithms. Mixed Integer Linear Programming has many applications, most prominently in optimizing time tables and the traveling salesman problem. The beauty of this optimization strategy is that it can employ a given list of rules or constraints considerably limiting the search space on top of which linear and discrete optimization is performed. In biochemistry, stoichiometric equations have been derived for several thousand metabolites and reactions since the last 50 years restricting the space of possible metabolic fluxes when assuming steady state, leading to Flux Balance Analysis as a MILP application (Orth et al, 2010). The instructors of the course used MILP to optimize two dimensional arrangements of cellular networks (Schramm et al, 2010), to infer gene regulatory interactions (Schacht et al, 2014, Poos et al, 2016), select mutually maximally distant reference genes in a gene regulatory network (Suratanee et al, 2014) and to combine classification problems (Saraiva et al 2017). Others used MILP based Steiner trees to infer gene regulatory modules in cellular networks (Beisser et al, 2012) or parsimonious regulation pathways
(Shachar et al, 2008). Within the tutorial, we will give a short introduction into the principle idea of MILP and will explain some of the above mentioned applications in bioinformatics. In a second part of the course, we will give a tutorial on Mixed Integer Linear Programming using the participants’ own laptops and an R and (academically free) Gurobi (solver) installation.

Software/Data Requirements: 

The participants need their own laptop with either Linux, MacOS or Windows running. The following
software should be installed: Current versions of R and R-Studio including the R-packages topGO and slam. In addition they need an installation of Gurobi 8.0.0 (www.gurobi.com). Gurobi installations and licenses are free for academic purposes but need registration. Non-academic participants please contact the instructors in advance.

References: 

Beisser D, Brunkhorst S, Dandekar T, Klau GW, Dittrich MT, Muller T (2012) Robustness and accuracy of functional modules in integrated network analysis. Bioinformatics 28: 1887-1894

Jerby L, Shlomi T, Ruppin E (2010) Computational reconstruction of tissue-specific metabolic models:

application to human liver metabolism. Molecular systems biology 6: 401

Lewis NE, Schramm G, Bordbar A, Schellenberger J, Andersen MP, Cheng JK, Patel N, Yee A, Lewis RA, Eils R, Konig R, Palsson BO (2010) Large-scale in silico modeling of metabolic interactions between cell types in the human brain. Nature biotechnology 28: 1279-1285

Orth JD, Thiele I, Palsson BO (2010) What is flux balance analysis? Nature biotechnology 28: 245-248

Piro RM, Wiesberg S, Schramm G, Rebel N, Oswald M, Eils R, Reinelt G, Konig R (2014) Network topology-based detection of differential gene regulation and regulatory switches in cell metabolism and signaling. BMC systems biology 8: 56

Schacht T, Oswald M, Eils R, Eichmuller SB, Konig R (2014) Estimating the activity of transcription factors by the effect on their target genes. Bioinformatics 30: i401-407

Schramm G, Wiesberg S, Diessl N, Kranz AL, Sagulenko V, Oswald M, Reinelt G, Westermann F, Eils R, Konig R (2010) PathWave: discovering patterns of differentially regulated enzymes in metabolic pathways. Bioinformatics 26: 1225-1231

Shachar R, Ungar L, Kupiec M, Ruppin E, Sharan R (2008) A systems-level approach to mapping the telomere length maintenance gene circuitry. Molecular systems biology 4: 172

Suratanee A, Schaefer MH, Betts MJ, Soons Z, Mannsperger H, Harder N, Oswald M, Gipp M, Ramminger E, Marcus G, Manner R, Rohr K, Wanker E, Russell RB, Andrade-Navarro MA, Eils R, Konig R (2014) Characterizing protein interactions employing a genome-wide siRNA cellular phenotyping screen. PloS computational biology 10: e1003814

Poos, A. M. et al. Mixed Integer Linear Programming based machine learning approach identifies regulators of telomerase in yeast. Nucleic acids research, doi:10.1093/nar/gkw111 (2016). Saraiva et al. Combination of classifiers identifies fungal-specific activation of lysosome genes in human monocytes Front. Microbiol, 8:2366 (2017).