dc.contributor.author
Hüffner, Sharon
dc.date.accessioned
2018-06-07T20:25:59Z
dc.date.available
2015-01-09T12:28:35.879Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/6828
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-11027
dc.description.abstract
Networks are commonly used to model complex real-world systems such as the
cell or the brain. An important notion in analyzing networks is modularity.
Usually, a network is considered modular if all its nodes can be partitioned
into dense, connected subsets that are sparsely connected to one another. In
this thesis, we extend the definition of modularity to cover networks that do
contain dense modules that are sparsely connected to the rest of the network,
but some nodes can belong to the region outside of modules, the so-called
transition region. Accordingly, in contrast to full partitions, this work
deals considers assignments: The association of every node to a module in the
modular region or to the transition region. The first task to be tackled in
this thesis is the construction of a formal definition of modularity. After
surveying some of the prominent existing definitions in the literature, we
found that they cannot be directly applied to networks that are not fully-
partitionable. We then developed an approach based on time-continuous random
walks for analyzing networks. Here we built on a rich literature on the topic
of spectral clustering, equating network modules with metastable sets of a
random walk. This allows us to define a network as modular if there is a
choice of modules that produces a coarse-grained Markov process whose dynamics
well-approximate those of the original random walk on the network. We first
demonstrate that this score matches our intuition of modularity on synthetic
networks, increasing with the density of the modules and in the case where the
modular region is large. Perturbation analysis is then used to formally prove
the correct behavior of the score on two specifically constructed classes of
networks. Motivated both by the need to provide a good assignment as input to
the modularity score and by the established usefulness of clustering methods,
the second task to be tackled is that of finding good assignments. Continuing
with the approach of Markov models, we first describe an algorithm based on a
continuous random walk on the network. Next, modifications to several leading
full-partition algorithms are described so that they output modules and
transition regions rather than full partitions. The performance of all
algorithms is then tested on a class of benchmark networks. Finally, we
developed a combinatorial model of networks that are not fully partitionable
as a union of split graphs, and posed the problem of finding modules and
transition regions as a graph editing problem, proving its hardness and
providing exact algorithms and heuristics. The discussion of each of the two
tasks is completed by an example of a biological application. Identifying good
assignments gives us a way to detect protein complexes in protein interaction
networks, a well-studied topic. The flexibility of assigning proteins to
modules or to the transition region helps identify more complicated structures
as complexes. The modularity score is used to analyze the brain networks of
autistic and typically-developed children, where the distribution of
modularity scores is different between the two types. In future work it will
be interesting to further investigate the modularity of biological networks
and draw conclusions about their organization.
de
dc.description.abstract
Netzwerke werden häufig benutzt, um komplexe reale Netzwerke wie die Zelle
oder das Gehirn zu modellieren. Ein wichtiger Begriff zur Analyse von
Netzwerken ist Modularität. Normalerweise wird ein Netzwerk als modular
angesehen, wenn alle Knoten in dichte zusammenhängende Teilmengen
partitioniert werden können, die untereinander nur schwach verbunden sind. In
dieser Arbeit erweitern wir die Definition von Modularität, um auch Netzwerke
zu erfassen, die dichte Module enthalten, die nur schwach mit dem Rest des
Netzwerks verbunden sind, aber in denen einige Knoten zum Bereich außerhalb
der Module gehören können, dem sogenannten Übergangsbereich.
Dementsprechend betrachtet diese Arbeit im Gegensatz zu vollständigen
Partitionen die sogenannten Zuordnungen: die Zuweisung von jedem Knoten zu
einem Modul im Modulbereich oder zum Übergangsbereich. Die erste Aufgabe, die
in dieser Arbeit in Angriff genommen wird, ist die Konstruktion einer formalen
Definition von Modularität. Nachdem wir eine Bestandsaufnahme einiger
bekannten existierenden Definitionen in der Literatur erstellt haben, fanden
wir heraus, dass sie nicht direkt für Netzwerke angewendet werden können,
die nicht vollständig partitionierbar sind. Wir entwickelten dann einen
Ansatz, der auf zeitkontinuierlichen Random Walks zur Analyse von Netzwerken
basiert. Dabei haben wir auf einer reichhaltigen Literatur zum Thema
spektrales Clustering aufgesetzt, bei der Netzwerkmodule mit metastabilen
Mengen des Random Walks gleichgesetzt werden. Dies erlaubt uns, ein Netzwerk
als modular zu definieren, wenn es eine Auswahl von Modulen gibt, die einen
grobkörnigen Markow-Prozess erzeugt, dessen Dynamik die des ursprünglichen
Random Walks auf dem Netzwerk gut approximiert. Wir zeigen zuerst, dass dieser
Score auf künstlichen Netzwerken mit unserer Intuition übereinstimmt und mit
der Dichte der Module und der Größe des Modulbereichs zunimmt.
Perturbationsanalyse wird dann benutzt, um das korrekte Verhalten des Scores
auf zwei speziell konstruierten Klassen von Netzwerken formal zu beweisen.
Motiviert sowohl durch die Notwendigkeit, eine gute Zuordnung als Eingabe für
den Score zu finden, als auch durch die bekannte Nützlichkeit von Clustering-
Methoden ist die zweite anzugehende Aufgabe die des Findens einer guten
Zuordnung. Den Ansatz von Markow-Modellen fortsetzend, beschreiben wir einen
Algorithmus, der auf einem zeitkontinuierlichen Random Walk auf dem Netzwerk
beruht. Als nächstes werden Modifikationen für mehrere etablierte
Algorithmen zum vollständigen Partitionieren beschrieben, die bewirken, dass
sie Module und Übergangsbereich ausgeben anstelle von vollständigen
Partitionen. Die Performance aller Algorithmen wird dann auf einer Klasse von
Benchmark-Netzwerken getestet. Schließlich entwickeln wir ein kombinatorisches
Modell von Netzwerken, die nicht vollständig partitionierbar sind, als
Vereinigung von Split-Graphen, und formulieren das Problem, Module und den
Übergangsbereich zu finden, als Grapheditierungsproblem; wir beweisen
kombinatorische Schwierigkeit und zeigen exakte Algorithmen und Heuristiken.
Die Diskussion jeder der beiden Aufgaben wird vervollständigt durch ein
Beispiel einer biologischen Anwendung. Die Identifikation guter Zuordnungen
gibt uns eine Möglichkeit, Proteinkomplexe in Proteininteraktionsnetzwerken
zu finden, ein gut untersuchtes Thema. Die Flexibilität, ein Protein einem
Modul oder dem Übergangsbereich zuzuordnen, hilft dabei, kompliziertere
Strukturen als Komplexe zu erkennen. Der Modularitäts-Score wird benutzt, um
die Gehirnnetzwerke von autistischen und typisch entwickelten Kindern zu
analysieren, wo die Verteilung von Modularitäts-Scores zwischen den beiden
Gruppen unterschiedlich ist, was uns Vermutungen über den Grund für diesen
Unterschied anstellen lässt. In weiteren Arbeiten wird es interessant sein,
die Modularität biologischer Netzwerke weiter zu erforschen und
Schlussfolgerungen über ihre Organisation zu ziehen.
de
dc.format.extent
VIII, 123 S.
dc.rights.uri
http://www.fu-berlin.de/sites/refubium/rechtliches/Nutzungsbedingungen
dc.subject.ddc
500 Naturwissenschaften und Mathematik::510 Mathematik::519 Wahrscheinlichkeiten, angewandte Mathematik
dc.title
Modularity in Biological Networks
dc.contributor.firstReferee
Prof. Dr. Christof Schütte
dc.contributor.furtherReferee
Prof. Dr. Ulrike von Luxburg
dc.date.accepted
2014-10-22
dc.identifier.urn
urn:nbn:de:kobv:188-fudissthesis000000098121-5
dc.title.translated
Modularität in biologischen Netzwerken
de
refubium.affiliation
Mathematik und Informatik
de
refubium.mycore.fudocsId
FUDISS_thesis_000000098121
refubium.mycore.derivateId
FUDISS_derivate_000000016251
dcterms.accessRights.dnb
free
dcterms.accessRights.openaire
open access