TY - THES U1 - Dissertation / Habilitation A1 - Nachtweide, Stefanie T1 - The Simultaneous Identification of Genes in Related Species N2 - As the tree of life is populated with sequenced genomes ever more densely, the new challenge is the accurate and consistent annotation of entire clades of genomes. In my dissertation, I address this problem with a new approach to comparative gene finding that takes a multiple genome alignment of closely related species and simultaneously predicts the location and structure of protein-coding genes in all input genomes, thereby exploiting negative selection and sequence conservation. The model prefers potential gene structures in the different genomes that are in agreement with each other, or—if not—where the exon gains and losses are plausible given the species tree. The multi-species gene finding problem is formulated as a binary labeling problem on a graph. The resulting optimization problem is NP hard, but can be efficiently approximated using a subgradient-based dual decomposition approach. I tested the novel approach on whole-genome alignments of 12 vertebrate and 12 Drosophila species. The accuracy was evaluated for human, mouse and Drosophila melanogaster and compared to competing methods. Results suggest that the new method is well-suited for annotation of a large number of genomes of closely related species within a clade, in particular, when RNA-Seq data are available for many of the genomes. The transfer of existing annotations from one genome to another via the genome alignment is more accurate than previous approaches that are based on protein-spliced alignments, when the genomes are at close to medium distances. The method is implemented in C++ as part of the gene finder AUGUSTUS. N2 - Dank der Fortschritte in der DNA-Sequenzierung werden Genomprojekte immer umfangreicher und befassen sich mit der Sequenzierung ganzer Gruppen nahverwandter Spezies, sogenannte Clades. Die Annotation dieser riesigen Datenmengen stellt eine große Herausforderung dar. Computergestützte Methoden, welche ganze Clades effizient und konsistent annotieren, werden dringend benötigt. In meiner Dissertation habe ich eine neue Methode zur vergleichenden Genvorhersage entwickelt, die Protein-kodierende Gene und deren Exon-Intron-Struktur gleichzeitig in mehreren Genomen von verwandten Spezies identifiziert. Der neue Ansatz verwendet ein Alignment der Genome, welches es ermöglicht, die Ähnlichkeit von Genstrukturen in verwandten Spezies bei der Vorhersage zu berücksichtigen und die Genauigkeit der Annotationen zu verbessern. In dem Modell werden einerseits in den verschiedenen Spezies übereinstimmende Genstrukturen favorisiert, andererseits werden plausible Unterschiede wie der Verlust oder Gewinn eines Exons in Abhängigkeit von der Phylogenie zugelassen. Das vergleichende Genvorhersage Problem (CGP) lässt sich als ein Knotenlabeling-Problem in einem Graphen formulieren. Das resultierende Optimierungsproblem ist zwar NP-vollständig, dennoch können gute approximative Lösungen mithilfe eines Subgradientenverfahrens und der Technik der Dual-Zerlegung gefunden werden. Die neue CGP Methode wurde auf Genom-Alignments von 12 Wirbeltieren und 12 Drosophila Spezies getestet und die Genauigkeit für die bereits annotierten Spezies Mensch, Maus und Drosophila Melanogaster mit konkurrierenden Methoden verglichen. Die Ergebnisse legen nahe, dass CGP für die Annotation großer Clades mit vielen Spezies geeignet ist, insbesondere wenn für viele der Genome RNA-Seq Daten zur Verfügung stehen. Ein weitere Anwendung der CGP Methode ist der Transfer von Annotationen von bereits annotierten Genomen auf neu sequenzierte Genome. Bei geringen bis mittleren Abständen ist die CGP Methode genauer als bisherige Ansätze zum Annotationstransfer, welche die Proteinsequenzen direkt gegen das Zielgenom alignieren. Die neue Methode ist als Erweiterung zu dem Genvorhersageprogramm AUGUSTUS implementiert. KW - Biomathematik , Bioinformatik KW - Genome Annotation KW - Comparative Gene Finding KW - Gene Structure Prediction KW - Clade Annotation KW - Comparative Genomics KW - Dual Decomposition KW - Lagrangian Relaxation Y2 - 2018 U6 - https://nbn-resolving.org/urn:nbn:de:gbv:9-opus-22204 UN - https://nbn-resolving.org/urn:nbn:de:gbv:9-opus-22204 SP - 155 S1 - 155 ER -