Genvorhersage mit einem Hidden-Markow-Modell

Die Annotation der großen und schnell wachsenden Menge von genomischen Sequenzdaten erfordert informatische Methoden um Gene in DNA-Sequenzen zu finden. Diese Doktorarbeit stellt eine informatische Methode vor, Protein-kodierende Gene zu finden, die in DNA-Sequenzen von Eukaryoten (Pflanzen und Tiere) kodiert sind. Wir führen ein sogenanntes verallgemeinertes Hidden-Markow-Modell (GHMM) für eukaryotische genomische Sequenzen ein.Dieses Modell, das wir AUGUSTUS nennen, ist ein probabilistisches Modell einer DNA-Sequenz und der ihr unterliegenden Genstruktur. Es definiert eine Verteilung auf der Menge aller möglichen Paare einer DNA-Sequenz und ihrer Annotation der Protein-kodierenden Bereiche. Dies erlaubt, in einer Eingabe-DNA-Sequenz Gene zu entdecken durch das Finden der wahrscheinlichsten Genstruktur der Eingabe-DNA-Sequenz, gegeben die Eingabe-DNA-Sequenz.Diese wahrscheinlichste Genstruktur der Eingabe-DNA-Sequenz wird von einem Computerprogramm gefunden. Wir haben mehrere neue Methoden angewendet um das Modell der tatsächlichen Verteilung der wahren Sequenzen und ihrer Annotationen besser anzupassen. Für die Splice Sites führen wir neue probabilistische Teilmodelle ein. Wir führen eine Methode zur besseren Schätzung der Parameter, die von der Basenzusammensetzung der Sequenz abhängen, ein. Desweiteren, behandeln wir das folgende Problem. Ein GHMM kann die Längenverteilung von bestimmten strukturellen Teilen der Sequenz wie Introns modellieren. Der Nachteil der bisher in Genvorhersageprogrammen eingesetzten Verfahren war, daß sie sich entweder aus Laufzeitgründen verboten oder, daß sie die wahre Längenverteilung schlecht modelliert haben. Der hier vorgestellte Zugang erlaubt bei relativ geringer Laufzeit des Algorithmus, ein Anfangsstück der Längenverteilung beliebig zu definieren und den Schwanz der Verteilung geometrisch verteilt sein zu lassen.Wir testeten das auf diesem Modell basierende Computerprogramm auf DNA-Sequenzen vom Mensch und von der Fruchtfliege Drosophila melanogaster mit bekannter Annotation. Die Genauigkeit der Genvorhersagen ist besser als die von bekannten und etablierten Genvorhersageprogrammen.Der zweite große Teil der Dissertation behandelt die Integration von unsicherer extrinsischer Information über die Genstruktur. Das GHMM AUGUSTUS wird zu einem GHMM AUGUSTUS+ erweitert, das ein probabilistisches Modell aller möglicher Tripel ist, die aus einer DNA-Sequenz, ihrer Annotation und extrinsischer Information über die Sequenz gebildet werden. Das Genvorhersageprogramm findet dann die wahrscheinlichste Annotation gegeben sowohl die Eingabe-DNA-Sequenz als auch die extrinsische Information.Die Methode führt zu einer auf natürliche Weise gerechtfertigten Erhöhung der Wahrscheinlichkeit von Genstrukturen, die die extrinsische Information berücksichtigen. Die Methode erlaubt auch, extrinsische Information über einen Bereich der DNA-Sequenz zu integrieren, zum Beispiel Hinweise, daß ein bestimmter Bereich Protein-kodierend ist, ohne dabei Genstrukturen zu bevorzugen, die den Hinweis nur "teilweise" berücksichtigen. Experimente mit AUGUSTUS+ zeigen, daß EST-Datenbank-Vergleiche die Vorhersagegenauigkeit signifikant verbessern können, wenn sie mit Protein-Datenbank-Vergleichen kombiniert werden.Annotation of the large and rapidly increasing amount of genomic sequence data requires computational tools for finding genes in DNA sequences. This thesis presents a computational method for finding protein-coding genes encoded in DNA sequences of eukaryotes (plants and animals). We introduce a so-called generalized Hidden Markov Model (GHMM) for eukaryotic genomic sequences.This model, called AUGUSTUS, is a probabilistic model of a DNA sequence with the gene structure underlying the sequence. It defines a probability distribution on the set of all possible pairs of a DNA sequence and its annotation of protein-coding regions. Genes in an input DNA sequence can be uncovered by finding the gene structure which is most likely in the probabilistic model given the input DNA sequence. The most likely gene structure of the input DNA sequence is searched by a computer program, which can be done both exactly and efficiently because of the relatively simple dependency structure of the distribution defined by a GHMM. In order for the model to fit well the actual distribution of true sequences and their annotations several new methods have been applied. A GHMM for gene prediction contains probabilistic state models for different functional parts of the genomic sequence, such as translational and splicing signals and coding regions. For the splice sites new probabilistic submodels are introduced. A method is used to better estimate the parameters of the model depending on the average base frequency.Further, the following issue is addressed. A GHMM may model the length distribution of certain structural parts of the sequence, such as introns. The disadvantage of the procedures used in existing programs was that they either caused prohibitively long running times or they modeled the true length distribution inadequately. An approach presented here allows to approximate a given length distribution by an arbitrary initial part and a geometric tail at relatively low computational cost.A computer program based on this model has been tested on DNA sequences with known annotation from human and the fruit fly Drosophila melanogaster. The accuracy of the predictions compare favorably to that of other well known, established gene prediction programs.The second major part of the thesis addresses insecure external information about the gene structure and presents a method for integrating external information into a GHMM for gene prediction. The GHMM AUGUSTUS is extended to a new GHMM AUGUSTUS+ which is a probabilistic model of all possible triplets formed by a DNA sequence, its annotation, and external information about the sequence.The gene prediction program then finds the most likely annotation given both the input DNA sequence and the external evidence. It accounts for the fact that such external evidence can be misleading. The parameters corresponding to the distribution of the external information can be easily estimated. This leads to a naturally justified increase in likelihood of gene structures respecting the external information compared to the likelihood in the previous model. The method allows to make use of evidence about a range of the DNA sequence, e.g. evidence that a certain range of the sequence is protein-coding, without preferring gene structures that only "partially respect" that evidence over those which do not respect at all the evidence. Another advantage of the method presented here, compared to ad-hoc methods for integrating external information into existing programs, is that the underlying theory of GHMMs still applies to the model.Experiments with AUGUSTUS+ show that the use of extrinsic information coming from EST database searches can significantly improve the prediction accuracy of gene prediction programs when combined with protein database searches