Algorithmen und Bewertungssysteme für die ähnlichkeitsbasierte Proteinstrukturvorhersage

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