Eine der größten Herausforderungen in Data Science ist heutzutage, Daten miteinander in Beziehung zu setzen und ähnliche Daten zu finden. Hierzu kann der aus relationalen Datenbanken bekannte Join-Operator eingesetzt werden. Das Konzept der Ähnlichkeit wird häufig durch mengenbasierte Ähnlichkeitsfunktionen gemessen. Um solche Funktionen als Join-Prädikat nutzen zu können, setzt diese Arbeit voraus, dass Records aus Mengen von Tokens bestehen. Die Arbeit fokussiert sich auf den mengenbasierten Ähnlichkeitsjoin, Set Similarity Join (SSJ). Die Datenmenge, die es heute zu verarbeiten gilt, ist groß und wächst weiter. Der SSJ hingegen ist eine rechenintensive Operation. Um ihn auf großen Daten ausführen zu können, sind neue Ansätze notwendig. Diese Arbeit fokussiert sich auf das Mittel der Parallelisierung. Sie leistet folgende drei Beiträge auf dem Gebiet der SSJs. Erstens beschreibt und untersucht die Arbeit den aktuellen Stand paralleler SSJ-Ansätze. Diese Arbeit vergleicht zehn Map-Reduce-basierte Ansätze aus der Literatur sowohl analytisch als auch experimentell. Der größte Schwachpunkt aller Ansätze ist überraschenderweise eine geringe Skalierbarkeit aufgrund zu hoher Datenreplikation und/ oder ungleich verteilter Daten. Keiner der Ansätze kann den SSJ auf großen Daten berechnen. Zweitens macht die Arbeit die verfügbare hohe CPU-Parallelität moderner Rechner für den SSJ nutzbar. Sie stellt einen neuen daten-parallelen multi-threaded SSJ-Ansatz vor. Der vorgestellte Ansatz ermöglicht erhebliche Laufzeit-Beschleunigungen gegenüber der Ausführung auf einem Thread. Drittens stellt die Arbeit einen neuen hoch skalierbaren verteilten SSJ-Ansatz vor. Mit einer kostenbasierten Heuristik und einem daten-unabhängigen Skalierungsmechanismus vermeidet er Daten-Replikation und wiederholte Berechnungen. Der Ansatz beschleunigt die Join-Ausführung signifikant und ermöglicht die Ausführung auf erheblich größeren Datenmengen als bisher betrachtete parallele Ansätze. / One of today's major challenges in data science is to compare and relate data of similar nature. Using the join operation known from relational databases could help solving this problem. Given a collection of records, the join operation finds all pairs of records, which fulfill a user-chosen predicate. Real-world problems could require complex predicates, such as similarity. A common way to measure similarity are set similarity functions. In order to use set similarity functions as predicates, we assume records to be represented by sets of tokens. In this thesis, we focus on the set similarity join (SSJ) operation. The amount of data to be processed today is typically large and grows continually. On the other hand, the SSJ is a compute-intensive operation. To cope with the increasing size of input data, additional means are needed to develop scalable implementations for SSJ. In this thesis, we focus on parallelization. We make the following three major contributions to SSJ. First, we elaborate on the state-of-the-art in parallelizing SSJ. We compare ten MapReduce-based approaches from the literature analytically and experimentally. Their main limit is surprisingly a low scalability due to too high and/or skewed data replication. None of the approaches could compute the join on large datasets. Second, we leverage the abundant CPU parallelism of modern commodity hardware, which has not yet been considered to scale SSJ. We propose a novel data-parallel multi-threaded SSJ. Our approach provides significant speedups compared to single-threaded executions. Third, we propose a novel highly scalable distributed SSJ approach. With a cost-based heuristic and a data-independent scaling mechanism we avoid data replication and recomputation. A heuristic assigns similar shares of compute costs to each node. Our approach significantly scales up the join execution and processes much larger datasets than all parallel approaches designed and implemented so far.

Herzinsuffizienz ist ein klinisches Syndrom, welches durch funktionelle und strukturelle Anomalien des Herzens verursacht wird, und ist weltweit die häufigste Todesursache. Die dilatative Kardiomyopathie, welche durch eine Vergrößerung der linken Herzkammer definiert ist, und die arrhythmogene Kardiomyopathie, welche im Gegensatz durch eine Dysfunktion der rechten Herzkammer definiert ist, sind eine der häufigsten Ursachen für Herzinsuffizienz. Trotz vieler Bemühungen die molekularen Veränderungen der Herzinsuffizienz zu charakterisieren, sind Zelltypzusammensetzung, Genexpressionsänderungen, und zelluläre Interaktionen unter pathologischen Bedingungen unbekannt. Um diese Fragen zu adressieren wurde ein Protokoll zur Isolation intakter Zellkerne entwickelt um Einzelkernsequenzierung im Herzen durchzuführen. Anschließend wurde mit dem entwickelten Protokoll die zelluläre Zusammensetzung des erwachsenen gesunden menschlichen Herzens charakterisiert. Hier war mein Fokus die Charakterisierung und Identifikation von Subformen von Fibroblasten, und deren Genexpressionsunterschiede in den linken und rechten Vorhöfen und Herzkammern. Basierend auf dieser Annotation wurden die Zelltypen und Subtypen von ungefähr 900.000 Zellkernen von 61 nicht-ischämischen Herzinsuffizienzpatienten mit unterschliedlichen pathogenen Varianten in DCM- und ACM-assoziierten Genen oder idiopathischen Erkrankungen charakterisiert und mit 18 gesunden Spenderherzen verglichen. Dieser Datensatz zeigte spezifische Unterschiede des linken und rechten Ventrikels mit differenziell regulierten Genen und Signalwegen, and Veränderungen in der Zusammensetzung der verschiedenen Zelltypen und Subtypen. Um genotyp-spezifische Antworten unabhängig zu bestätigen wurden Algorithmen des maschinellen Lernens angewendet, welche die zugehörige Genotyp-Untergruppe des Patienten mit hoher Genauigkeit vorhersagten. Zusammenfassend stellen die in dieser Arbeit veröffentlichten Daten das vorherrschende Dogma in Frage, dass Herzinsuffizienz auf einen gemeinsamen finalen Signalweg zurückzuführen ist. / Heart failure is a clinical syndrom and leading cause of death worldwide, caused by functional and structural abnormalities of the heart. Dilated Cardiomyopathy, defined by a left ventricular enlargement, and arrhythmogenic cardiomyopathy, defined by a right ventricular dysfunction, are leading causes of heart failure. Despite previous efforts to characterise molecular changes in the failing heart, little is known on cell-type specific abundance and expression changes under pathological conditions, and how individual cell-types interact during heart failure and cardiac remodelling. To address this question, a protocol for the isolation of intact nuclei was firstly established to perform robust single-nucleus RNA sequencing in the heart. Next, the cell-type composition of the healthy adult human heart was characterised. Here my focus was on the fibroblast nieche by characterising fibroblast states, their composition and their atria- and ventricle-specific expression patterns. Cell type and state annotation was then used to characterize the transcriptome of roughly 900,000 nuclei from 61 failing, non-ischemic human hearts with distinct pathogenic variants in DCM and ACM genes or idiopathic disease and compared those to 18 healthy donor hearts. This dataset revealed distinct responses of the right and left ventricle with differently regulated genes and pathways, and compositional changes across cell types and states. To independently confirm genotype-specific responses, machine learning approaches were applied, predicting genotype subgroups with high accuracy. Taken together, the findings published in this thesis upend the prevalent dogma that heart failure results in a final common pathway.

Process Mining ermöglicht die Analyse von Event Logs. Jede Aktivität ist durch ein Event in einem Trace recorded, welcher jeweils einer Prozessinstanz entspricht. Traces können sensible Daten, z.B. über Patienten enthalten. Diese Dissertation adressiert Datenschutzrisiken für Trace Daten und Process Mining. Durch eine empirische Studie zum Re-Identifikations Risiko in öffentlichen Event Logs wird die hohe Gefahr aufgezeigt, aber auch weitere Risiken sind von Bedeutung. Anonymisierung ist entscheidend um Risiken zu adressieren, aber schwierig weil gleichzeitig die Verhaltensaspekte des Event Logs erhalten werden sollen. Dies führt zu einem Privacy-Utility-Trade-Off. Dieser wird durch neue Algorithmen wie SaCoFa und SaPa angegangen, die Differential Privacy garantieren und gleichzeitig Utility erhalten. PRIPEL ergänzt die anonymiserten Control-flows um Kontextinformationen und ermöglich so die Veröffentlichung von vollständigen, geschützten Logs. Mit PRETSA wird eine Algorithmenfamilie vorgestellt, die k-anonymity garantiert. Dafür werden privacy-verletztende Traces miteinander vereint, mit dem Ziel ein möglichst syntaktisch ähnliches Log zu erzeugen. Durch Experimente kann eine bessere Utility-Erhaltung gegenüber existierenden Lösungen aufgezeigt werden. / Process mining analyzes business processes using event logs. Each activity execution is recorded as an event in a trace, representing a process instance's behavior. Traces often hold sensitive info like patient data. This thesis addresses privacy concerns arising from trace data and process mining. A re-identification risk study on public event logs reveals high risk, but other threats exist. Anonymization is vital to address these issues, yet challenging due to preserving behavioral aspects for analysis, leading to a privacy-utility trade-off. New algorithms, SaCoFa and SaPa, are introduced for trace anonymization using noise for differential privacy while maintaining utility. PRIPEL supplements anonymized control flows with trace contextual info for complete protected logs. For k-anonymity, the PRETSA algorithm family merges privacy-violating traces based on a prefix representation of the event log, maintaining syntactic similarity. Empirical evaluations demonstrate utility improvements over existing techniques.

Next-generation sequencing (NGS) ermöglicht das molekulare Profiling von Zellen mit beispiellos hohem Durchsatz. Allerdings ist der Fokus oftmals auf proteinkodierende Proteine beschränkt, wodurch die vollständige Diversität des Transkriptoms übersehen wird. Nicht-kodierende RNA-Moleküle variieren stark in ihrer Biogenese, Struktur und Funktion, wodurch ihre unverzerrte Inklusion in die Analyse erschwert wird. Diese Promotion fokussiert sich auf das Verständnis nicht-kodierender RNA und navigiert durch drei aufeinander aufbauende Säulen in der Analyse, um Beobachtungen in Wissen zu verwandeln: Generierung von Daten, Quantifizierung und Interpretation. Diese drei Säulen werden in den drei Kapiteln der Dissertation aus der bioinformatischen Perspektive adressiert, indem Schlüsselherausforderungen beschrieben und neue Lösungen vorgestellt werden, um die Analyse des gesamten Transkriptoms mit NGS-Techniken zu verbessern. Zunächst wird ein vollautomatischer Algorithmus vorgestellt, welcher die verschiedenen Quellen von aus der Vorberei- tung von Bibliotheken resultierenden Artefakten mittels unüberwachtes Lernen erkennt, was anschließend zur Optimierung der Protokolle zur Vorbereitung von total-RNA-seq-Bibliotheken genutzt werden kann. Zudem werden die primären Herausforderungen der Quantifizierung von total-RNA-seq behandelt: die Prozessierung von Reads, die mehreren, möglicherweise überlappenden Loci zugeordnet werden können, wie auch die Tatsache, dass manche Loci mehrfach im Genom vorkommen und ein Read zu all diesen Loci passen kann. Diese beiden Fälle können auch gleichzeitig vorkommen, was die Analyse von nicht-kodierender RNA mit üblichen Methoden erschwert. Um diese Problematik anzugehen, wird eine neue Software namens Multi-Graph count (MGcount) vorgestellt. Diese ordnet hierarchisch Reads Transkripten zu, um unter anderem eine Diskrepanz zwischen der Loci-Länge von small und long RNA zu berücksichtigen. Wenn Reads konsistent mehrfach alignieren, fasst MGcount Loci in Communitys zusammen. Es wird gezeigt, dass die Beurteilung der Expression auf der Community-Ebene eine genauere Quantifizierung von biologisch bedeutsamen RNA-Einheiten (Einfachtranskript oder Locusfamilien) ermöglicht. Schließlich wird MGcount angewandt, um nicht-kodierende RNA während der Differenzierung von induzierten pluripotenten Stammzellen in die Keimblätter Mesoderm, Endoderm und Ektoderm zu analysieren. In dieser Dissertation wird eine Multi-Omics-Analyse erfolgreich angewandt, um sowohl die Expressionsverläufe von verschiedenen RNA-Biotypen während der Determination zu charakterisieren als auch einen Zusammenhang bezüglich Chromatin-Remodellierung (“chromatin remodeling“) und DNA-Methylierung an den jeweiligen Loci herzustellen. Schlussendlich dient diese Dissertation als Ratgeber für alle Forschenden, die neue Einsichten in das nicht-kodierende Transkriptom gewinnen wollen. / Next-generation sequencing (NGS) techniques enable the molecular profiling of cells with unprecedented high throughput. Yet, in transcriptome analysis, the focus is often restricted to protein-coding RNA, overlooking the transcriptome in its entire diversity. Non-coding RNA molecules largely vary in biogenesis, structure and function and this challenges their unbiased inclusion into the analyses. This doctoral research places non-coding RNA understanding at the focus spot and navigates through the three workflow pillars that must align effectively to turn observations into knowledge: data generation, quantification, and interpretation. Throughout three chapters, this Thesis addresses these pillars from a Bioinformatics perspective, by outlining key challenges and introducing novel solutions to improve whole-transcriptome analysis through NGS techniques. First, we introduce a fully automatic algorithm that identifies sources of library preparation artifacts in an unsupervised manner and we demonstrate its utility within the development and optimization of total-RNA-seq library preparation protocols. Secondly, we address a major challenge in total-RNA-seq quantification; processing reads that align to multiple loci that overlap within the same genomic region or/and multiple loci that are present in high copy numbers. Such ambiguous alignments commonly arise due to the inherent characteristics of non-coding RNA. To tackle this, we introduce a novel software, named Multi-Graph count (MGcount), that hierarchically assigns reads to transcripts to account for loci length disparity between small-RNA and long-RNA and subsequently collapses loci where reads consistently multi-map into communities defined in a data-driven fashion. We show that these cohesive communities allow the quantification of biologically meaningful RNA entities (single-transcripts or locus-families) and estimate their abundance more accurately. Finally, we apply the developed method to investigate non-coding RNA in early development, specifically during the differentiation of Induced Pluripotent Stem Cells into the three germ-layer lineages, namely, mesoderm, endoderm, and ectoderm. In this study, we leverage a multi-omics analysis to characterize the expression trajectories of diverse RNA biotypes along cell-commitment and the interplay with chromatin remodeling and DNA methylation patterns at the locus surroundings. Ultimately, this work is intended to serve as a guide for all those who want to gain new insights from the non-coding transcriptome.

Bakterielle Wirte wie Escherichia coli dienen der Produktion industrieller rekombinanter Proteine. Dieser Prozess verursacht systemischen Stress und führt zu umfangreichen Veränderungen in mRNA- und Proteinexpression. In meiner Arbeit analysiere ich Regulationsmechanismen der zellulären Reaktion auf diesen Stress. Zudem untersuche ich die zelluläre Ressourcenallokation mittels eines stationären Ganzzellmodells von E. coli, basierend auf der Resource Balance Analysis. Das Modell berücksichtigt Kosten zellulärer Prozesse und Einschränkungen wie Energie, Effizienz und Raum. Es unterstützt die Experimentplanung in der Bioproduktion. Weiterhin habe ich an der Entwicklung von RBApy mitgewirkt, einer Software zur Erstellung und Simulation von RBA-Modellen. Schließlich entwickle ich ein Modell zur Untersuchung der Regulation von Stressreaktionen durch die Tendenz der Zelle, wachstumsoptimale Ressourcenstrategien anzuwenden. Das Modell berücksichtigt zelluläre Beschränkungen und zeigt, dass die erhaltene Stressreaktion der experimentell ermittelten Reaktion ähnelt. Die Integration von Ressourcenzuteilung in Zellmodelle ermöglicht Einsichten in regulatorische Ereignisse und Anpassungen während der Bioproduktion, was zur Optimierung der rekombinanten Proteinexpression in Escherichia coli beiträgt. / Bacterial hosts such as Escherichia coli are used for the production of industrial recombinant proteins. This process causes systemic stress and leads to extensive changes in mRNA and protein expression. In my work, I analyze regulatory mechanisms of the cellular response to this stress. In addition, I investigate cellular resource allocation using a steady-state whole-cell model of E. coli based on resource balance analysis. The model accounts for costs of cellular processes and constraints such as energy, efficiency, and space. It supports experiment design in bioproduction. Furthermore, I contributed to the development of RBApy, a software to create and simulate RBA models. Finally, I developed a model to study the regulation of stress responses by the tendency of the cell to adopt growth-optimal resource strategies. The model accounts for cellular constraints and shows that the obtained stress response resembles the experimentally determined response. Integrating resource allocation into cell models provides insights into regulatory events and adaptations during bioproduction, which contributes to the optimization of recombinant protein expression in Escherichia coli.

Erfolgreiche Unternehmen denken intensiv über den eigentlichen Nutzen ihres Unternehmens für Kunden nach. Diese versuchen, ihrer Konkurrenz voraus zu sein, und zwar durch gute Ideen, Innovationen und Kreativität. Dabei wird Erfolg anhand von Metriken gemessen, wie z.B. der Anzahl der loyalen Kunden oder der Anzahl der Käufer. Gegeben, dass der Wettbewerb durch die Globalisierung, Deregulierung und technologische Innovation in den letzten Jahren angewachsen ist, spielen die richtigen Entscheidungen für den Erfolg gerade im operativen Geschäft der sämtlichen Bereiche des Unternehmens eine zentrale Rolle. Vor diesem Hintergrund entstammen die in der vorliegenden Arbeit zur Evaluation der Methoden des maschinellen Lernens untersuchten Entscheidungsprobleme vornehmlich der Entscheidungsunterstützung. Hierzu gehören Klassifikationsprobleme wie die Kreditwürdigkeitsprüfung im Bereich Credit Scoring und die Effizienz der Marketing Campaigns im Bereich Direktmarketing. In diesem Kontext ergaben sich Fragestellungen für die korrelativen Modelle, nämlich die Untersuchung der Eignung der Verfahren des maschinellen Lernens für den Bereich des Credit Scoring, die Kalibrierung der Wahrscheinlichkeiten, welche mithilfe von Verfahren des maschinellen Lernens erzeugt werden sowie die Konzeption und Umsetzung einer Synergie-Heuristik zwischen den Methoden der klassischen Statistik und Verfahren des maschinellen Lernens. Desweiteren wurden kausale Modelle für den Bereich Direktmarketing (sog. Uplift-Effekte) angesprochen. Diese Themen wurden im Rahmen von breit angelegten empirischen Studien bearbeitet. Zusammenfassend ergibt sich, dass der Einsatz der untersuchten Verfahren beim derzeitigen Stand der Forschung zur Lösung praxisrelevanter Entscheidungsprobleme sowie spezifischer Fragestellungen, welche aus den besonderen Anforderungen der betrachteten Anwendungen abgeleitet wurden, einen wesentlichen Beitrag leistet. / Nowadays right decisions, being it strategic or operative, are important for every company, since these contribute directly to an overall success. This success can be measured based on quantitative metrics, for example, by the number of loyal customers or the number of incremental purchases. These decisions are typically made based on the historical data that relates to all functions of the company in general and to customers in particular. Thus, companies seek to analyze this data and apply obtained knowlegde in decision making. Classification problems represent an example of such decisions. Classification problems are best solved, when techniques of classical statistics and these of machine learning are applied, since both of them are able to analyze huge amount of data, to detect dependencies of the data patterns, and to produce probability, which represents the basis for the decision making. I apply these techniques and examine their suitability based on correlative models for decision making in credit scoring and further extend the work by causal predictive models for direct marketing. In detail, I analyze the suitability of techniques of machine learning for credit scoring alongside multiple dimensions, I examine the ability to produce calibrated probabilities and apply techniques to improve the probability estimations. I further develop and propose a synergy heuristic between the methods of classical statistics and techniques of machine learning to improve the prediction quality of the former, and finally apply conversion models to turn machine learning techqiques to account for causal relationship between marketing campaigns and customer behavior in direct marketing. The work has shown that the techniques of machine learning represent a suitable alternative to the methods of classical statistics for decision making and should be considered not only in research but also should find their practical application in real-world practices.

Die Psychologie und andere empirische Wissenschaften befinden sich in einer Krise, da vielen Forschenden bewusst geworden ist, dass viele Erkenntnisse nicht so stark empirisch gestützt sind, wie sie einst glaubten. Es wurden mehrere Ursachen dieser Krise vorgeschlagen: Missbrauch statistischer Methoden, soziologische Verzerrungen und schwache Theorien. In dieser Dissertation gehe ich davon aus, dass ungenaue Theorien unvermeidlich sind, diese aber mithilfe von Induktion einer empirischen Prüfung unterzogen werden können. Anhand von Daten können Theorien ergänzt werden, sodass präzise Vorhersagen möglich sind, die sich mit der Realität vergleichen lassen. Eine solche Strategie ist jedoch mit Kosten verbunden. Induktion ist daher zwar notwendig, aber führt zu einem übermäßigen Vertrauen in empirische Befunde. Um empirische Ergebnisse adäquat zu bewerten, muss diese Verzerrung berücksichtigt werden. Das Ausmaß der Verzerrung hängt von den Eigenschaften des induktiven Prozesses ab. Einige induktive Prozesse können vollständig transparent gemacht werden, sodass ihre Verzerrung angemessen berücksichtigt werden kann. Ich zeige, dass dies bei Induktion der Fall ist, die beliebig mit anderen Daten wiederholt werden kann, was die Bedeutung von computergestützter Reproduzierbarkeit unterstreicht. Induktion, die die Forschenden und ihr kognitives Modell einbezieht, kann nicht beliebig wiederholt werden; daher kann die Verzerrung durch Induktion nur mit Unsicherheit beurteilt werden. Ich schlage vor, dass die Verringerung dieser Unsicherheit das Ziel von Präregistrierung sein sollte. Nachdem ich die Ziele von Reproduzierbarkeit und Präregistrierung unter dem Gesichtspunkt der Transparenz über Induktion präzisiert habe, gebe ich in den wissenschaftlichen Artikeln, die als Teil der Dissertation veröffentlicht wurden, Empfehlungen für die praktische Umsetzung beider Verfahren. / Psychology and other empirical sciences are in the middle of a crisis, as many researchers have become aware that many findings do not have as much empirical support as they once believed. Several causes of this crisis have been suggested: misuse of statistical methods, sociological biases, and weak theories. This dissertation proposes the following rationale: to some extent, imprecise theories are unavoidable, but they still can be subjected to an empirical test by employing induction. Data may be used to amend theories, allowing precise predictions that can be compared to reality. However, such a strategy comes at a cost. While induction is necessary, it causes overconfidence in empirical findings. When assessing findings, this overconfidence must be taken into account. The extent of the overconfidence depends on the properties of the inductive process. Some inductive processes can be made fully transparent, so their bias can be accounted for appropriately. I show that this is the case for induction that can be repeated at will on other data, highlighting the importance of computational reproducibility. Induction involving the researcher and their cognitive model can not be repeated; hence, the extent of overconfidence must be judged with uncertainty. I propose that reducing this uncertainty should be the objective of preregistration. Having explicated the goals of computational reproducibility and preregistration from a perspective of transparency about induction in the synopsis, I put forward recommendations for the practice of both in the articles published as part of this dissertation.

Einzelzell-Omics-Daten stehen derzeit im Fokus der Entwicklung computergestützter Methoden in der Molekularbiologie und Genetik. Einzelzellexperimenten lieferen dünnbesetzte, hochdimensionale Daten über zehntausende Gene oder hunderttausende regulatorische Regionen in zehntausenden Zellen. Diese Daten bieten den Forschenden die Möglichkeit, Gene und regulatorische Regionen zu identifizieren, welche die Bestimmung und Aufrechterhaltung der Zellidentität koordinieren. Die gängigste Strategie zur Identifizierung von Zellidentitätsmarkern besteht darin, die Zellen zu clustern und dann Merkmale zu finden, welche die Cluster unterscheiden, wobei davon ausgegangen wird, dass die Zellen innerhalb eines Clusters die gleiche Identität haben. Diese Annahme ist jedoch nicht immer zutreffend, insbesondere nicht für Entwicklungsdaten bei denen sich die Zellen in einem Kontinuum befinden und die Definition von Clustergrenzen biologisch gesehen potenziell willkürlich ist. Daher befasst sich diese Dissertation mit Clustering-unabhängigen Strategien zur Identifizierung von Markern aus Einzelzell-Omics-Daten. Der wichtigste Beitrag dieser Dissertation ist SEMITONES, eine auf linearer Regression basierende Methode zur Identifizierung von Markern. SEMITONES identifiziert (Gruppen von) Markern aus verschiedenen Arten von Einzelzell-Omics-Daten, identifiziert neue Marker und übertrifft bestehende Marker-Identifizierungsansätze. Außerdem ermöglicht die Identifizierung von regulatorischen Markerregionen durch SEMITONES neue Hypothesen über die Regulierung der Genexpression während dem Erwerb der Zellidentität. Schließlich beschreibt die Dissertation einen Ansatz zur Identifizierung neuer Markergene für sehr ähnliche, dennoch underschiedliche neurale Vorlauferzellen im zentralen Nervensystem von Drosphila melanogaster. Ingesamt zeigt die Dissertation, wie Cluster-unabhängige Ansätze zur Aufklärung bisher uncharakterisierter biologischer Phänome aus Einzelzell-Omics-Daten beitragen. / Single-cell omics approaches are the current frontier of computational method development in molecular biology and genetics. A single single-cell experiment provides sparse, high-dimensional data on tens of thousands of genes or hundreds of thousands of regulatory regions (i.e. features) in tens of thousands of cells (i.e. samples). This data provides researchers with an unprecedented opportunity to identify those genes and regulatory regions that determine and coordinate cell identity acquisition and maintenance. The most common strategy for identifying cell identity markers consists of clustering the cells and then identifying differential features between these clusters, assuming that cells within a cluster share the same identity. This assumption is, however, not guaranteed to hold, particularly for developmental data where cells lie along a continuum and inferring cluster boundaries becomes non-trivial and potentially biologically arbitrary. In response, this thesis presents clustering-independent strategies for marker feature identification from single-cell omics data. The primary contribution of this thesis is a linear regression-based method for marker feature identification from single-cell omics data called SEMITONES. SEMITONES can identify markers or marker sets from diverse single-cell omics data types, identifies novel markers, outperforms existing marker identification approaches. The thesis also describes how the identification of marker regulatory regions by SEMITONES enables the generation of novel hypotheses regarding gene regulation during cell identity acquisition. Lastly, the thesis describes the clustering-independent identification of novel marker genes for highly similar yet distinct neural progenitor cells in the Drosophila melanogaster central nervous system. Altogether, the thesis demonstrates how clustering-independent approaches aid the elucidation of yet uncharacterised biological patterns from single cell-omics data.

Die Recurrence Quantification Analysis (RQA) ist eine Methode aus der nicht-linearen Zeitreihenanalyse. Im Mittelpunkt dieser Methode steht die Auswertung des Inhalts sogenannter Rekurrenzmatrizen. Bestehende Berechnungsansätze zur Durchführung der RQA können entweder nur Zeitreihen bis zu einer bestimmten Länge verarbeiten oder benötigen viel Zeit zur Analyse von sehr langen Zeitreihen. Diese Dissertation stellt die sogenannte skalierbare Rekurrenzanalyse (SRA) vor. Sie ist ein neuartiger Berechnungsansatz, der eine gegebene Rekurrenzmatrix in mehrere Submatrizen unterteilt. Jede Submatrix wird von einem Berechnungsgerät in massiv-paralleler Art und Weise untersucht. Dieser Ansatz wird unter Verwendung der OpenCL-Schnittstelle umgesetzt. Anhand mehrerer Experimente wird demonstriert, dass SRA massive Leistungssteigerungen im Vergleich zu existierenden Berechnungsansätzen insbesondere durch den Einsatz von Grafikkarten ermöglicht. Die Dissertation enthält eine ausführliche Evaluation, die den Einfluss der Anwendung mehrerer Datenbankkonzepte, wie z.B. die Repräsentation der Eingangsdaten, auf die RQA-Verarbeitungskette analysiert. Es wird untersucht, inwiefern unterschiedliche Ausprägungen dieser Konzepte Einfluss auf die Effizienz der Analyse auf verschiedenen Berechnungsgeräten haben. Abschließend wird ein automatischer Optimierungsansatz vorgestellt, der performante RQA-Implementierungen für ein gegebenes Analyseszenario in Kombination mit einer Hardware-Plattform dynamisch bestimmt. Neben anderen Aspekten werden drastische Effizienzgewinne durch den Einsatz des Optimierungsansatzes aufgezeigt. / Recurrence quantification analysis (RQA) is a method from nonlinear time series analysis. It relies on the identification of line structures within so-called recurrence matrices and comprises a set of scalar measures. Existing computing approaches to RQA are either not capable of processing recurrence matrices exceeding a certain size or suffer from long runtimes considering time series that contain hundreds of thousands of data points. This thesis introduces scalable recurrence analysis (SRA), which is an alternative computing approach that subdivides a recurrence matrix into multiple sub matrices. Each sub matrix is processed individually in a massively parallel manner by a single compute device. This is implemented exemplarily using the OpenCL framework. It is shown that this approach delivers considerable performance improvements in comparison to state-of-the-art RQA software by exploiting the computing capabilities of many-core hardware architectures, in particular graphics cards. The usage of OpenCL allows to execute identical SRA implementations on a variety of hardware platforms having different architectural properties. An extensive evaluation analyses the impact of applying concepts from database technology, such memory storage layouts, to the RQA processing pipeline. It is investigated how different realisations of these concepts affect the performance of the computations on different types of compute devices. Finally, an approach based on automatic performance tuning is introduced that automatically selects well-performing RQA implementations for a given analytical scenario on specific computing hardware. Among others, it is demonstrated that the customised auto-tuning approach allows to considerably increase the efficiency of the processing by adapting the implementation selection.

Frequent itemset mining is an important building block in many data mining applications like market basket analysis, recommendation, web-mining, fraud detection, and gene expression analysis. In many of them, the datasets being mined can easily grow up to hundreds of gigabytes or even terabytes of data. Hence, efficient algorithms are required to process such large amounts of data. In recent years, there have been many frequent-itemset mining algorithms proposed, which however (1) often have high memory requirements and (2) do not exploit the large degrees of parallelism provided by modern multiprocessor systems. The high memory requirements arise mainly from inefficient data structures that have only been shown to be sufficient for small datasets. For large datasets, however, the use of these data structures force the algorithms to go out-of-core, i.e., they have to access secondary memory, which leads to serious performance degradations. Exploiting available parallelism is further required to mine large datasets because the serial performance of processors almost stopped increasing. Algorithms should therefore exploit the large number of available threads and also the other kinds of parallelism (e.g., vector instruction sets) besides thread-level parallelism. In this work, we tackle the high memory requirements of frequent itemset mining twofold: we (1) compress the datasets being mined because they must be kept in main memory during several mining invocations and (2) improve existing mining algorithms with memory-efficient data structures. For compressing the datasets, we employ efficient encodings that show a good compression performance on a wide variety of realistic datasets, i.e., the size of the datasets is reduced by up to 6.4x. The encodings can further be applied directly while loading the dataset from disk or network. Since encoding and decoding is repeatedly required for loading and mining the datasets, we reduce its costs by providing parallel encodings that achieve high throughputs for both tasks. For a memory-efficient representation of the mining algorithms’ intermediate data, we propose compact data structures and even employ explicit compression. Both methods together reduce the intermediate data’s size by up to 25x. The smaller memory requirements avoid or delay expensive out-of-core computation when large datasets are mined. For coping with the high parallelism provided by current multiprocessor systems, we identify the performance hot spots and scalability issues of existing frequent-itemset mining algorithms. The hot spots, which form basic building blocks of these algorithms, cover (1) counting the frequency of fixed-length strings, (2) building prefix trees, (3) compressing integer values, and (4) intersecting lists of sorted integer values or bitmaps. For all of them, we discuss how to exploit available parallelism and provide scalable solutions. Furthermore, almost all components of the mining algorithms must be parallelized to keep the sequential fraction of the algorithms as small as possible. We integrate the parallelized building blocks and components into three well-known mining algorithms and further analyze the impact of certain existing optimizations. Our algorithms are already single-threaded often up an order of magnitude faster than existing highly optimized algorithms and further scale almost linear on a large 32-core multiprocessor system. Although our optimizations are intended for frequent-itemset mining algorithms, they can be applied with only minor changes to algorithms that are used for mining of other types of itemsets.