Structural and Relational Data Mining for Systems Biology Applications

Abstract

Due to the enormous accumulation of experimental data and the increasing need for combining heterogeneous data sources, the field of systems biology yields novel and very interesting problems in data analysis. The development of high-throughput technologies has opened the possibility to study the behavior of many cellular components simultaneously. Therefore, there is an increasing interest and effort in not only understanding the functions of single isolated components, but also revealing the interactions and functional relationships between different components. Often, the outcome of large-scale measurements is conveniently represented in a structured form; prominent examples are protein-protein interaction networks, coexpression networks for genes, and bipartite graphs of associations between experimental conditions and regulated genes. This thesis presents different methods that aim at finding interesting patterns in such data. The main contributions are as follows. First, an exact enumerative approach to dense cluster detection is proposed. Given a weighted interaction network and a default weight for missing edges, the density of a node set is defined as the average pairwise interaction weight. The described method finds all patterns that satisfy a user-defined minimum density threshold. Conceptually, this task is a generalization of clique search; however, the standard techniques to solve that problem are not appropriate for the generalized question. Fortunately, an efficient enumeration strategy can be achieved by adopting the reverse search paradigm. Remarkably, the same algorithmic framework is applicable to discover cluster patterns in other types of structured data, like asymmetric binary relations and multipartite graphs, as well as hypergraphs, n-ary relations, and tensors. Second, our approach integrates additional constraints in order to focus the search on clusters that are relevant for the specific application at hand. For example, if each node in a network has an annotation profile attached to it, we can identify dense clusters where the nodes share a common subprofile. The principal idea is that the user provides the datasets of interest and defines desired properties of patterns with respect to them, and the method yields all solutions that match these criteria. This allows to jointly explore network data and background information in a systematic way. Third, we devise dense cluster detection approaches that sacrifice completeness of the solution set in favor of efficiency. Here, two different directions are pursued. On the one hand, we use the search strategy of the enumeration methods and introduce heuristic pruning rules to speed up the procedure. On the other hand, we propose generalizations of agglomerative hierarchical clustering for bipartite data. They detect dense clusters by successive “greedy” merging of instance sets. Consequently, this strategy and the complete enumeration approach can be seen as opposite extremes of dense cluster detection algorithms for structured data. However, both methods are very transparent with respect to the properties of the discovered set of patterns and thereby facilitate the interpretation of results. The presented algorithmic approaches are illustrated with a number of real-world applications in systems biology. They involve multiple types of genomic datasets and relate to different representative organisms, primarily yeast, human, and the plant A. thaliana. One scenario is protein complex prediction from experimental interaction data, with optional constraints from background data; the latter allow to discover context-dependent variants of complexes. Another application is the joint analysis of multiple biological networks that describe different kinds of relationships between genes, in our case transcriptional coregulation under different cellular conditions. Beyond that, we consider the detection of bicluster patterns from gene expression measurements. Finally, we show a small-scale case study on discovering associations between genomic sequence variation and transcription of genes.

Aufgrund der enormen Fülle an experimentellen Daten und des steigenden Bedarfs an Methoden, die heterogene Datenquellen integrieren, stellt die Systembiologie-Forschung das Gebiet der Datenanalyse vor neue und sehr interessante Aufgaben. Die Entwicklung von Hochdurchsatz-Messmethoden hat die Möglichkeit eröffnet, das Verhalten zahlreicher zellulärer Komponenten gleichzeitig zu analysieren. Neben der Aufklärung der Funktion einzelner isolierter Komponenten gilt daher auch den Interaktionen und funktionellen Beziehungen zwischen verschiedenen Komponenten wachsendes Interesse. Zur zusammenfassenden Darstellung von experimentellen Daten großen Maßstabs sind Graphstrukturen oftmals sehr geeignet, beispielsweise Interaktionsnetzwerke für Proteine, Coexpressionsnetzwerke für Gene und bipartite Graphen von Assoziationen zwischen experimentellen Bedingungen und regulierten Genen. Diese Arbeit stellt verschiedene Methoden vor, die darauf abzielen, interessante Muster in solchen Daten zu finden. Die wesentlichen Beiträge sind im Folgenden zusammengefasst. Zunächst wird ein exakter enumerativer Ansatz zum Auffinden von dichten Clustern vorgeschlagen. Für ein gegebenes gewichtetes Interaktionsnetzwerk und ein Standardgewicht für fehlende Kanten definieren wir die Dichte einer Knotenmenge als das durchschnittliche paarweise Interaktionsgewicht. Die beschriebene Methode zählt alle Muster auf, die einen benutzerdefinierten Dichte-Schwellwert überschreiten. Konzeptionell kann man dieses Problem als eine Verallgemeinerung der Cliquen-Suche betrachten; entsprechende Standardtechniken eignen sich allerdings nicht zur Lösung der allgemeineren Fragestellung. Jedoch kann man durch Anwendung des Paradigmas der reversen Suche eine effiziente Enumerationsstrategie erhalten. Bemerkenswerterweise lässt sich dasselbe algorithmische Framework auch zur Clustersuche in anderen Formen strukturierter Daten anwenden; Beispiele dafür sind asymmetrische binäre Relationen und multipartite Graphen sowie Hypergraphen, n-äre Relationen und Tensoren. Zum zweiten integriert unser Ansatz zusätzliche Constraints, um die Suche auf Clusterstrukturen zu beschränken, die für die spezifische vorliegende Anwendung relevant sind. Falls zum Beispiel jeder Knoten eines Netzwerks mit einem Annotationsprofil versehen ist, können wir dichte Cluster identifizieren, deren Knoten hinsichtlich eines Teilprofils übereinstimmen. Die grundsätzliche Idee dabei ist, dass der Benutzer die Datensätze von Interesse vorgibt und gewünschte Mustereigenschaften in Bezug auf die einzelnen Datensätze festlegt; die Methode liefert dann alle Lösungen, die diese Kriterien erf¨ullen. Dieser Ansatz ermöglicht es dem Benutzer, Netzwerkdaten und Hintergrundinformation gemeinsam und auf systematische Art und Weise zu untersuchen. Drittens werden Methoden zum Auffinden von dichten Clustern ausgearbeitet, die zugunsten der Effizienz auf die Vollständigkeit der Lösungsmenge verzichten. Hierbei werden zwei unterschiedliche Richtungen verfolgt. Einerseits verwenden wir die enumerative Strategie und führen zusätzlich heuristische Pruningregeln ein, um die Suche zu beschleunigen. Andererseits schlagen wir Verallgemeinerungen des agglomerativen hierarchischen Clusterings in bipartiten Daten vor, welche durch fortgesetztes "greedy" Verschmelzen von Instanzmengen dichte Muster entdecken. Letzterer Ansatz und die vollständige Musteraufzählung stellen gewissermaßen entgegengesetzte Extreme für Algorithmen zur Clustersuche dar. Jedoch sind beide Methoden äußerst transparent im Hinblick auf die Eigenschaften der zurückgegebenen Mustermenge und erleichtern somit die Interpretation der Ergebnisse. Die vorgestellten algorithmischen Ansätze werden anhand einer Reihe von praktischen Anwendungen aus dem Bereich der Systembiologie illustriert. Diese beinhalten unterschiedliche Arten von genomischen Datensätzen und beziehen sich auf verschiedene repräsentative Organismen, in erster Linie auf Hefe, Mensch und die Pflanze A. thaliana. Ein Szenario ist die Vorhersage von Proteinkomplexen auf der Basis von experimentellen Interaktionsdaten, mit optionalen Constraints bezüglich verschiedener Arten von Hintergrundinformation; letztere ermöglichen die Entdeckung kontextabhängiger Komplexvarianten. Eine weitere Anwendung ist die gemeinsame Analyse mehrerer biologischer Netzwerke, welche unterschiedliche Arten von Beziehungen zwischen Genen beschreiben, in unserem Fall transkriptionelle Coregulation unter verschiedenen zellulären Bedingungen. Darüber hinaus betrachten wir die Suche nach Bicluster-Mustern in Genexpressionsdaten. Schließlich zeigen wir eine kleine Fallstudie, die Assoziationen zwischen der Variation genomischer Sequenzen und der Transkription von Genen untersucht.