Die Graphtheorie ist eines der wirklich interdisziplinären Forschungsfelder. Nicht nur führt die Anwendung von Graphen zu neuen Erkenntnissen in einer Vielzahl von Disziplinen – Physik, Biologie, Soziologie, Mathematik, Informatik –, sondern all diese Disziplinen wirken mit ihren unterschiedlichen Fragestellungen und Sichtweisen aktiv auf die Entwicklung und Erforschung der Graphtheorie selbst ein. Vernetzte und mit Interdependenzen behaftete Systeme abstrahieren und mathematisch exakt beschreiben zu können, bietet für viele Fragestellungen eine Art der Problembeschreibung, die das Finden gewisser »topologie-basierter« Lösungswege begünstigt und gleichzeitig einen methodischen Werkzeugkoffer zur Verfügung stellt – gerade die statistische Physik bietet zahlreiche Beispiele dafür.

In dieser Arbeit werden verschiedene Fragestellungen aus dem Bereich der verteilten Analysen der Biologie und Medizin betrachtet. Dabei stellen die verwendeten Gesundheitsdaten oft ein erhebliches Risiko für die Privatsphäre der Betroffenen dar – noch immer sind zahlreiche Erkrankungen gesellschaftlich stigmatisiert, sodass ein Bekanntwerden zu Ausgrenzung, beruflichen Nachteilen, bis hin zu körperlichen Gefährdungen führen könnte. Das wird auch von der Gesetzgebung widergespiegelt, die Gesundheitsdaten — und anderen Daten, die das Risiko der Identifikation eines Individuums bergen — einen besonderen Schutzbedarf attestiert.

Daher werden in dieser Dissertation Methoden und Algorithmen entworfen, implementiert und empirisch untersucht, die nicht nur für die Erlangung medizinischer Erkenntnisse und der Entwicklung neuer Behandlungsmethoden relevant sind, sondern die zeitgleich ein überaus hohes Datenschutzniveau bezüglich der sensiblen Daten aufweisen. Dazu bedienen sich die entwickelten Methoden der Techniken des kryptografischen Feldes der Secure Multi-Party-Computation (MPC) – einer Klasse kryptografischer Protokolle, die die gemeinsame Berechnung über verteilte Datenbestände ermöglicht und zeitgleich höchste Sicherheitsgarantien bezüglich der Geheimhaltung der (verteilten) Eingabedaten gibt. Dabei spielen Graphen eine zentrale Rolle: Die abzubildenden Funktionalitäten werden als Boolesche oder arithmetische ungerichtete azyklische Graphen repräsentiert, bei denen die Knoten Operationen oder interaktive Protokolle darstellen.

Doch nicht nur die Methodik und die eingesetzten Techniken in dieser Dissertation bedienen sich der Methoden der statistischen Physik und der Graphtheorie – viele der medizinischen Fragestellungen sind ganz direkt Graphprobleme oder führen über die Betrachtung als Graph zu einer effizienteren Problemdarstellung. So wurde ein Verfahren entwickelt, um Epistasisbeziehungen, also nichtlineare Gen-Gen- und Gen-Umgebungs-Interaktionen, sowie die daraus resultierenden Genregulationsnetzwerke effizient und die Privatsphäre schützend zu analysieren. Um die Verarbeitung der erforderlichen Mengen genetischer Daten in für den Einsatz akzeptablen Zeitskalen zu ermöglichen, wurden neue, allgemein verwendbare MPC-Bausteine entwickelt. Des Weiteren wurde das Graphoptimierungsproblem der effizienten und fairen Zuteilung von Spendernieren für Nierentransplantationen bearbeitet. Auch hier sind sensible medizinische Daten betroffen, sodass Datenschutzaspekte eine bedeutende Rolle spielen. Nicht nur bestehen bei dieser Fragestellung viele Randbedingungen, zum Beispiel bezüglich der Robustheit der Lösungen oder der medizinischen Kompatibilität von Organspendern und -empfängern sondern das Finden der globalen Lösung ist ein Problem mit superpolynomialer Komplexität, sodass in dieser Arbeit ein lokal optimaler Algorithmus vorgestellt wird. Schließlich wird das in der medizinischen Forschung hochrelevante Problem des probabilistischen Record-Linkage betrachtet. Dabei soll basierend auf personenbezogenen Daten wie Vorund Nachname, Adresse und Geburtstag die Ähnlichkeit zwischen Patienten in einer oder mehreren Datenbanken beurteilt werden, mit dem Ziel, selbst bei »verrauschten« Daten, also Schreibfehlern und der Verwechslung von Kennzeichnern, Duplikate zu identifizieren. Über den Weg der Graphrepräsentation und die damit verbundene Suche nach approximierten Subgraph-Isomorphismen wird Record-Linkage auf ein (einfacheres) Datenbank-Problem mit effizient lösbaren Algorithmen zurückgeführt. Das entwickelte Framework Mainzelliste Secure EpiLinker (MainSEL) bietet eine Möglichkeit zum sicheren, die Privatsphäre schützenden probabilistischen Record-Linkage zwischen verschiedenen medizinischen Institutionen. Es ermöglicht zudem weitere Datentypen auf Ähnlichkeit zu vergleichen. Am Ende dieser Dissertation werden drei vielversprechende, jedoch noch nicht umfänglich erforschte Erweiterung vorgestellt, die den Abgleich von pharmakologisch relevanten kleinen Molekülgraphen, die Suche nach ähnlichen Patienten in klinischen Datenbanken für unspezifische Diagnosen oder die Identifikation von gestörten biologischen Regulationspfaden durch den Vergleich von Transkriptomnetzwerken erlauben.