This dissertation presents a study of discriminative learning techniques for probabilistic sequence analysis that find application in pattern discovery of binding sites in nucleic acid sequences. Sets of positive and negative example sequences define contrasts that are mined for sequence motifs whose occurrence frequency varies between the sets. A discriminative motif discovery method based on hidden Markov models (HMMs) is described that allows choice of different objective functions, two of which are used for the first time for motif finding with HMMs: mutual information of condition and motif occurrence (MICO), and Matthews correlation coefficient. We perform an extensive and systematic comparison of motif discovery performance of our method and numerous published tools. Using MICO or several other of the implemented objective functions, our method’s performance exceeds that of all other tools. MICO is also the most generally useful discriminative objective function, as it is applicable both to the analysis of probabilistic as well as discrete binding motif models, can leverage contrasts of more than two conditions, and provides natural extensions to quantify conditional association that are used to build models of multiple motifs. The investigation concludes with several case studies comprising 30 datasets from transcriptome-scale technologies —ChIP-Seq, RIP-ChIP, and PAR-CLIP—of embryonic stem cell transcription factors and of RNA-binding proteins. The case studies demonstrate practicality and utility of the method, and validate it by reproducing motifs of well-studied proteins. In addition, they provide novel insights by connecting previously known splicing-relevant motifs to an alternative splicing regulator. The presented motif discovery method scales to large data sizes, makes use of available repeat experiments for increased statistical power, and aside from binary contrasts also more complex data configurations can be utilized. It is implemented in the open source software Discrover (portmanteau of discriminative and discover), and is available from https://github.com/maaskola/discrover.
Die Mustersuche in Sequenzdaten ist ein Standardproblem der Bioinformatik, der Anwendung von Rechenmethoden in der Biologie. Klassische Verfahren der Mustersuche stützen sich vorrangig auf Methoden des maschinellen Lernens, die üblicherweise auf probabilistischer Modellierung der Sequenzen basieren. Die Einführung neuer Methoden zur Sequenzierung von DNS und RNS im Laufe des letzten Jahrzehnts sorgt für eine Flut von Daten, die motivieren, innovative Lösungen zur automatisierten Analyse zu entwickeln. Die vorliegende Dissertation beschreibt eine Untersuchung diskriminativer Lernmethoden der Sequenzanalyse mit Anwendung zur Mustersuche in Nukleinsäuresequenzen. Der grundlegende Ansatz diskriminativer Verfahren zur Mustersuche besteht darin, solche Muster aufzuspüren, die in einem Satz von Sequenzen häufiger vorliegen als in einem anderen, oder deren Häufigkeit in mehreren Sequenzsätzen variiert. Es gibt vielfältige Maße zur Quantifizierung relativer Anreicherung solcher Art. Eine Anzahl von Publikationen beschreibt diskriminative Mustersuchmethoden, die sich nicht nur in der Wahl der Zielfunktion unterscheiden, sondern unter anderem auch in der Modellierung der Sequenzen, was es erschwert, die Nützlichkeit verschiedener Maße zu vergleichen. Diese Dissertation bespricht klassische Verfahren der Sequenzanalyse und beschreibt darauf aufbauend eine flexible Methode zur Mustersuche, die die Wahl verschiedener Zielfunktionen zulässt. Die Leistungsfähigkeit der verschiedenen Zielfunktionen in der beschriebenen Methode und der anderer, bereits publizierter Methoden wird sorgfältig analysiert mit Hilfe von umfassenden, synthetisch erzeugten Daten. Insbesondere erlaubt diese Auswertung auch den Vergleich der Vor- und Nachteile diskriminativer und nicht-diskriminativer Lernmethoden. Dabei stellt sich heraus, dass einige der in der vorliegend beschriebenen Methode implementierten diskriminativen Zielfunktionen wesentlich bessere Ergebnisse erzielen als bisher veröffentlichte Methoden. In der Fähigkeit Muster zu entdecken, sind einige der Zielfunktionen in der betrachteten Aufgabenstellung sehr nahe am theoretisch erreichbaren Optimum. Dies zeigt der Vergleich mit der Musterwiedererkennung, dem Bestimmen von Mustervorkommen, wenn das Muster bereits bekannt ist. Unter diesen Zielfunktionen sticht die gegenseitige Information (mutual information), ein Maß aus der Informationstheorie, heraus, da sie sich sowohl zur Optimierung probabilistischer, wie auch diskreter Sequenzmodelle eignet, sie die Analyse von Kontrasten mit mehr als zwei Bedingungen erlaubt, und sie außerdem geeignete Generalisierungen bietet um Modelle mehrerer Muster zu finden. Schließlich wird die Nützlichkeit und realistische Anwendbarkeit der vorgestellten Methode unter Verwendung der gegenseitigen Information dargestellt. Zahlreiche publizierte, mit unterschiedlichen Technologien erzeugte, biologische Datensätze werden analysiert. Dies umfasst Daten einer Familie von RNS-bindenden Proteinen in verschiedenen Spezies sowie Daten von Transkriptionsfaktoren, die von zentraler Bedeutung für die Regulation embryonaler Stammzellen höherer Säugetiere sind. Neue Erkentnisse ergeben sich für einen Alternative-Splicing-Faktor, für den Muster gefunden werden, die als Splicing-relevant bekannt sind, deren Bedeutung für den untersuchten Faktor allerdings bisher noch nicht vergleichbar gut belegt worden ist.
