Viele Probleme der Kombinatorik, Zahlentheorie, Wahrscheinlichkeitstheorie, Zuverlässigkeitstheorie und Statistik lassen sich durch Anwendung einer einheitlichen Methode lösen, die als Prinzip der Inklusion-Exklusion bekannt ist. Das Prinzip der Inklusion-Exklusion drückt die Indikatorfunktion einer Vereinigung endlich vieler Ereignisse als alternierende Summe der Indikatorfunktionen ihrer Durchschnitte aus. Die vorliegende Schrift befasst sich mit verbesserten Inklusions-Exklusions-Identitäten und verbesserten Bonferroni-Ungleichungen, die voraussetzen, dass die Ereignisfamilie gewissen strukturellen Anforderungen genügt. Solche wohl-strukturierten Ereignisfamilien finden sich u.a. in der schließenden Statistik, der kombinatorischen Zuverlässigkeitstheorie und der chromatischen Graphentheorie. / Many problems in combinatorics, number theory, probability theory , reliability theory and statistics can be solved by applying a unifying method, which is known as the principle of inclusion-exclusion. The principle of inclusion-exclusion expresses the indicator function of a union of finitely many events as an alternating sum of indicator functions of their intersections. This thesis deals with improved inclusion-exclusion identities and improved Bonferroni inequalities that require the family of events to satisfy some structural restrictions. Examples of such well-structured families arise in problems of statistical inference, combinatorial reliability theory and chromatic graph theory.

Ein drahtloses Multihop-Netzwerk (DMN) ist ein verteiltes Kommunikationssystem, welches vor allem die Fähigkeit zur automatischen Anpassung an sich ständig änderne Umgebungsbedingungen hat. Eine zentrale Fragestellung in DMNen ist, ob das Netzwerk partitioniert ist, ob also nicht mehr jeder Knoten mit jedem anderen Knoten kommunizieren kann. Um festzustellen, ob eine Partitionierung droht werden mit Hilfe von 2-Zusammenhangstests Brücken und Artikulationspunkte im Kommunikationsgraphen gesucht. Daraufhin können anschließend korrektive Aktionen eingeleitet werden um die Partitionierung zu verhindern und somit die Netzwerkverfügbarkeit zu erhöhen. Eine Vielzahl von 2-Zusammenhangstestverfahren wurde bereits erfolgreich bei drahtgebundenen Netzen eingesetzt. Allerdings sind diese Verfahren ungeeignet für drahtlose Netze, da die Ungenauigkeiten durch den häufigen Paketverlust in solchen Systemen bisher nicht berücksichtigt wurden. Mit Hilfe von stochastischen Modellen wird gezeigt, dass Fehler in der Entscheidungsfindung für DMNen bereits bei sehr einfachen Problemen wie der Link-Erkennung signifikant sein können. In dieser Arbeit werden daher verschiedene Verfahren präsentiert, die auch auf Grundlage unsicherer Informationen noch eine verlässliche Entscheidungsfindung ermöglichen. Die Arbeit präsentiert einen neuen verteilten Algorithmus zum Test auf 2-Zusammenhang, welcher Fehler durch Nachrichtenverlust berücksichtigt und gleichzeitig die Anzahl an Nachrichten reduziert. Basierend auf einer umfassenden Analyse der Einflüsse von Kommunikationsfehlern auf den Algorithmus, wurden Abstimmungsprozeduren entwickelt, die die Wahrscheinlichkeit von Fehlentscheidungen nochmals reduzieren. Zur weiteren Analyse werden die Algorithmen erstens in der Motelab-Umgebung und zweitens mit Hilfe von Simulationen untersucht. Die präsentierten Algorithmen zeigen überzeugende Ergebnisse unter variierenden Bedingungen, was ihre Anwendbarkeit in realen Szenarien unterstreicht. / Wireless multi-hop network (WMN) is a distributed communication system composed of autonomous processing nodes that is known for its ability to automatically adjust to rapidly changing conditions in the surrounding environment. Connectivity is one of the basic properties of a network. Removal of a bridge or an articulation point partitions a network. Biconnectivity testing identifies bridges and articulation points in a network, and once they are known corrective actions can be performed in order to improve network''s reliability. Numerous biconnectivity testing algorithms are successfully applied in graphs, wired networks and multiprocessor systems. However, they are inadequate for application in wireless networks since the frequent packet losses introduce uncertainty in the system which these algorithms cannot handle. The stochastic analysis shows that errors in decision-making in WMNs are considerable even for seemingly simple tasks such as the detection of links. The main contribution of this work is to provide means for accurate binary decision-making under uncertainty within the context of biconnectivity testing in WMNs. A distributed algorithm is developed that successfully handles the faults caused by message losses and simultaneously utilizes benefits of wireless communication to reduce message complexity from O(e) to O(n). Based on stochastic analysis of WMN topologies and a comprehensive analysis of impact of communication faults on algorithm''s behavior, the algorithm is extended by voting theory to reduce probability of erroneous decisions. The algorithm and the voting rules are evaluated in experiments in Motelab testbed and in the event-based simulator Jist/SWANS. The algorithm is accurate under various conditions which demonstrates its applicability in reality and capability of successful operation in presence of packet losses.

Biolog:innen untersuchen häufig Pathways, Netzwerke von Interaktionen zwischen Proteinen und Genen mit einer spezifischen Funktion. Neue Erkenntnisse über Pathways werden in der Regel zunächst in Publikationen veröffentlicht und dann in strukturierter Form in Lehrbüchern, Datenbanken oder mathematischen Modellen weitergegeben. Deren Kuratierung kann jedoch aufgrund der hohen Anzahl von Publikationen sehr aufwendig sein. In dieser Arbeit untersuchen wir wie Text Mining Methoden die Kuratierung unterstützen können. Wir stellen PEDL vor, ein Machine-Learning-Modell zur Extraktion von Protein-Protein-Assoziationen (PPAs) aus biomedizinischen Texten. PEDL verwendet Distant Supervision und vortrainierte Sprachmodelle, um eine höhere Genauigkeit als vergleichbare Methoden zu erreichen. Eine Evaluation durch Expert:innen bestätigt die Nützlichkeit von PEDLs für Pathway-Kurator:innen. Außerdem stellen wir PEDL+ vor, ein Kommandozeilen-Tool, mit dem auch Nicht-Expert:innen PPAs effizient extrahieren können. Drei Kurator:innen bewerten 55,6 % bis 79,6 % der von PEDL+ gefundenen PPAs als nützlich für ihre Arbeit. Die große Anzahl von PPAs, die durch Text Mining identifiziert werden, kann für Forscher:innen überwältigend sein. Um hier Abhilfe zu schaffen, stellen wir PathComplete vor, ein Modell, das nützliche Erweiterungen eines Pathways vorschlägt. Es ist die erste Pathway-Extension-Methode, die auf überwachtem maschinellen Lernen basiert. Unsere Experimente zeigen, dass PathComplete wesentlich genauer ist als existierende Methoden. Schließlich schlagen wir eine Methode vor, um Pathways mit komplexen Ereignisstrukturen zu erweitern. Hier übertrifft unsere neue Methode zur konditionalen Graphenmodifikation die derzeit beste Methode um 13-24% Genauigkeit in drei Benchmarks. Insgesamt zeigen unsere Ergebnisse, dass Deep Learning basierte Informationsextraktion eine vielversprechende Grundlage für die Unterstützung von Pathway-Kurator:innen ist. / Biological knowledge often involves understanding the interactions between molecules, such as proteins and genes, that form functional networks called pathways. New knowledge about pathways is typically communicated through publications and later condensed into structured formats such as textbooks, pathway databases or mathematical models. However, curating updated pathway models can be labour-intensive due to the growing volume of publications. This thesis investigates text mining methods to support pathway curation. We present PEDL (Protein-Protein-Association Extraction with Deep Language Models), a machine learning model designed to extract protein-protein associations (PPAs) from biomedical text. PEDL uses distant supervision and pre-trained language models to achieve higher accuracy than the state of the art. An expert evaluation confirms its usefulness for pathway curators. We also present PEDL+, a command-line tool that allows non-expert users to efficiently extract PPAs. When applied to pathway curation tasks, 55.6% to 79.6% of PEDL+ extractions were found useful by curators. The large number of PPAs identified by text mining can be overwhelming for researchers. To help, we present PathComplete, a model that suggests potential extensions to a pathway. It is the first method based on supervised machine learning for this task, using transfer learning from pathway databases. Our evaluations show that PathComplete significantly outperforms existing methods. Finally, we generalise pathway extension from PPAs to more realistic complex events. Here, our novel method for conditional graph modification outperforms the current best by 13-24% accuracy on three benchmarks. We also present a new dataset for event-based pathway extension. Overall, our results show that deep learning-based information extraction is a promising basis for supporting pathway curators.

In Laufe der letzten zehn Jahre haben Scientific Workflows als Werkzeug zur Erstellung von reproduzierbaren, datenverarbeitenden in-silico Experimenten an Aufmerksamkeit gewonnen, in die sowohl lokale Skripte und Anwendungen, als auch Web-Services eingebunden werden können. Über spezialisierte Online-Bibliotheken, sogenannte Repositories, können solche Workflows veröffentlicht und wiederverwendet werden. Mit zunehmender Größe dieser Repositories werden Ähnlichkeitsmaße für Scientific Workflows notwendig, etwa für Duplikaterkennung, Ähnlichkeitssuche oder Clustering von funktional ähnlichen Workflows. Die vorliegende Arbeit untersucht solche Ähnlichkeitsmaße für Scientific Workflows. Als erstes untersuchen wir ähnlichkeitsrelevante Eigenschaften von Scientific Workflows und identifizieren Charakteristika der Wiederverwendung ihrer Komponenten. Als zweites analysieren und reimplementieren wir existierende Lösungen für den Vergleich von Scientific Workflows entlang definierter Teilschritte des Vergleichsprozesses. Wir erstellen einen großen Gold-Standard Corpus von Workflowähnlichkeiten, der über 2400 Bewertungen für 485 Workflowpaare enthält, die von 15 Experten aus 6 Institutionen beigetragen wurden. Zum ersten Mal erlauben diese Vorarbeiten eine umfassende, vergleichende Evaluation verschiedener Ähnlichkeitsmaße für Scientific Workflows, in der wir einige vorige Ergebnisse bestätigen, andere aber revidieren. Als drittes stellen wir ein neue Methode für das Vergleichen von Scientific Workflows vor. Unsere Evaluation zeigt, dass diese neue Methode bessere und konsistentere Ergebnisse liefert und leicht mit anderen Ansätzen kombiniert werden kann, um eine weitere Qualitätssteigerung zu erreichen. Als viertes zweigen wir, wie die Resultate aus den vorangegangenen Schritten genutzt werden können, um aus Standardkomponenten eine Suchmaschine für schnelle, qualitativ hochwertige Ähnlichkeitssuche im Repositorymaßstab zu implementieren. / Over the last decade, scientific workflows have gained attention as a valuable tool to create reproducible in-silico experiments. Specialized online repositories have emerged which allow such workflows to be shared and reused by the scientific community. With increasing size of these repositories, methods to compare scientific workflows regarding their functional similarity become a necessity. To allow duplicate detection, similarity search, or clustering, similarity measures for scientific workflows are an essential prerequisite. This thesis investigates similarity measures for scientific workflows. We carry out four consecutive research tasks: First, we closely investigate the relevant properties of scientific workflows regarding their similarity and identify characteristics of re-use of their components. Second, we review and dissect existing approaches to scientific workflow comparison into a defined set of subtasks necessary in the process of workflow comparison, and re-implement previous approaches to each subtask. We create a large gold-standard corpus of expert-ratings on workflow similarity, with more than 2400 ratings provided for 485 pairs of workflows by 15 workflow experts from 6 institutions. For the first time, this allows comprehensive, comparative evaluation of different scientific workflow similarity measures, confirming some previous findings, but rejecting others. Third, we propose and evaluate a novel method for scientific workflow comparison. We show that this novel method provides results of both higher quality and higher consistency than previous approaches, and can easily be stacked and ensembled with other approaches for still better performance and higher speed. Fourth, we show how our findings can be leveraged to implement a search engine using off-the-shelf tools that performs fast, high quality similarity search for scientific workflows at repository-scale, a premier area of application for similarity measures for scientific workflows.

Vernetzte Standardarbeitsplatzrechner (sog. Cluster) sind eine attraktive Umgebung zur Ausf"uhrung paralleler Programme; f"ur einige Anwendungsgebiete bestehen jedoch noch immer ungel"oste Probleme. Ein solches Problem ist die Verl"asslichkeit und Rechtzeitigkeit der Programmausf"uhrung: In vielen Anwendungen ist es wichtig, sich auf die rechtzeitige Fertigstellung eines Programms verlassen zu k"onnen. Mechanismen zur Kombination dieser Eigenschaften f"ur parallele Programme in verteilten Rechenumgebungen sind das Hauptanliegen dieser Arbeit. Zur Behandlung dieses Anliegens ist eine gemeinsame Metrik f"ur Verl"asslichkeit und Rechtzeitigkeit notwendig. Eine solche Metrik ist die Responsivit"at, die f"ur die Bed"urfnisse dieser Arbeit verfeinert wird. Als Fallstudie werden Calypso und Charlotte, zwei Systeme zur parallelen Programmierung, im Hinblick auf Responsivit"at untersucht und auf mehreren Abstraktionsebenen werden Ansatzpunkte zur Verbesserung ihrer Responsivit"at identifiziert. L"osungen f"ur diese Ansatzpunkte werden zu allgemeineren Mechanismen f"ur (parallele) responsive Dienste erweitert. Im Einzelnen handelt es sich um 1. eine Analyse der Responsivit"at von Calypsos ``eager scheduling'' (ein Verfahren zur Lastbalancierung und Fehlermaskierung), 2. die Behebung eines ``single point of failure,'' zum einen durch eine Responsivit"atsanalyse von Checkpointing, zum anderen durch ein auf Standardschnittstellen basierendes System zur Replikation bestehender Software, 3. ein Verfahren zur garantierten Ressourcenzuteilung f"ur parallele Programme und 4.die Einbeziehung semantischer Information "uber das Kommunikationsmuster eines Programms in dessen Ausf"uhrung zur Verbesserung der Leistungsf"ahigkeit. Die vorgeschlagenen Mechanismen sind kombinierbar und f"ur den Einsatz in Standardsystemen geeignet. Analyse und Experimente zeigen, dass diese Mechanismen die Responsivit"at passender Anwendungen verbessern. / Clusters of standard workstations have been shown to be an attractive environment for parallel computing. However, there remain unsolved problems to make them suitable to some application scenarios. One of these problems is a dependable and timely program execution: There are many applications in which a program should be successfully completed at a predictable point of time. Mechanisms to combine the properties of both dependable and timely execution of parallel programs in distributed computing environments are the main objective of this dissertation. Addressing these properties requires a joint metric for dependability and timeliness. Responsiveness is such a metric; it is refined for the purposes of this work. As a case study, Calypso and Charlotte, two parallel programming systems, are analyzed and their shortcomings on several abstraction levels with regard to responsiveness are identified. Solutions for them are presented and generalized, resulting in widely applicable mechanisms for (parallel) responsive services. Specifically, these solutions are: 1) a responsiveness analysis of Calypso's eager scheduling (a mechanism for load balancing and fault masking), 2) ameliorating a single point of failure by a responsiveness analysis of checkpointing and by a standard interface-based system for replication of legacy software, 3) managing resources in a way suitable for parallel programs, and 4) using semantical information about the communication pattern of a program to improve its performance. All proposed mechanisms can be combined and are suitable for use in standard environments. It is shown by analysis and experiments that these mechanisms improve the responsiveness of eligible applications.

Die Besonderheit der drahtlosen Kommunikation gegenüber den drahtgebundenen Netzwerken liegt im drahtlosen Übertragungsmedium. Aufgrund der Broadcast-Eigenschaft des Übertragungsmediums werden Nachrichten potentiell von allen Netzwerkstationen empfangen, welche sich in der Übertragungsreichweite des Senders aufhalten. Als Konsequenz können bei einem unsynchronisierten Medienzugriff mehrere Nachrichten beim Empfänger kollidieren und nicht korrekt empfangen werden. Dieses Phänomen wird auch als Interferenz bezeichnet. Um solche Interferenzen zu vermeiden, wurden spezielle Protokolle für den Medienzugriff in drahtlosen Netzen entwickelt. Ein solcher Ansatz für drahtlose Maschennetze ist die verteilte Kanalzuweisung. Bei der verteilten Kanalzuweisung werden sich nicht-überlappende Kanäle im verfügbaren Frequenzspektrum für Übertragungen verwendet, die auf dem gleichen Kanal Interferenzen erzeugen würden. Dieser Ansatz ist möglich, da die verwendeten Funktechnologien, wie zum Beispiel IEEE 802.11 (WLAN), mehrere nicht-überlappende Kanäle bereitstellen. Aufgrund der großen Verbreitung von IEEE 802.11, ist eine hohe Dichte von privaten wie kommerziellen Netzen im urbanen Raum die Norm. Diese räumlich überlappenden Netze konkurrieren um den Medienzugriff. Daher ist es für die Leistung von Kanalzuweisungsalgorithmen von großer Bedeutung, die Aktivität der externen Netze mit einzubeziehen. Die Leistung der vorgelegten Arbeit umfasst das Design, die Implementierung und Validierung von Modellen und Algorithmen zur Reduzierung von Interferenzen in drahtlosen Maschennetzen. Die Arbeit beinhaltet die Entwicklung eines Messungs-basierten Interferenzmodells, mit dem Interferenzabhängigkeiten der Maschenrouter untereinander effizient bestimmt werden können. Weiterhin wurde ein Algorithmus für die verteilte Kanalzuweisung entwickelt, der die Aktivität von externen Netzen berücksichtigt. Die Gesamtlösung wurde in einem großen drahtlosen Maschennetz experimentell validiert. / Due to the broadcast nature of the shared medium, wireless transmissions are potentially received by all network stations in the communication range of the sender. With an unsynchronized medium access, multiple transmissions may be active at the same time and thus interfere with each other. In consequence, multiple transmissions may collide at the receiver side and cannot be properly decoded. For this reason, protocols have been developed on the MAC layer to synchronize the medium access and thus reduce interference effects. One of these approaches in wireless mesh networks is channel assignment. The idea of channel assignment is to minimize the network-wide interference by utilizing non-overlapping channels for otherwise interfering wireless transmissions. This is feasible, since wireless mesh routers are usually equipped with multiple radios and commonly used wireless network technologies, such as IEEE 802.11, provide multiple non-overlapping channels. Since IEEE 802.11 operates in the unlicensed frequency spectrum, the dense distribution of private and commercial network deployments of WLANs in urban areas poses a new challenge. Co-located networks compete for the wireless medium, thus decreasing the achievable network performance in terms of throughput and latency. Therefore, an important issue for efficient channel assignment is to also address external interference The contributions of this dissertation comprise the design, implementation, and validation of models and algorithms to enable wireless multi-hop networks to become interference-aware. This includes a measurement-based interference model suitable for large-scale network deployments. A distributed channel assignment algorithm has been developed that considers external sources of interference. The overall solution has been experimentally validated in a large-scale wireless multi-hop multi-radio testbed and has significantly increased the network performance with regard to the network capacity.

Proteininteraktionen sind entscheidend für zelluläre Funktion. Interaktionen reflektieren direkte funktionale Beziehungen zwischen Proteinen. Veränderungen in spezifischen Interaktionsmustern tragen zur Entstehung von Krankheiten bei. In dieser Arbeit werden funktionale und pathologische Aspekte von Proteininteraktionen analysiert, um Funktionen für bisher nicht charakterisierte Proteine vorherzusagen und Proteine mit Krankheitsphänotypen zu assoziieren. Verschiedene Methoden wurden in den letzten Jahren entwickelt, die die funktionalen Eigenschaften von Proteinen untersuchen. Dennoch bleibt ein wesentlicher Teil der Proteine, insbesondere menschliche, uncharakterisiert. Wir haben eine Methode zur Vorhersage von Proteinfunktionen entwickelt, die auf Proteininteraktionsnetzwerken verschiedener Spezies beruht. Dieser Ansatz analysiert funktionale Module, die über evolutionär konservierte Prozesse definiert werden. In diesen Modulen werden Proteinfunktionen gemeinsam über Orthologiebeziehungen und Interaktionspartner vorhergesagt. Die Integration verschiedener funktionaler Ähnlichkeiten ermöglicht die Vorhersage neuer Proteinfunktionen mit hoher Genauigkeit und Abdeckung. Die Aufklärung von Krankheitsmechanismen ist wichtig, um ihre Entstehung zu verstehen und diagnostische und therapeutische Ansätze zu entwickeln. Wir stellen einen Ansatz für die Identifizierung krankheitsrelevanter Genprodukte vor, der auf der Kombination von Proteininteraktionen, Proteinfunktionen und Netzwerkzentralitätsanalyse basiert. Gegeben einer Krankheit, werden krankheitsspezifische Netzwerke durch die Integration von direkt und indirekt interagierender Genprodukte und funktionalen Informationen generiert. Proteine in diesen Netzwerken werden anhand ihrer Zentralität sortiert. Das Einbeziehen indirekter Interaktionen verbessert die Identifizierung von Krankheitsgenen deutlich. Die Verwendung von vorhergesagten Proteinfunktionen verbessert das Ranking von krankheitsrelevanten Proteinen. / Protein interactions are essential to many aspects of cellular function. On the one hand, they reflect direct functional relationships. On the other hand, alterations in protein interactions perturb natural cellular processes and contribute to diseases. In this thesis we analyze both the functional and the pathological aspect of protein interactions to infer novel protein function for uncharacterized proteins and to associate yet uncharacterized proteins with disease phenotypes, respectively. Different experimental and computational approaches have been developed in the past to investigate the basic characteristics of proteins systematically. Yet, a substantial fraction of proteins remains uncharacterized, particularly in human. We present a novel approach to predict protein function from protein interaction networks of multiple species. The key to our method is to study proteins within modules defined by evolutionary conserved processes, combining comparative cross-species genomics with functional linkage in interaction networks. We show that integrating different evidence of functional similarity allows to infer novel functions with high precision and a very good coverage. Elucidating the pathological mechanisms is important for understanding the onset of diseases and for developing diagnostic and therapeutic approaches. We introduce a network-based framework for identifying disease-related gene products by combining protein interaction data and protein function with network centrality analysis. Given a disease, we compile a disease-specific network by integrating directly and indirectly linked gene products using protein interaction and functional information. Proteins in this network are ranked based on their network centrality. We demonstrate that using indirect interactions significantly improves disease gene identification. Predicted functions, in turn, enhance the ranking of disease-relevant proteins.

Edsger W. Dijkstra prägte im Jahr 1974 den Begriff Selbststabilisierung (self-stabilization) in der Informatik. Ein System ist selbststabilisierend, wenn es von jedem denkbaren Zustand aus nach einer endlichen Anzahl von Aktionen ein stabiles Verhalten erreicht. Im Mittelpunkt dieser Arbeit steht der Entwurf selbststabilisierender Algorithmen. Wir stellen eine Petrinetz-basierte Methode zum Entwurf selbststabilisierender Algorithmen vor. Wir validieren unsere Methode an mehreren Fallstudien: Ausgehend von algorithmischen Ideen existierender Algorithmen beschreiben wir jeweils die die schrittweise Entwicklung eines neuen Algorithmus. Dazu gehört ein neuer randomisierter selbststabilisierender Algorithmus zur Leader Election in einem Ring von Prozessoren. Dieser Algorithmus ist abgeleitet aus einem publizierten Algorithmus, von dem wir hier erstmals zeigen, daß er fehlerhaft arbeitet. Wir weisen die Speicherminimalität unseres Algorithmus nach. Ein weiteres Ergebnis ist der erste Algorithmus, der ohne Time-Out-Aktionen selbststabilisierenden Tokenaustausch in asynchronen Systemen realisiert. Petrinetze bilden einen einheitlichen formalen Rahmen für die Modellierung und Verifikation dieser Algorithmen. / In 1974, Edsger W. Dijkstra suggested the notion of self-stabilization. A system is self-stabilizing if regardless of the initial state it eventually reaches a stable behaviour. This thesis focuses on the design of self-stabilizing algorithms. We introduce a new Petri net based method for the design of self-stabilizing algorithms. We validate our method on several case studies. In each of the case studies, our stepwise design starts from an algorithmic idea and leads to a new self-stabilizing algorithm. One of these algorithms is a new randomized self-stabilizing algorithm for leader election in a ring of processors. This algorithm is derived from a published algorithm which we show to be incorrect. We prove that our algorithm is space-minimal. A further result is the first algorithm for token-passing in a asynchronous environment which works without time-out actions. Petri nets form a unique framework for modelling and verification of these algorithms.

In der Bioinformatik und der Next-Generation Sequenzierung benötigen wir oft große und komplexe Verarbeitungsabläufe um Daten zu analysieren. Die Werkzeuge und Bibliotheken, die hierin die Verarbeitungsschritte bilden, stammen aus unterschiedlichen Quellen und exponieren unterschiedliche Schnittstellen, was ihre Integration in Datenanalyseplattformen erschwert. Hinzu kommt, dass diese Verarbeitungsabläufe meist große Datenmengen prozessieren weshalb Forscher erwarten, dass unabhängige Verarbeitungsschritte parallel laufen. Der Stand der Technik im Feld der wissenschaftlichen Datenverarbeitung für Bioinformatik und Next-Generation Sequenzierung sind wissenschaftliche Workflowsysteme. Ein wissenschaftliches Workflowsystem erlaubt es Forschern Verarbeitungsabläufe als Workflow auszudrücken. Solch ein Workflow erfasst die Datenabhängigkeiten in einem Verarbeitungsablauf, integriert externe Software und erlaubt es unabhängige Verarbeitungsschritte zu erkennen, um sie parallel auszuführen. In dieser Arbeit präsentieren wir Cuneiform, eine Workflowsprache, und ihre verteilte Ausführungsumgebung. Für Cuneiform's Design nehmen wir die Perspektive der Programmiersprachentheorie ein. Wir lassen Methoden der funktionalen Programmierung einfließen um Komposition und Datenabhängigkeiten auszudrücken. Wir nutzen operationelle Semantiken um zu definieren, wann ein Workflow wohlgeformt und konsistent ist und um Reduktion zu erklären. Für das Design der verteilten Ausführungsumgebung nehmen wir die Perspektive der verteilten Systeme ein. Wir nutzen Petri Netze um die Kommunikationsstruktur der im System beteiligten Agenten zu erklären. / Bioinformatics and next-generation sequencing data analyses often form large and complex pipelines. The tools and libraries making up the processing steps in these pipelines come from different sources and have different interfaces which hampers integrating them into data analysis frameworks. Also, these pipelines process large data sets. Thus, users need to parallelize independent processing steps. The state of the art in large-scale scientific data analysis for bioinformatics and next-generation sequencing are scientific workflow systems. A scientific workflow system allows researchers to describe a data analysis pipeline as a scientific workflow which integrates external software, defines the data dependencies forming a data analysis pipeline, and parallelizes independent processing steps. Scientific workflow systems consist of a workflow language providing a user interface, and an execution environment. The workflow language determines how users express workflows, reuse and compose workflow fragments, integrate external software, how the scientific workflow system identifies independent processing steps, and how we derive optimizations from a workflow's structure. The execution environment schedules and runs data processing operations. In this thesis we present Cuneiform, a workflow language, and its distributed execution environment. For Cuneiform's design we take the perspective of programming languages. We adopt methods from functional programming towards composition and expressing data dependencies. We apply operational semantics and type systems to define well-formedness, consistency, and reduction of Cuneiform workflows. For the design of the distributed execution environment we take the perspective of distributed systems. We apply Petri nets to define the communication patterns among the distributed execution environment's agents.

Domänenspezifische Sprachen (DSLs) sind Software-Sprachen, die speziell für bestimmte Anwendungsdomänen entwickelt wurden. Mithilfe von DSLs können Domänenexperten ihr Domänenwissen auf einem hohen Abstraktionsniveau beschreiben. Wie andere Software-Sprachen auch, benötigen DSLs Sprachwerkzeuge, die Assistenz bei der Erstellung und Verarbeitung von domänenspezifischen Modellen bieten. Eine domänenspezifische Werkbank (DSW) ist ein Software-Werkzeug, welches mehrere solcher Sprachwerkzeuge für eine DSL miteinander integriert. Existierende Werkzeuge, die es erlauben eine DSW aufgrund der Beschreibung einer DSL automatisch generieren zu lassen, unterstützen jedoch nicht die Beschreibung und Generierung von editierbaren Sichten. Eine Sicht ist ein Teil einer DSW, der nur einen bestimmten Aspekt eines Modells darstellt. Diese Dissertation stellt spezielle Modelltransformationssprachen (MTLs) vor, mit denen die Synchronisation von Sichten in einer generierten DSW beschrieben werden kann. Dadurch können DSWs mit editierbaren Sichten mittels existierender Werkzeuge zur Generierung von Sprachwerkzeugen erstellt werden. Dafür wird eine DSW für die Nanophysik-Domäne sowie eine Taxonomie von Synchronisationstypen vorgestellt, welche es erlaubt genau zu bestimmen, welche Art von Modelltransformationen für die Synchronisation von Sichten in dieser Werkbank benötigt werden. Entsprechend dieser Anforderungen werden zwei MTLs entwickelt. Insbesondere wird eine bidirektionale MTL entwickelt. Mit solch einer Sprache kann man eine Relation, welche definiert ob zwei Modelle synchron sind, so beschreiben, dass die entsprechende Synchronisationslogik automatisch abgeleitet werden kann. Die gezeigten MTLs werden als interne DSLs - das heißt eingebettet als ausdrucksstarke Bibliotheken - in der Programmiersprache Scala implementiert. Auf diese Weise kann Scalas Typprüfung genutzt werden, um Transformationen und deren Komposition statisch zu verifizieren. / Domain-specific languages (DSLs) are software languages which are tailored to a specific application domain. DSLs enable domain experts to create domain-specific models, that is, high-level descriptions of domain knowledge. As any other software languages, DSLs rely on language tools which provide assistance for processing and managing domain-specific models. A domain-specific workbench is an integrated set of such tools for a DSL. A recently proposed approach is to automatically generate a domain-specific workbench for a DSL from a description of that DSL. However, existing tools which apply this approach do not support to describe and generate editable domain-specific views. A view is a part of domain-specific workbench that presents only one aspect of a model, for example, its hierarchical structure. This dissertation presents special model transformation languages which support the description of view synchronization in a generated domain-specific workbench. This allows a multi-view domain-specific workbench to be created with existing tools for language tool generation. We present a generated domain-specific workbench for the nanophysics domain and present a taxonomy of synchronization types. This allows us to precisely define what model transformations are required for view synchronization in that workbench. According to these requirements, we develop two transformation languages by adapting existing ones. In particular, we develop a bidirectional transformation language. With such a language one can describe a relation which defines whether two models are in sync and let the synchronization logic be inferred automatically. We implement model transformation languages as internal DSLs - that is, embedded as expressive libraries - in the Scala programming language and use Scala''s type checking for static verification of transformations and their composition.