Maschinelles Lernen zur Genom-Sequenzanalyse

Die Entwicklung neuer Sequenziertechnologien ebnete den Weg für kosteneffiziente Genomsequenzierung. Allein im Jahr 2008 werden etwa 250 neue Genome sequenziert. Es ist offensichtlich, dass diese gewaltigen Mengen an Daten effektive und genaue computer-gestützte Methoden zur Sequenzanalyse erfordern. Diese werden benötigt, um eines der wichtigsten Probleme der Bioinformatik zu lösen: die akkurate Lokalisation von Genen auf der DNA. In dieser Arbeit werden auf Basis von Support Vector Machines (SVMs) genaueste genomische Signalerkenner entwickelt, die in Gensuchmaschinen verwendet werden können. Die Arbeit untergliedert sich in folgende Themenschwerpunkte: String-Kerne Es wurden String-Kerne zur Detektion von Signalen auf dem Genom entwickelt und erweitert. Die Kerne haben eine in der Länge der Eingabesequenzen nur lineare Berechnungskomplexität und sind für eine Vielzahl von Problemen verwendbar. Dadurch gestaltet sich die Sequenzanalyse sehr effektiv: Mit nur geringem Vorwissen ist es möglich, geeignete String-Kernkombinationen auszuwählen, die hohe Erkennungsraten ermöglichen. Large-Scale-Lernen Das Training von SVMs war bisher zu rechenintensiv, um auf Daten genomischer Grösse angewendet zu werden. Mithilfe der in dieser Arbeit entwickelter Large-Scale-Lernmethoden ist es nun in kurzer Zeit möglich, string-kern-basierte SVMs auf bis zu zehn Millionen Sequenzen zu trainieren und auf über sechs Milliarden Sequenzpositionen vorherzusagen. Der entwickelte linadd-Ansatz beschleunigt die Berechnung von Linearkombinationen von String-Kernen, die bereits in linearer Zeit berechenbar sind. Dieser Ansatz ermöglicht den Verzicht auf einen Kern-Cache beim SVM-Training und führt somit zu einer drastischen Reduktion des Speicheraufwands. Interpretierbarkeit Ein häufig kritisierter Nachteil von SVMs mit komplexen Kernen ist, dass ihre Entscheidungsregeln für den Menschen schwer zu verstehen sind. In dieser Arbeit wird die "Black Box" der SVM-Klassifikatoren "geöffnet", indem zwei Konzepte entwickeln werden, die zu ihrem Verständnis beitragen: Multiple Kernel Learning (MKL) und Positional Oligomer Importance Matrices (POIMs). MKL ermöglicht die Interpretation von SVMs mit beliebigen Kernen und kann dazu verwendet werden heterogene Datenquellen zu fusionieren. POIMs sind besonders gut für String-Kerne geeignet, um die diskriminativsten Sequenzmotive zu bestimmen. Genom-Sequenzanalyse In dieser Arbeit werden SVMs mit neuentwickelten, sehr präzisen String-Kernen zur Detektion einer Vielzahl von Genom-Signalen, zum Beispiel der Transkriptionsstart- oder Spleissstellen, angewendet. Dabei werden unerreichte Genauigkeiten erzielt. Unter Verwendung von POIMs wurden die trainierten Klassifikatoren analysiert und unter anderem viele bereits bekannte Sequenzmuster gefunden. Die verbesserten Signaldetektoren wurden dann zur genauen Genstrukturvorhersage verwendet. Die Doktorarbeit schliesst mit einem Ausblick, wie in dieser Arbeit entwickelte Methoden die Basis für eine vollständige Gensuchmaschine legen.With the development of novel sequencing technologies, the way has been paved for cost efficient, high-throughput whole genome sequencing. In the year 2008 alone, about 250 genomes will have been sequenced. It is self-evident that the handling of this wealth of data requires efficient and accurate computational methods for sequence analysis. They are needed to tackle one of the most important problems in computational biology: the localisation of genes on DNA. In this thesis, I describe the development of state-of-the- art genomic signal detectors based on Support Vector Machines (SVM) that can be used in gene finding systems. The main contributions of this work can be summarized as follows: String Kernels We have developed and extended string kernels so that they are particularly well suited for the detection of genomic signals. These kernels are computationally very efficient - they have linear effort with respect to the length of the input sequences - and are applicable to a wide range of signal detection problems. Only little prior knowledge is needed to select a suitable string kernel combination for use in a classifier that delivers a high recognition accuracy. Large Scale Learning The training of SVMs used to be too computationally demand- ing to be applicable to datasets of genomic scale. We have developed large scale learning methods that enable the training of string kernel based SVMs using up to ten million instances and the application of the trained classifiers to six billions of instances within reasonable time. The proposed linadd approach speeds up the computation of linear combinations of already linear time string kernels. Due to its high efficiency, there is no need for kernel caches in SVM training. This leads to drastically reduced memory requirements. Interpretability An often criticised downside of SVMs with complex kernels is that it is very hard for humans to understand the learnt decision rules and to derive insight from them. We have opened the “black box” of SVM classifiers by developing two concepts helpful for their understanding: Multiple Kernel Learning (MKL) and Positional Oligomer Importance Matrices (POIMs). While MKL algorithms work with arbitrary kernels and are also useful in fusing heterogeneous data sources, POIMs are especially well suited for string kernels and the identification of the most discriminative sequence motifs. Genomic Sequence Analysis We have applied SVMs using novel string kernels to the detection of various genomic signals, like the transcription start and splice sites, outperforming state-of-the-art methods. Using POIMs, we analysed the trained classifiers, demonstrating the fidelity of POIMs by identifying, among others, many previously known functional sequence motifs. Finally, we have used the improved signal detectors to accurately predict gene structures. This thesis concludes with an outlook of how this framework prepares the ground for a fully fledged gene finding system outcompeting prior state-of-the-art methods