Accurate prediction of protein-coding genes with discriminative learning techniques [Elektronische Ressource] / vorgelegt von Gabriele Schweikert

Sujets

• Informatik

Informations

• Publié par: technische_universitat_berlin
• Publié le: 01 janvier 2010
• Nombre de lectures: 12
• Langue: English
• Poids de l'ouvrage: 36 Mo

Extrait

Accurate Prediction of Protein-Coding Genes
with Discriminative Learning Techniques
vorgelegt von
Diplom-Physikerin
Gabriele Beate Schweikert
aus Heidenheim a.d. Brenz
Von der Fakult at IV | Elektrotechnik und Informatik
der Technischen Universit at Berlin
zur Erlangung des akademischen Grades eines
Doktor der Naturwissenschaften
Dr. rer. nat.
genehmigte Dissertation
Promotionsausschuss:
Vorsitzender: Prof. Dr. Manfred Opper
Berichter: Dr. Gunnar R atsch
Berichter: Prof. Dr. Klaus-Robert Muller
Berichter: Prof. Dr. Bernhard Sch olkopf
Tag der mundlic hen Aussprache: 24.11.2010
Berlin 2010
D 83Erklarung
Hiermit erkl are ich, dass ich diese Schrift selbst andig und nur mit den angege-
benen Hilfsmitteln angefertigt habe und dass alle Stellen, die im Wortlaut oder dem
Sinne nach anderen Werken entnommen sind, durch Angaben der Quellen kenntlich
gemacht sind.
G ottingen, 2010 Gabriele SchweikertFur AntoniaAbstract
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, e cient and ac-
curate 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 nders, I
created a purely discriminative system, thus achieving signi cant improvements in the ac-
curacy 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 e ciently 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-speci c models.
With the gene nding system, mGene, we participated in an international gene pre-
diction 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 di erent 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 accu-
rate 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 ndings 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 signi cantly on various genomic signal prediction tasks.
vZusammenfassung
Zur Zeit werden die Genome einer Vielzahl von Organismen vollst andig sequenziert. Die
vorliegende Arbeit hatte daher zum Ziel, eine neue, gleicherma en e ziente wie genaue
Methode zu entwickeln, die es erlaubt, Protein-kodierende Gene mit Hilfe eines Computer-
Programms zu nden. Betrachtet wurden eukaryotische Genome, bei denen die O enen
Leserahmen der Gene durch nicht-kodierende Introns unterbrochen werden. Im Gegen-
satz zu den meisten bereits bestehenden Ansatzen wurden ausschliesslich diskriminative
Lerntechniken verwendet, wodurch eine signi kante 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 atze, die den Um-
fang und die Komplexit at von genomweiten DNA-Sequenzen aufweisen, stellte allerdings
eine erhebliche Herausforderung dar. Daher wurde ein zweistu ges Verfahren gewah lt:
Zun achst wurden mehrere unabh angige Teilprobleme gel ost | wie etwa die Erkennung von
verschiedenen funktionalen Elementen und Signalen auf der DNA-Sequenz, z.B. von Pro-
motoren oder Splei -Stellen. Zu diesem Zweck wurden support vector machines (SVMs)
eingesetzt, die in der Lage sind, Informationen hoher Ordnung aus Millionen von Train-
ingsbeispielen zu nutzen. Anschlie end wird die geeignete Gewichtung der einzelnen Kom-
ponenten mit Hilfe des HSM-SVM-Systems erlernt, so dass korrekte Genstrukturen bes-
timmt werden k onnen. Dadurch wird es m oglich, tausende Beispiele in einer angemessenen
Zeitspanne auszuwerten und dabei die Vielzahl verschlusselter Informationen weitestge-
hend auszusch opfen. Um den komplizierten Prozess der Genvorhersage quasi auf Knopf-
druck durchfuhren zu k onnen, wurde au erdem ein Webserver entwickelt. Dieser Dienst
enth alt die Option, Spezies-spezi sche Modelle neu zu erzeugen.
Mit dem resultierenden System mGene nahmen wir an einem internationalen Wettbe-
werb zur Genvorhersage teil. Eine unabh angige Evaluierung bewies die hohe Vorhersage-
qualit at von mGene im Vergleich zu 47 eingereichten Datens atzen von 17 verschiedenen
Gruppen: Unsere Beitr age erwiesen sich als die genauesten in sieben von insgesamt zw olf
Evaluationskriterien, in weiteren drei Kriterien kamen sie auf den zweiten Platz. Nach
dem Wettbewerb wurde mGene weiter verbessert, so dass Vorhersagen erm oglicht wurden,
die sich als die genauesten in zehn von zw olf Evaluationskriterien etablierten.
Infolgedessen wurden genomweite Vorhersagen fur C. elegans erzeugt, wobei ca. 2000
Gene vorhergesagt wurden, die nicht in der aktuellen Annotation vorkamen. Bei der ex-
perimentellen Uberprufun g 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 fur vier weitere Nematoden generiert, fur 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 ub ertragen. Erste Ergebnisse zeigen, dass die Genauigkeit fur die
Vorhersagen genomischer Signale auf diese Weise signi kant verbessert werden kann.
viiPreface
Initially trained as a physicist, I became interested in the biological sciences early in
my undergraduate studies. I therefore started a Diplom thesis in the group of Prof.
Baumeister, where cryo-electron tomography is used to visualize cells in 3D.
In the context of image processing, I became aware of the power of modern machine
learning techniques to extract patterns from diverse, complex data. To learn more about
these methods and to apply them to biologically relevant questions, I joined the groups of
Bernhard Sch olkopf, Detlef Weigel and Gunnar R atsch. I started to work on the detection
of sequence variation, analyzing a huge set of hybridization data from re-sequencing tiling
arrays. We revealed hundreds of thousands of single nucleotide polymorphisms (SNPs)
in the genome of 20 varieties of the plant Arabidopsis thaliana, including many "major
e ect" SNPs that introduced premature stop codons, or destroyed the consensus dimer of
splice sites [32]. Due to space constraints, these results are not included into this thesis.
Subsequently, I turned my attention to a problem that is substantially more di cult to
solve, namely to identify those SNPs in the vicinity of splice sites that had a similarly
large e ect on the gene product by changing the splice form. While the initial results of
this e ort were not satisfying | mainly due to the lack of high quality labelled data for
training and assessment | I became interested in splice site prediction, and together with
S oren Sonnenburg and Petra Philips I studied the problem in various organisms [148]. I
also made myself familiar with the system mSplicer that predicts splice forms when the
location of a gene is known.
At the end of 2006, the international wormbase consortium launched a genome anno-
tation competition (nGASP) to assess the quality of existing gene nders. We took this
opportunity to advance our methods, to apply them to the provided data and accordingly
generated