Proteins interacting with the genome, such as histones and transcription factors, play a major role in the regulation of gene expression. These interactions can be detected with ChIP-seq, which provides sequences of non- negative integers, called count signals, quantifying the presence of a given protein at each genomic locus. However, the computational analysis of count signals is challenging, as the biological patterns are complex and the datasets are large. In this thesis, we propose accurate and efficient algorithms for 3 different pattern detection problems in count signals. First, we present an algorithm that infers the genomic locations of positioned nucleosomes from histone ChIP-seq experiments. This method can integrate measurements for different histone marks and uses a wavelet to detect the count pattern corresponding to positioned nucleosomes. When compared with previous approaches using biological and simulated data, our method shows a higher precision and reduced runtimes. Next, we introduce an algorithm that annotates genomic regions according to the regulatory processes acting on them. The labels of this annotation, called chromatin states, are learned automatically from the measurements of multiple histone marks. Unlike previous approaches, our method characterizes chromatin states with a rigorous probabilistic model of the count signals. The resulting annotation is shown to be more strongly associated to DNA accessibility and transcription, as well as more robust and comprehensive compared to previous approaches. Lastly, we present an algorithm for finding transcription factor binding sites from ChIP- exo data (a method similar to ChIP-seq). Our algorithm learns the genomic sequences that attract the transcription factor (the motif) and the count pattern observable at binding sites (the footprint) at once. We show that our method finds the correct motif and detects interpretable footprints in 4 different datasets. Moreover, our approach can distinguish different categories of binding sites in the same experiment. Overall, the proposed algorithms represent an advancement in the automatic detection of biological patterns, as they are more accurate and in some cases considerably faster than existing approaches. Finally, they are based on a mathematical framework that is general and likely to be important for future research.
Proteine, die mit dem Genom interagieren, spielen eine wichtige Rolle in der Regulation der Genexpression. Diese Interaktionen können mit Hilfe sogenannter ChIP-seq Experimente detektiert werden. Die resultierenden Messungen lassen sich durch Sequenzen von nicht-negativen ganzen Zahlen darstellen, die Zählsignale genannt werden und die die Proteinmenge in jedem Lokus quantifizieren. Die Analyse dieser Signale wird jedoch im Allgemeinen durch die Komplexität der biologischen Muster und der Größe der Datensätze erschwert. In der vorliegenden Arbeit werden Algorithmen für drei Mustererkennungsprobleme in Zählsignalen vorgeschlagen. Als erstes wird ein Algorithmus präsentiert, der die Koordinaten gut positionierter Nukleosomen aus ChIP-seq Daten von Histonmodifikationen vorhersagt. Die vorgestellte Methode kann Messungen für verschiedene Histonmodifikationen integrieren und benutzt ein Wavelet um das Muster, das gut positionierten Nukleosomen entspricht, in dem Zählsignal zu erkennen. Ein Vergleich der vorgestellten Methode mit früheren Ansätzen auf biologischen sowie simulierten Daten zeigt, dass die neue Methode präziser und schneller ist. Der zweite vorgestellte Algorithmus annotiert Genomregionen nach den auf sie wirkenden genregulatorischen Prozessen. Die Kategorien dieser Annotation, die Chromatinzustände genannt werden, werden automatisch aus den Messungen von mehreren Histonmodifikationen gelernt. Die vorgestellte Methode bestimmt Chromatinzustände mit Hilfe eines exakten Modells der Zählsignale. Die so gelernte Annotation ist besser mit Daten zur Genomzugänglichkeit und Transkription assoziiert, so wie robuster und umfassender im Vergleich zu früheren Ansätzen. Als letztes wird ein Algorithmus beschrieben, der Bindungsstelle von Transktiptionsfaktoren aus einem ChIP-exo Experiment (eine ähnliche Methode wie ChIP-seq) vorhersagt. Der vorgestellte Algorithmus lernt gleichzeitig, welche Genomsequenzen die Transkriptionsfaktoren binden (das Motif) und welches Muster das Zählsignal an den Bindungsstellen zeigt (das Footprint). Auf vier unterschiedlichen Datensätzen wird gezeigt, dass die vorgestellte Methode immer das korrekte Motif und interpretierbare Footprints findet. Außerdem kann der vorgestellte Ansatz verschiedene Gruppen von Bindungsstellen in einem ChIP-exo Experiment erkennen. Zusammenfassend, präsentiert die vorliegende Arbeit Methoden, die die bestehenden verbessern und die als Startpunkt fuer künftige Ansätze dienen können.
