Logical Analysis of Biological Data

Abstract

Methods and models of machine learning have become indispensable for the analysis and interpretation of big data sets in the biomedical field. This work focuses on the machine learning method Logical Analysis of Data (LAD), which combines concepts from combinatorics, Boolean functions and optimization. LAD is based on the generation of patterns. These patterns are used to communicate relevant information and form theories, which are the classifiers for the prediction of new data points. This thesis makes contributions to practice, theory and applications of LAD. With regards to LAD practice, we present the design and development of our freely available software package AnswerSetLAD. In the implementation we make use of the declarative programming paradigm Answer Set Programming (ASP), which is oriented towards difficult combinatorial search and optimization problems. For that reason, it provides a perfectly suited framework for the LAD functionalities. In this thesis, we substantiate this statement with an empirical study on the running time of our ASP approach and a state-of-the-art Mixed-Integer Linear Programming (MILP) approach for the generation of maximal patterns, which are a specific type of LAD patterns. We present two theoretical advancements of LAD concerning prime patterns. This pattern type plays a key role in the LAD method. Firstly, we propose an algorithm for the enumeration of all prime patterns of a data set. The algorithm is preferable to classical methods in the case that the data set has a small maximal Hamming distance between the two classes of data points. Secondly, we investigate theories formed of prime patterns. Since the number of such prime theories for a data set is large in general, we define a statistical measure that can be used to rank prime patterns and, based on this, select those prime patterns that are more significant than others to form a theory. Finally, we illustrate two biological applications of LAD. In the first application, we use prime patterns to successfully identify protein interactions in a cell signaling network based on perturbation measurement data. The second application is located in the field of synthetic biology. Here we outline our approach of Boolean classifier generation out of miRNA data. These classifiers can be used for the assembly of in-vitro synthetic cell circuits to distinguish healthy from cancerous tissue.

Maschinelle Lernverfahren und Modelle sind für die Analyse und Interpretation großer Datensätze im biomedizinischen Bereich unverzichtbar geworden. In dieser Arbeit befassen wir uns mit der Logischen Analyse von Daten (LAD), einer Methode für maschinelles Lernen. LAD vereint Konzepte aus Kombinatorik, Booleschen Funktionen und Optimierung und basiert auf der Erzeugung von Mustern. Diese Muster werden dazu verwendet relevante Informationen zu kommunizieren und Theorien zu bilden, welche dazu genutzt werden können Vorhersagen für neue Datenpunkte zu treffen. Diese Arbeit liefert Beiträge zu Praxis, Theorie und Anwendungen von LAD. Im praktischen Teil der Arbeit stellen wir das Design und die Entwicklung unseres frei zugänglichen Software-Pakets AnswerSetLAD vor. Für die Implementierung nutzen wir das deklarative Programmierparadigma Answer Set Programming (ASP), welches auf schwierige kombinatorische Such- und Optimierungsprobleme ausgerichtet ist. Aus diesem Grund bietet es einen perfekt geeigneten Rahmen für die Implementierung der LAD Funktionalitäten. Wir untermauern diese Aussage innerhalb dieser Arbeit mit einem empirischen Vergleich zur Laufzeit unseres ASP und eines aktuell gebräuchlichen Mixed-Integer Linear Programming (MILP) Ansatzes zur Erzeugung maximaler Muster, einem speziellen Typ von LAD Mustern. Wir präsentieren zwei theoretische Weiterentwicklungen bezüglich Primmustern in LAD. Dieser Mustertyp spielt eine zentrale Rolle in der LAD Methode. Zunächst schlagen wir einen Algorithmus zur Aufzählung aller Primmuster eines Datensatzes vor, welcher besonders in dem Fall eine geringere Laufzeit als klassische Methoden aufweist, in dem der Datensatz einen kleinen maximalen Hamming-Abstand zwischen den beiden Klassen von Datenpunkten hat. Außerdem untersuchen wir Theorien, die aus Primmustern aufgebaut sind. Die Anzahl solcher Primtheorien für einen Datensatz ist im Allgemeinen groß. Wir definieren ein statistisches Maß, das es ermöglicht, bestimmte sinnvolle Theorien aus der Menge der Primtheorien auszuwählen. Abschließend zeigen wir zwei biologische Anwendungen von LAD. In der ersten Anwendung nutzen wir erfolgreich Primmuster um die Proteininteraktionen in einem Zellsignalnetzwerk basierend auf einem Perturbationsexperiment zu bestimmen. Die zweite Anwendung ist in der synthetischen Biologie angesiedelt. Hier erläutern wir unseren Ansatz zur Bestimmung Boolescher Klassifikatoren aus miRNA Daten. Diese Klassifikatoren können anschließend dazu genutzt werden um in-vitro synthetische Zellschaltkreise zu erzeugen, die gesundes von krebsbefallenem Gewebe unterscheiden können.