Under CopyrightThiele, R.R.Thiele2022-03-0631.07.20021998https://publica.fraunhofer.de/handle/publica/27333510.24406/publica-fhg-273335In dieser Arbeit wird eine divide & conquer Methode für das Sequenzstrukturalignment von Proteinen vorgestellt (rekursiven dynamischen Programmierung (RDP)). Sequenzstrukturalignment ist eine der erfolgreichsten Methoden, um entfernte Verwandtschaften zwischen Proteinsequenzen und anderen experimentell strukturaufgeklärten Proteinen zu erkennen, die der Ableitung von Strukturmodellen für die betrachtete Sequenz dienen. Die Qualität der so erhaltenen Strukturmodelle wird wesentlich durch die Korrektheit der Abbildung der Sequenz auf die Strukturen festgelegt, die als Vorlage dienen. Daher zielt die RDP{Methode auf die Berechnung von sehr guten Sequenzstrukturalignments ab, um so die Zuverlässigkeit sowohl der Faltungserkennung als auch der zugehörigen Modellstrukturen zu erhöhen. Die RDP-Methode bildet die Proteinsequenz schrittweise auf eine bekannte Rückgratstruktur ab, indem sie lokale Alignments mit unterschiedlichen Kostenfunktionen berechnet. RDP modifiziert jeweils die Vorlagestruktur gemäß der bereits abgebildeten Aminosäureresten und sucht dann rekursiv nach signifikanten Ähnlichkeiten zwischen bisher nicht berücksichtigten Teilen in Sequenz und Vorlagestruktur. Dieser rekursive Prozeß wird solange fortgesetzt, bis auch im Kontext der bereits abgebildeten Teile keine signifikanten Ähnlichkeiten zwischen den verbleibenden Teilen von Sequenz und Struktur mehr gefunden werden. Die RDP-Methode wird sowohl an Beispielen mit bekannten Strukturen als auch an echten Blindvorhersagen validiert. Auf Standardtestmengen liefert die RDP-Methode im Vergleich zu anderen state-of-the-art-Sequenzstrukturalignmentverfahren eine signifikante Verbesserung der Alignmentqualität und damit in direkter Konsequenz eine Erhöhung der zuverlässig in Faltungserkennungsexperimenten erkannten entfernten strukturellen Verwandtschaften.This thesis presents a divide-and-conquer method for protein threading called recursive dynamic programming (RDP). Protein threading is one of the most successful methods to detect distant relationships between protein sequences and proteins whose three dimensional structures have been experimentally solved. Such relationships are used to predict structural models for protein sequences. The quality of the derived structural model is mainly determined by the correctness of the mapping of the sequence onto the template structure. Therefore, by calculating high quality sequence structure alignments the RDP method aims at the improvement of the reliability of fold recognition and corresponding model structures. The RDP method works as follows: The protein sequence is mapped onto a potential template structure in a stepwise fashion, similarly to computing local alignments but utilizing different cost functions. RDP, recursively, modifies the template structure in order to account for the mapped residues and searches for significant similarities between the yet unmapped parts of the sequence and the modified template. This recursive process is continued until no significant similarities between the remaining parts of sequence and template are found according to the scoring system in the context of the already mapped parts. We validate our method on different sets of protein pairs where both structures are known as well as with blind predictions. On standard test sets the RDP method shows significant improvements of the alignment quality in comparison with available state-of-the-art threading tools. As a result of the improved alignment quality the number of distant structural relationships reliably identified in fold recognition experiments is also significantly increased.1 Einleitung S.1 2 Proteine S.7 - 2.1 Strukturbeschreibende Elemente S.7 - 2.1.1 Primärstruktur S.10 - 2.1.2 Sekundärstruktur S.12 - 2.1.3 Tertiärstruktur S.14 - 2.1.4 Quartärstruktur S.15 - 2.2 Experimentelle Proteinstrukturbestimmung S.16 - 2.2.1 Röntgenkristallographie S.16 - 2.2.2 Kernresonanzspektroskopie S.17 - 2.2.3 Kryo-Elektronenmikroskopie S.18 - 2.3 Proteinfaltung S.19 3 Proteinstrukturvorhersageproblem S.21 - 3.1 Motivation S.21 - 3.2 Problemdei nition S.22 - 3.3 Homologie in Sequenz und Struktur S.26 - 3.3.1 Sequenzen und Faltungsmotive S.26 - 3.3.2 Sequenzhomologie und strukturelle Ähnlichkeit S.27 - 3.3.3 Strukturelle Ähnlichkeit ohne signi kante Sequenzhomologie S.34 - 3.3.4 Strukturelle Ähnlichkeit und Funktion S.37 - 3.3.5 Klassifizierung von Proteinen S.38 - 3.3.6 Bedeutung für die Vorhersage S.41 4 Methoden zur Proteinstrukturvorhersage S.43 - 4.1 Vergleichende Modellierung S.44 - 4.1.1 Verschiedene Ansätze zur vergleichenden Modellierung S.47 - 4.1.2 Sequenzalignment S.49 - 4.2 Faltungserkennung S.54 - 4.2.1 Sequenzstrukturalignment S.57 - 4.2.2 Faltungserkennung mit Einkörpertermen S.58 - 4.2.3 Faltungserkennung mit Mehrkörpertermen S.60 - 4.3 Ab initio-Methoden S.71 - 4.3.1 Sekundarstrukturvorhersage S.72 - 4.3.2 Ab initio-Tertiarstrukturvorhersage S.76 5 Bewertungssysteme S.79 - 5.1 Sequenzabhängige Bewertungssysteme S.79 - 5.1.1 Aminosäureaustauschmatrizen S.79 - 5.1.2 Vergleich sequenzabhängiger Bewertungssysteme S.83 - 5.2 Empirische Potentiale zur Faltungserkennung S.84 - 5.2.1 Ableitung empirischer Potentiale S.84 - 5.2.2 Faltungsmodelle fur empirische Potentiale S.87 - 5.2.3 Einkörperpotentiale S.93 - 5.2.4 Zwei- und Mehrkörperpotentiale S.97 - 5.2.5 Bewertung empirischer Potentiale S.101 6 Rekursive Dynamische Programmierung S.105 - 6.1 Motivation S.105 - 6.2 Die RDP-Methode S.109 7 RDP-Sequenzstrukturalignment S.117 - 7.1 Datenstrukturen S.120 - 7.1.1 Informationen zur Sequenz S.121 - 7.1.2 Informationen zur Struktur S.122 - 7.1.3 Darstellung von Teilproblemen S.123 - 7.1.4 Darstellung von Teillösungen S.124 - 7.1.5 Der Lösungsbaum T S.125 - 7.2 Generierung von Teillösungen S.129 - 7.2.1 Orakel und Sequenzinformation S.129 - 7.2.2 Orakel und Einkörperpotentiale S.133 - 7.2.3 Orakel und Mehrkörperpotentiale S.134 - 7.2.4 Orakel und Informationen über aktive Stellen S.147 - 7.3 Vorselektion der Teillösungen S.151 - 7.3.1 Signi kanz von Teillösungen S.151 - 7.3.2 Identische Teillösungen S.153 - 7.3.3 Nicht zulässige Teillösungen S.153 - 7.3.4 Ahnliche Teillösungen S.153 - 7.3.5 Kombination verschiedener Orakellösungen S.155 - 7.4 Aufteilung in Unterprobleme S.158 - 7.5 Abarbeitungsreihenfolge des Lösungsbaums S.159 - 7.6 Bestimmung der Gesamtlösung S.161 - 7.6.1 Kombination von Lösungen an Knoten aus V S.162 - 7.6.2 Auswahl von Losungen an Knoten aus V S.163 - 7.7 Parameterkalibrierung S.168 - 7.7.1 Empirische Methode zur Einstellung der Parameter S.169 - 7.7.2 Vergleich verschiedener Parametersätze S.170 8 Ergebnisse S.177 - 8.1 Dei nition der Erfolgskriterien S.177 - 8.2 Der ToPLign-Ansatz fur Blindvorhersagen S.178 - 8.3 Alignmentqualität S.180 - 8.3.1 Definition von Gütekriterien S.180 - 8.3.2 Testmengen fur die Bewertung der Alignmentqualität S.184 - 8.3.3 Vergleich auf der Basis von multiplen HSSP-Alignments S.189 - 8.3.4 Vergleich auf der Basis von JOY-Strukturalignments S.196 - 8.3.5 Vergleich auf der Basis von SARF-Strukturalignments S.201 - 8.3.6 Vergleich der Laufzeiten S.208 - 8.4 Faltungserkennung S.210 - 8.4.1 Testmenge fur die Erkennungsexperimente S.210 - 8.4.2 Bewertungskriterien fur die Erkennungsexperimente S.215 - 8.4.3 Ergebnisse der Erkennungsexperimente S.216 - 8.5 Strukturvorhersagewettbewerb: CASP II S.224 - 8.5.1 Target t4: Polyribonukleotide Nukleotidyltransferase S.229 - 8.5.2 Target t14: 3-Dehydroquinase S.231 - 8.5.3 Target t31: Exfoliatives Toxin S.233 - 8.6 Strukturvorhersage fur die Thymidinkinase S.236 - 8.7 Zusammenfassung der Ergebnisse S.243 9 Ausblick und RDP-Erweiterungen S.245 - 9.1 Schleifenmodellierung mit RDP S.246 - 9.2 Multiples RDP-Sequenzstrukturalignment S.248 - 9.3 Regelbasierte Steuerung der RDP-Methode S.248 - 9.4 Sequenzalignment mit RDP S.249 - 9.5 Multiples Sequenzalignment mit RDP S.249 - 9.6 Strukturalignment mit RDP S.250 10 Zusammenfassung S.251deProteinstrukturvorhersageFaltungserkennungSequenzstrukturalignmentOptimierungstatistisches Potentialprotein structure predictionfold recognitionsequence-structure alignmentthreadingdivide and conquer algorithm003005006518doctoral thesis