Network Optimization in Bioinformatics and Systems Biology

Mathematical models and algorithmic approaches for solving combinatorial optimization problems from the field of network optimization are known to be essential in telecommunications and the design of transportation and supply chain networks. More recently, it has been discovered that network optimization algorithms are also crucial in the context of bioinformatics and systems biology. Numerous publications in systems biology point out that studying functions, structures and interactions of proteins in combination with networks can provide new insights regarding robust biomarkers, can allow new discoveries regarding protein functions, or testing of new hypothesis regarding their interactions. Network optimization algorithms have also been applied in the analysis of functional modules in protein-protein interaction networks, the discovery of regulatory subnetworks, in revealing hidden components in biological processes, or in detecting transcription factor modules. Motivated by these recent developments, we aim to study several network optimization problems that are among the most challenging ones in these fields and that were not sufficiently studied or understood so far. One of them is essential for the analysis of protein-protein interaction networks, and the other one is an innovative way of combining machine learning and network optimization techniques for extracting signaling pathways or building network-driven classifiers. Existing approaches for these benchmark problems in particular are not able to tackle the supernetworks of very large-scale arising in real world. Thus, in this project we aim at developing the first supernetwork-driven approach in combinatorial optimization that will seamlessly integrate various methodologies from operations research (exact and metaheuristic approaches for network optimization) and computer science (machine learning) into a single mathematical framework. To capture important real world characteristics of the problems to be studied, we will thereby combine techniques of combinatorial, robust optimization and bi-objective optimization. In order to ensure that our algorithms will be able to cope with the enormous size of supernetworks, the tools we will develop will rely on decomposition approaches for mixed integer programming, metaheuristics and parallelization techniques. The obtained results will be important contributions to the fields of combinatorial optimization and bioinformatics.

Our work within this research project focused on developing new and improved models and algorithms for solving well-known difficult combinatorial optimization problems that arise in the research domains of bioinformatics and systems biology. This includes research endeavors like providing new insights into the functions and structures of proteins and their interactions between each other, discovering hidden components in biological processes, or improving our understanding of the evolutionary history of and the relationships between individuals, species and populations. The optimization problems we considered in the course of this project span a wide range of problem families. We first considered problems that deal with identifying subgraphs or subtrees of a certain structure within directed and undirected graphs. The goal is to find the best such subgraph/-tree with respect to an objective function that commonly considers some weights assigned to each node, edge or arc when determining the quality of a solution. This class of problems includes the Steiner tree problem, one of the most well-known NP-hard combinatorial optimization problems, and its variants. We developed sophisticated algorithms for solving these problems that were often able to significantly improve upon the previous state of the art for solving them. We successfully applied these algorithms to a wide range of problem instances, including ones from bioinformatics and systems biology. In our research efforts, we also considered the class of facility location problems. Here, the goal is to place a set of facilities for serving customers and to then assign customers to these facilities in such a way that minimizes the total placement and assignment costs. These problems can be combined with the aforementioned graph problems to form the class of connected facility location problems where the set of selected facilities must be somehow connected by a graph. As for the previous problem family, we developed optimization algorithms that were able to improve upon the previous state of the art for solving them. We furthermore investigated the class of bilevel optimization problems, an exceptionally challenging type of optimization problem where one decision maker must consider the behavior of a second, independent agent (who also acts optimally in their own self interest) when making their decisions. As before, we developed new state-of-the-art optimization procedures for solving this class of problems. We successfully presented our research at various top-tier conferences in the field of operations research and published a number of articles in high-quality journals. We were also able to further existing and to establish new international collaborations with researchers from Chile, Germany, Italy, and Spain. Additionally, some of the software we developed over the course of this project was made publicly available to the research community in binary or source code form.