Dokument 1

Prüfsumme (MD5)

Kurzfassung in Englisch:
Many complex real-world objects cannot be mapped onto “flat” feature vector representations without a significant loss of information. Recently, the use of graph-based models gained increasing attention in the field of data mining. This thesis presents efficient methods for fuzzy pattern mining in databases of such graph representations. It is assumed that relatively homogeneous sets of graphs originating from common classes or clusters are given. The class assignment can either result from background knowledge or from a previously performed cluster analysis. The aim of the developed methods is to derive patterns that are characteristic for a given cluster (i.e., that occur in all or most of the members of a cluster). Additionally, it is of interest to derive patterns that are discriminative among different clusters (i.e., that occur in most of the members of one cluster but are missing in most of the members of a different cluster). As a certain variability can be observed also among members of the same cluster, one cannot expect that a characteristic pattern is present in all members of the cluster in identical form. The methods presented in this thesis thus allow also for variations of a characteristic pattern in its different occurrences. This is achieved by arranging the different graph representations in the common framework of a multiple graph alignment. In a graph alignment, nodes with different labels can be assigned to each other (“mismatch”) and dummy nodes can be inserted into the graphs to compensate “missing” nodes. This increases the robustness of the approach against variations in the considered graphs. A scoring system is used to penalize such constellations as they should be allowed only if no “valid” match for a certain node exists in the remaining graph instances. The calculation of a graph alignment can thus be interpreted as an optimization problem and a number of different strategies for the calculation of optimal graph alignments are examined. Once an optimal graph alignment has been calculated, characteristic and discriminative patterns can be derived and a number of different analyses can be performed. In particular, the concept of multiple graph alignment yields a mechanism for mapping the aligned graphs onto “flat” feature vectors that preserves the correspondence among the individual features of the graph and vector representation. Relibase+/Cavbase, a huge database of putative protein binding sites serves as the main motivation for the methods developed in this thesis. In Cavbase, the protein binding pockets are represented through pseudocenters that describe the spatial position of certain physicochemical properties. In a first-order approximation, graphs can be used as descriptors for the Cavbase entries. The methods presented in this thesis can therefore be used to analyze families of related protein binding pockets. The derived patterns can be used to guide the development of novel and selective inhibitors. Regions of a binding pocket that are common to the members of a protein family (i.e., characteristic patterns) could be addressed to gain affinity for the whole protein family. Regions that vary among the different members of a protein family (i.e., discriminative patterns) indicate features that can be addressed to gain selectivity within the examined protein family.

Kurzfassung in Deutsch:
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.

Das Dokument ist im Internet frei zugänglich - Hinweise zu den Nutzungsrechten