Netzwerkoptimierung in Bioinformatik und Systembiologie

Mathematische Modelle und algorithmische Verfahren zur Lösungvonkombinatorischen Optimierungsproblemen aus dem Bereich der Netzwerkoptimierung sind essentiell im Design von Telekommunikations-, Transport- oder Supply-chain-Netzwerken. In den letzten Jahren wurde auch die hohe Relevanz von Netzwerkoptimierungsalgorithmen in der Bioinformatik und der Systembiologie erkannt. Viele Publikationen im Gebiet der Systembiologie zeigen, dass die Untersuchung von Funktionen und Strukturen von Proteinen sowie deren Wechselwirkungen unter gleichzeitiger Berücksichtigung von Netzwerkaspekten neue Einsichten hinsichtlich robusterer Biomarker, neue Erkenntnisse in Bezug auf Proteinfunktionen, sowie das Testen neuer Hypothesen bezüglicher derer Interaktionen, erlaubt. Netzwerkoptimierungsalgorithmen wurden auch in der Analyse von funktionalen Modulen in Protein-Protein-Interaktionsnetzwerken, der Erforschung von Genregulationsnetzwerken, zur Erkennung von versteckten Komponenten in biologischen Prozessen, sowie zur Entdeckung von Transkriptionsfaktormodulen verwendet. Motiviert durch diese Entwicklungen werden wir zwei Netzwerkoptimierungsprobleme (und ihre Varianten), welche zu den herausforderndsten in diesen Gebieten zählen und bisher nicht ausreichend untersucht oder gelöst wurden, studieren. Eines davon ist in der Analyse von Protein-Protein-Interaktionsnetzwerken wichtig, das zweite stellt eine innovative Methode zur Kombination von Machine Learning und Techniken der Netzwerkoptimierung zur Extraktion von Signaltransduktionswegen oder zum Generieren von Netzwerk- basierten Klassifikatoren dar. Existierende Verfahren für diese Probleme können nicht mit den in den enorm großen Supernetzwerken, welche in der Praxis auftreten, umgehen. In diesem Projekt werden wir deshalb den ersten Supernetzwerk-getriebenen Ansatz im Gebiet der kombinatorischen Optimierung entwickeln, welcher die nahtlose Integration verschiedener methodologischer Ansätze aus den Bereichen Operations Research (exakte und heuristische Methoden für Netzwerkoptimierung) und Informatik (Machine Learning) in ein mathematisches Framework erlaubt. Um dabei wichtige Aspekte der ausgewählten Benchmarkprobleme berücksichtigen zu können werden wir Methoden der kombinatorischen Optimierung, der robusten Optimierung und der Optimierung mit mehreren Zielfunktionen, kombinieren. Um mit der enormen Größe von Supernetzwerken umgehenzu können,werden dievon uns entwickeltenVerfahren auf Dekompositionsverfahren aus dem Gebiet der gemischtganzzahligen Programmierung, Metaheuristiken und Parallelisierung beruhen. Unsere Ergebnisse sind wichtige Beiträge in den Bereichen kombinatorische Optimierung und Bioinformatik.

Ziel unserer Arbeit im Rahmen dieses Forschunsprojekt war es, neue bzw. bessere Modelle und Algorithmen zur Lösung bekannter schwieriger kombinatorischer Optimierungsprobleme in den Bereichen der Bioinformatik und der Systembiologie zu entwickeln. Hierzu gehören etwa das Gewinnen neue Einsichten in Funktion und Struktur von Proteinen und deren Interaktionen, das Finden verborgener Komponenten in biologischen Prozessen, sowie die Verbesserung unseres Verständnisses der evolutionären Geschichte und der Beziehungen zwischen Individuen, Spezies und Populationen. Wir haben uns im Laufe dieses Projekts mit einer großen Bandbreite dieser Problemfamilien befasst. Die erste befasst sich mit dem Finden von Subgraphen oder Subbäumen mit spezieller Struktur in gerichteten und ungerichteten Graphen. Das Ziel ist hierbei, den besten dieser Subgraphen/-bäume zu finden, wobei die Lösungsqualität anhand einer Zielfunktion bestimmt wird, die häufig Knoten- und Kantengewichte einbezieht. Ein bekannter Vertreter dieser Problemfamilie ist das Steiner tree problem und seine Varianten. Die von uns entwickelten Algorithmen zur Lösung dieser Probleme stellten oft eine signifikante Verbesserung gegenüber dem bisherigen Stand der Technik dar und wurden von uns zur Lösung einer Vielzahl an Probleminstanzen (aus den Bereichen Bioinformatik, Systembiologie und anderen) verwendet. Die zweite von uns untersuchte Problemfamilie beschäftigt sich mit facility location. Ziel bei dieser Problemklasse ist es, eine Menge an Standorten zur Versorgung von Kunden auszuwählen und die Kunden diesen gewählten Standorten so zuzuweisen, dass die Gesamtkosten für Standorterrichtung und Zuweisung minimal ist. Diese Probleme können auch mit den vorher erwähnten Graphenproblemen verbunden werden, was zur Problemklasse der connected facility location problems führt. Auch für diese Problemfamilie konnten wir neue Algorithmen entwickeln und so den Stand der Technik verbessern. Die dritte und letzte Problemfamilie, die von uns untersucht wurde, beschäftigt sich mit sogenannten bilevel optimization problems. Bei dieser außergewöhnlich schwierig zu lösenden Art von Optimierungsproblemen muss das Verhalten eines zweiten Akteurs, der unabhängig und optimal im eigenen Interesse handelt, in den Entscheidungsprozess mit einbezogen werden. Auch hierfür ist es uns gelungen, den Stand der Technik durch von uns entwickelte Algorithmen zu verbessern. Die Ergebnisse unserer Arbeit wurden mehrfach bei erstklassigen wissenschaftlichen Konferenzen präsentiert und in Fachzeitschriften höchster Qualität veröffentlicht. Weiters konnten wir Kooperationen mit Forscherinnen und Forschern aus Chile, Deutschland, Italien und Spanien herstellen und vertiefen. Die von uns entwickelten Algorithmen sind teilweise online in Form von Quellcode oder als fertige Anwendung für andere Forscherinnen und Forscher verfügbar.