Algorithmen und Bewertungssysteme für die ähnlichkeitsbasierte Proteinstrukturvorhersage

In 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.