Optimizing Global Network Alignment in Protein-Protein Interaction Networks

Abstract

Global Network Alignment in Protein-Protein Interaction Networks is an NP-complete problem due to the contradicting nature of its biological and topological alignment objectives. There have been several aligners developed focusing on various priorities and objectives of the problem. However, none of these alignment heuristics provide exact solutions, despite the fact that they achieve problem objectives up to a certain extent. For this reason, the research question of uniting stronger aspects of dissimilar Network Alignment heuristics is quite promising. In this thesis, it is aimed to improve the methods to scan the search space of this problem by managing the simultaneous use of several heuristics and two novel population-based meta-heuristic methods are proposed for this purpose. The first one of these methods (SUMONA) is a supervised genetic algorithm approach that is an extension to the computationally demanding multi-objective memetic algorithm called OptNetAlign. This method intends to accelerate and guide the alignment process by modifying the crossing-over mechanism of the genetic algorithm with inputs from other aligners/heuristics while preventing premature convergence by randomizing the usage of these inputs. The algorithm is based on a generic procedure that generates several alignments with changing heuristics and input parameters, classifies the generated alignments, establishes a randomized alignment selection mechanism from the classified alignments for cross-over and finally adjusts global and local search parameters. It is possible to achieve better running time performance, prioritize certain objectives upon others and also optimize the secondary objectives with this method. The second method (PERSONA) is a particle swarm inspired collaborative approach that orchestrates several aligners to share their partial solutions continuously while they progress. These aligners jointly constitute a particle swarm that searches for multi-objective solutions of the alignment problem in a reactive actor environment. Within the swarm, the leading or prominent actors send the stronger portion of their solution as a subgraph to other actors and receive the stronger subgraphs of the counter party back upon evaluation of those partial solutions. The individual alignment heuristics were also developed within the scope of the same research and they were implemented based on alternatives such as seed-and-extend approaches with various centrality and sequence seeds, cluster mapping approach and node similarity prioritization. Both the population-based meta-heuristic tasks and the individual heuristic tasks were implemented in a non-deterministic fashion in order to improve flexibility and preventing to be trapped in locally optimal solutions. The results achieved with this method are remarkably optimized and balanced for both topological and node similarity objectives.

Die ‘Globale Netzwerkausrichtung’ in Protein-Protein-Interaktionsnetzwerken ist ein NP- vollständiges Problem aufgrund der widersprüchlichen Natur der biologischen und topol- ogischen Ausrichtungsziele. Es wurden bereits mehrere Aligner entwickelt, die sich auf verschiedene Prioritäten und Ziele des Problems konzentrieren. Keine dieser Alignment- Heuristiken liefert jedoch exakte Lösungen, obwohl sie die Problemziele bis zu einem gewissen Grad erreichen. Aus diesem Grund ist die Forschungsfrage, wie man stärkere Aspekte von unterschiedlichen Network Alignment Heuristiken vereinen kann, sehr vielver- sprechend. In dieser Arbeit wird das Ziel verfolgt, die Methoden zum Durchsuchen des Suchraumes dieses Problems zu verbessern, indem die gleichzeitige Verwendung mehrerer Heuristiken verwaltet wird, und zu diesem Zweck werden zwei neuartige populationsbasierte meta-heuristische Methoden vorgeschlagen. Bei der ersten dieser Methoden (SUMONA) handelt es sich um einen überwachten genetis- chen Algorithmus, der eine Erweiterung des rechenintensiven memetischen Multi-Zielsetzung algorithmus OptNetAlign darstellt. Diese Methode zielt darauf ab, den Ausrichtungsprozess zu beschleunigen und zu leiten, indem der Crossing-Over-Mechanismus des genetischen Algorithmus mit Eingaben von anderen Alignern/Heuristiken modifiziert wird. Der Algo- rithmus basiert auf einer generischen Prozedur, die mehrere Alignments mit wechselnden Heuristiken und Eingabeparametern generiert, die generierten Alignments klassifiziert, einen randomisierten Alignment-Auswahlmechanismus aus den klassifizierten Alignments für das Cross-over etabliert und schließlich globale und lokale Suchparameter anpasst. Mit dieser Methode ist es möglich, eine bessere Laufzeitleistung zu erzielen, bestimmte Ziele gegenüber anderen zu priorisieren und auch die sekundären Ziele zu optimieren. Die zweite Methode (PERSONA) ist ein von einem Partikelschwarm inspirierter kollabora- tiver Ansatz, der mehrere Aligner so orchestriert, dass sie ihre Teillösungen kontinuierlich austauschen, während sie Fortschritte machen. Diese Aligner bilden gemeinsam einen Partikelschwarm, der in einer reaktiven Akteur-Umgebung nach multiobjectiven Lösungen für das Alignment-Problem sucht. Innerhalb des Schwarms senden die führenden oder prominenten Akteure den stärkeren Teil ihrer Lösung als Teilgraphen an andere Akteure und erhalten nach Auswertung dieser Teillösungen die stärkeren Teilgraphen der Gegenpartei zurück. Die individuellen Alignment-Heuristiken wurden ebenfalls im Rahmen dersel- ben Forschung entwickelt und auf der Grundlage von Alternativen wie Seed-and-Extend- Ansätzen mit verschiedenen Zentralitäts- und Sequenz-Seeds, Cluster-Mapping-Ansatz und Knotenähnlichkeitspriorisierung implementiert. Sowohl die populationsbasierten meta- heuristischen Aufgaben als auch die individuellen heuristischen Aufgaben wurden in einer nicht-deterministischen Weise implementiert, um die Flexibilität zu verbessern und zu verhin- dern, dass man in lokal optimalen Lösungen gefangen ist. Die mit dieser Methode erzielten Ergebnisse sind sowohl für topologische als auch für Knotenähnlichkeitsziele bemerkenswert optimiert und ausgewogen.