Structural and relational data mining for systems biology applications [Elektronische Ressource] / vorgelegt von Elisabeth Georgii

Sujets

• Informatik

Informations

• Publié par: eberhard_karls_universitat_tubingen
• Publié le: 01 janvier 2010
• Nombre de lectures: 4
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Structural and Relational
Data Mining
for Systems Biology Applications
Dissertation
der Fakult¨at fur¨ Informations- und Kognitionswissenschaften
der Eberhard-Karls-Universit¨at Tu¨bingen
zur Erlangung des Grades eines
Doktors der Naturwissenschaften
(Dr. rer. nat.)
vorgelegt von
Dipl.-Bioinf. Elisabeth Georgii
aus Bielefeld
Tubi¨ ngen
2010Tag der mun¨ dlichen Qualifikation: 15.12.2010
Dekan: Prof. Dr.-Ing. Oliver Kohlbacher
1. Berichterstatter: Prof. Dr. Daniel Huson
2. Berichterstatter: PD Dr. Peer Kr¨ogerA self does not amount to much, but no self is an island; each exists in a fabric of
relations [...].
Jean-Fran¸cois LyotardAbstract
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,anefficientenumerationstrategycanbeachievedbyadopting
the reverse search paradigm. Remarkably, the same algorithmic framework is appli-
cable 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
searchonclustersthatarerelevantforthespecificapplicationathand. Forexample,
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 ofvi
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 pur-
sued. 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 bipar-
tite 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 experi-
mental 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.Zusammenfassung
Aufgrund der enormen Fulle¨ 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¨oglichkeit er¨off-
net, das Verhalten zahlreicher zellul¨arer Komponenten gleichzeitig zu analysieren.
NebenderAufkl¨arungderFunktioneinzelnerisolierterKomponentengiltdaherauch
den Interaktionen und funktionellen Beziehungen zwischen verschiedenen Kompo-
nenten wachsendes Interesse. Zur zusammenfassenden Darstellung von experimen-
tellenDatengroßenMaßstabssindGraphstrukturenoftmalssehrgeeignet,beispiels-
weise Interaktionsnetzwerke fur¨ Proteine, Coexpressionsnetzwerke fur¨ Gene und bi-
partite Graphen von Assoziationen zwischen experimentellen Bedingungen und re-
guliertenGenen. DieseArbeitstelltverschiedeneMethodenvor,diedaraufabzielen,
interessante Muster in solchen Daten zu finden. Die wesentlichen Beitrag¨ e sind im
Folgenden zusammengefasst.
Zun¨achst wird ein exakter enumerativer Ansatz zum Auffinden von dichten
Clustern vorgeschlagen. Fur¨ ein gegebenes gewichtetes Interaktionsnetzwerk und
ein Standardgewicht fur¨ fehlende Kanten definieren wir die Dichte einer Knoten-
menge als das durchschnittliche paarweise Interaktionsgewicht. Die beschriebene
Methode za¨hlt alle Muster auf, die einen benutzerdefinierten Dichte-Schwellwert
ub¨ erschreiten. Konzeptionell kann man dieses Problem als eine Verallgemeinerung
der Cliquen-Suche betrachten; entsprechende Standardtechniken eignen sich aller-
dings nicht zur L¨osung der allgemeineren Fragestellung. Jedoch kann man durch
Anwendung des Paradigmas der reversen Suche eine effiziente Enumerationsstrate-
gie erhalten. Bemerkenswerterweise l¨asst sich dasselbe algorithmische Framework
auch zur Clustersuche in anderen Formen strukturierter Daten anwenden; Beispiele
dafur¨ sind asymmetrische bin¨are Relationen und multipartite Graphen sowie Hy-
pergraphen, n-¨are Relationen und Tensoren.
Zum zweiten integriert unser Ansatz zus¨atzliche Constraints, um die Suche auf
Clusterstrukturen zu beschr¨anken, die fur¨ die spezifische vorliegende Anwendungviii
relevant sind. Falls zum Beispiel jeder Knoten eines Netzwerks mit einem Annota-
tionsprofil versehen ist, k¨onnen wir dichte Cluster identifizieren, deren Knoten hin-
sichtlich eines Teilprofils ub¨ ereinstimmen. Die grunds¨atzliche Idee dabei ist, dass
der Benutzer die Datens¨atze von Interesse vorgibt und gewunsc¨ hte Mustereigen-
schafteninBezugaufdieeinzelnenDatens¨atzefestlegt; dieMethodeliefertdannalle
L¨osungen, die diese Kriterien erfulle¨ n. Dieser Ansatz erm¨oglicht 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¨andigkeit der L¨osungsmenge verzichten.
Hierbei werden zwei unterschiedliche Richtungen verfolgt. Einerseits verwenden wir
die enumerative Strategie und fuhr¨ en zus¨atzlich 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¨andige Musteraufza¨hlung stellen gewissermaßen ent-
gegengesetzteExtremefur¨ AlgorithmenzurClustersuchedar. JedochsindbeideMe-
thoden a¨ußerst transparent im Hinblick auf die Eigenschaften der zuruc¨ kgegebenen
Mustermenge und erleichtern somit die Interpretation der Ergebnisse.
DievorgestelltenalgorithmischenAnsa¨tzewerdenanhandeinerReihevonprak-
tischen Anwendungen aus dem Bereich der Systembiologie illustriert. Diese be-
inhalten unterschiedliche Arten von genomischen Datens¨atzen und beziehen sich auf
verschiedene reprasen¨ tative 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 bezuglic¨ h
verschiedener Arten von Hintergrundinformation; letztere erm¨oglichen die Entde-
ckung kontextabh¨angiger Komplexvarianten. Eine weitere Anwendung ist d