Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-2671
Main Title: Accurate Prediction of Protein-Coding Genes with Discriminative Learning Techniques
Translated Title: Computer-gestützte Vorhersage protein-kodierender Gene mithilfe diskriminativer Lernmethoden
Author(s): Schweikert, Gabriele
Advisor(s): Rätsch, Gunnar
Granting Institution: Technische Universität Berlin, Fakultät IV - Elektrotechnik und Informatik
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Zur Zeit werden die Genome einer Vielzahl von Organismen vollständig sequenziert. Die vorliegende Arbeit hatte daher zum Ziel, eine neue, gleichermaßen effiziente wie genaue Methode zu entwickeln, die es erlaubt, Protein-kodierende Gene mit Hilfe eines Computer- Programms zu finden. Betrachtet wurden eukaryotische Genome, bei denen die Offenen Leserahmen der Gene durch nicht-kodierende Introns unterbrochen werden. Im Gegensatz zu den meisten bereits bestehenden Ansätzen wurden ausschliesslich diskriminative Lerntechniken verwendet, wodurch eine signifikante Steigerung der Vorhersagegenauigkeit erzielt werden konnte. Um die Segmentierung der DNA in kodierende und nicht-kodierende Abschnitte korrekt vorherzusagen, wurden hidden semi-Markov support vector machines (HSM-SVMs) trainiert. Die Anwendung dieser Technik auf Datensätze, die den Umfang und die Komplexit ̈at von genomweiten DNA-Sequenzen aufweisen, stellte allerdings eine erhebliche Herausforderung dar. Daher wurde ein zweistufiges Verfahren gewählt: Zunächst wurden mehrere unabhängige Teilprobleme gelöst — wie etwa die Erkennung von verschiedenen funktionalen Elementen und Signalen auf der DNA-Sequenz, z.B. von Promotoren oder Spleiß-Stellen. Zu diesem Zweck wurden support vector machines (SVMs) eingesetzt, die in der Lage sind, Informationen hoher Ordnung aus Millionen von Trainingsbeispielen zu nutzen. Anschließend wird die geeignete Gewichtung der einzelnen Komponenten mit Hilfe des HSM-SVM-Systems erlernt, so dass korrekte Genstrukturen bes- timmt werden können. Dadurch wird es möglich, tausende Beispiele in einer angemessenen Zeitspanne auszuwerten und dabei die Vielzahl verschlüsselter Informationen weitestgehend auszuschöpfen. Um den komplizierten Prozess der Genvorhersage quasi auf Knopfdruck durchführen zu können, wurde außerdem ein Webserver entwickelt. Dieser Dienst enthält die Option, Spezies-spezifische Modelle neu zu erzeugen. Mit dem resultierenden System mGene nahmen wir an einem internationalen Wettbewerb zur Genvorhersage teil. Eine unabhängige Evaluierung bewies die hohe Vorhersagequalität von mGene im Vergleich zu 47 eingereichten Datensätzen von 17 verschiedenen Gruppen: Unsere Beiträge erwiesen sich als die genauesten in sieben von insgesamt zwölf Evaluationskriterien, in weiteren drei Kriterien kamen sie auf den zweiten Platz. Nach dem Wettbewerb wurde mGene weiter verbessert, so dass Vorhersagen ermöglicht wurden, die sich als die genauesten in zehn von zwölf Evaluationskriterien etablierten. Infolgedessen wurden genomweite Vorhersagen für C. elegans erzeugt, wobei ca. 2000 Gene vorhergesagt wurden, die nicht in der aktuellen Annotation vorkamen. Bei der experimentellen Überprüfung dieser potentiell neuen Gene wurde eine sehr hohe Erfolgsrate erzielt. Diese Ergebnisse zeigen, dass sogar der Gen-Katalog von so intensiv untersuchten Organismen wie von C. elegans durch mGene-Vorhersagen verbessert werden kann. Schließlich wurden Genvorhersagen für vier weitere Nematoden generiert, für die zuvor keine ausreichenden Annotationen existierten. In diesem Zusammenhang, wurden auch Techniken untersucht, um ein auf einem bestimmten Organismus erlerntes Modell auf andere Genome zu übertragen. Erste Ergebnisse zeigen, dass die Genauigkeit für die Vorhersagen genomischer Signale auf diese Weise signifikant verbessert werden kann.
Nowadays, the sequences of complete genomes for more and more organisms arrive at great pace. The aim of this thesis was therefore, to develop a novel, efficient and accurate method for the detection of protein-coding genes by computational means. The focus was put on eukaryotic genomes, where the open reading frames of these genes are typically interrupted by non-coding introns. In contrast to most existing gene finders I created a purely discriminative system, thus achieving significant improvements in the accuracy of the predictions. In particular, the segmentation problem was solved with hidden semi-Markov support vector machines (HSM-SVMs), which have been shown to perform well on label sequence prediction tasks. However, applying this technique to data sets of the size and complexity of genomic-scale sequences posed a substantial challenge. It was solved by a two-step architecture: initially, the problem is partitioned into several independent sub-problems, namely the detection of signals on the genomic DNA induced by functional elements such as promoters or splice sites. For these tasks, support vector machines (SVMs) were used that are each capable of exploiting high-order information from millions of training examples. Subsequently, the integration and weighting of the individual components is efficiently learnt in the HSM-SVM framework. It is thus possible to process thousands of sequences in a reasonable time span, while taking full advantage of the wealth of encoded information. To aid the highly involved process of annotation, a web server was developed that allows to perform the complex process of gene prediction on the push of a button. This service includes optional re-training for species-specific models. With the gene finding system, mGene, we participated in an international gene prediction competition on the genome of the model organism C. elegans. An independent evaluation revealed mGene’s high prediction quality when compared to 47 submitted sets from 17 different groups: Our contributions were most accurate in seven out of twelve evaluation criteria, ranking second in three more measures. With further improvements to mGene, implemented after the competition, I created predictions that were most accurate according to 10 out of 12 evaluation criteria. I subsequently generated genome-wide predictions for C. elegans and predicted ≈ 2, 000 genes that were not contained in the current annotation. The expression of some of the potentially novel genes were tested by experiment, which showed a remarkably high success rate. These findings suggest that even the gene catalog of such a well-studied organism can be improved by mGene predictions. Finally, I predicted complete gene sets for four other nematodes, which previously lacked high quality annotations. In this context, I also investigated new techniques to adapt a learnt model for the prediction on related organisms. Initial results show that prediction accuracy can thus be improved significantly on various genomic signal prediction tasks.
URI: urn:nbn:de:kobv:83-opus-28603
http://depositonce.tu-berlin.de/handle/11303/2968
http://dx.doi.org/10.14279/depositonce-2671
Exam Date: 24-Nov-2010
Issue Date: 4-Jan-2011
Date Available: 4-Jan-2011
DDC Class: 004 Datenverarbeitung; Informatik
Subject(s): Domain adaptation
Genomannotation
Genvorhersage
Hidden Markov support vector machine
Maschinelles Lernen
Domain adaptation
Gene prediction
Genome annotation
Hidden Markov support vector machine
Machine learning
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Institut für Softwaretechnik und Theoretische Informatik » Publications

Files in This Item:
File Description SizeFormat 
Dokument_36.pdf37.35 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.