Efficient Algorithms for Robust Pattern Mining on Structured Objects with Applications to Structure-Based Drug Design

Viele Objekte aus der realen Welt können nicht auf „flache“ Eigenschaftsvektoren abgebildet werden, ohne dass es dabei zu einem erheblichen Verlust an Information kommt. In den letzten Jahren sind daher graphbasierte Modelle in den Fokus der Forschung im Bereich des Data Mining geraten. In dieser Arbeit werden effiziente Methoden zur Entdeckung unscharfer Muster in Datenbanken aus solchen Graphrepräsentationen vorgestellt. Dabei wird angenommen, dass eine relativ homogene Menge von Graphen gegeben ist, die zum gleichen Cluster beziehungsweise zur gleichen Klasse gehören. Die Klassenzuordnung kann entweder das Ergebnis einer zuvor durchgeführten Cluster-Analyse sein oder auf Hintergrundwissen beruhen. Ziel der hier vorgestellten Methoden ist es, Muster abzuleiten, die charakteristisch für einen so gegebenen Cluster sind. Zusätzlich ist es von Interesse, Muster zu bestimmen, die in der Lage sind, zwischen verschiedenen Clustern zu diskriminieren da sie in den meisten Elementen eines Clusters vorhanden sind, in denen eines anderen Clusters jedoch fehlen. Da jedoch eine gewisse Variabilität auch innerhalb eines sehr homogenen Clusters erwartet werden kann, ist es unwahrscheinlich, dass ein charakteristisches Muster in allen Mitgliedern eines Clusters in exakt identischer Form vorhanden ist. Die in dieser Arbeit vorgestellten Methoden erlauben daher, dass gewisse Modifikationen in den einzelnen Vorkommen der Muster auftreten. Dies wird erreicht, indem die verschiedenen Graphrepräsentationen in das gemeinsame Rahmenwerk eines multiplen Graph-Alignments angeordnet werden. In einem solchen Graph-Alignment werden die einzelnen Knoten der betrachteten Graphen den Knoten der jeweiligen anderen Graphen zugeordnet. Dabei ist es erlaubt, dass Knoten mit verschiedenen Markierungen aufeinander abgebildet werden (bezeichnet als Mismatch). Zusätzlich können sogenannte Dummy-Knoten in die betrachteten Graphen eingefügt werden, die als Platzhalter für „fehlende“ Knoten dienen. Dadurch wird die Robustheit des Ansatzes gegenüber Variationen deutlich erhöht. Ein Bewertungssystem wird eingesetzt, um solche (eigentlich unerwünschten) Konstellationen zu „bestrafen“. Mismatches und Dummy-Nodes sollen in das Graph- Alignment nur eingefügt werden, wenn kein geeigneter Match-Partner in dem jeweiligen Graphen zur Verfügung steht. Damit wird die Berechnung eines Graph-Alignments zu einem diskreten Optimierungsproblem. Für die Lösung solcher Optimierungsprobleme stehen zahlreiche Strategien zur Verfügung, von denen einige im Rahmen der vorliegenden Arbeit untersucht werden. Nachdem ein optimales Graph-Alignment berechnet wurde, können aus diesem charakteristische und diskriminierende Muster abgeleitet werden. Zusätzlich können auf dieser Grundlage eine Reihe weiterer Analysen durchgeführt werden. Insbesondere liefert das Konzept des Graph-Alignment einen Mechanismus, um die Graphrepräsentationen auf „flache“ Eigenschaftsvektoren abzubilden. Dabei wird jedoch die Zuordnung zwischen den einzelnen Knoten der jeweiligen Graphen und den Einträgen der Eigenschaftsvektoren erhalten. Relibase+/Cavbase, eine Datenbank mit potentiellen Protein-Bindestellen, diente als Hauptmotivation für die in dieser Arbeit entwickelten Methoden. In Cavbase werden die Protein-Bindetaschen durch Pseudozentren repräsentiert, die die räumliche Position verschiedener physiko-chemischer Eigenschaften repräsentieren. Die Cavbase-Einträge können in erster Näherung durch Graphen beschrieben werden. Die in dieser Arbeit beschriebenen Methoden können daher genutzt werden, um Familien aus verwandten Proteinbindetaschen zu analysieren. Die so ermittelten Muster können Hinweise für die Entwicklung neuartiger und selektiver Inhibitoren verwendet werden. Bereiche der Bindetasche, die in allen Mitgliedern einer Proteinfamilie in gleicher Form vorhanden sind, (d.h. charakteristische Muster) können adressiert werden, um Affinität für alle Mitglieder der Familie gleichermassen zu erhalten. Bereiche, die zwischen den verschiedenen Mitgliedern der Proteinfamilie variieren (d.h. diskriminierende Muster), können durch Liganden adressiert werden, um Selektivität innerhalb der Proteinfamilie zu erreichen.