Applications of Fast Protein Structure Alignments

Abstract

Diese Arbeit behandelt die Entwicklung und Anwendungen von Proteinstrukturvergleichsalgorithmen. Das beinhaltet die Bewertung existierender Ähnlichkeits und Distanzmaße für Proteinstrukturen, eine Methode zur Ähnlichkeitssuche in 3D-Strukturdatenbanken, die Rekonstruktion von Stammbäumen der Kinasen sowie das Clustern der kompletten Proteindatenbank (PDB). Wir zeigen dass unsere Proteinvergleichsmethode um Grössenordnungen schneller ist als bestehende Methoden und dabei Alignments vergleichbarer Qualität liefert. Diese Eigenschaften erlaubten es SALAMI, einen öffentlich verfügbaren Webserver zu erstellen der 3D-Struktursuchen in einer Datenbank durchführt und HANSWURST, ein multiples Alignmenttool integriert. SALAMI wurde vor kurzem bei der Auswertung von CASP, einem weltweiten gemeinschaftlichen Experiment zur Bewertung von Strukturvorhersagemethoden, verwendet. Eine weitere Anwendung unserer Methode ist die Klassifizierung von Proteinstrukturen, insbesondere von Kinasen. Unter der Annahme dass Proteinstukturen stärker konserviert sind als ihre Sequenzen konnten wir entfernte evolutionäre Beziehungen auflösen welche ausserhalb der Reichweite sequenzbasierter Methoden liegen. Auf der Basis von jeder-gegen-jeden Vergleichen von 964 Proteinen wurde eine Methode zur nichtlinearen Abbildung verwendet um eine Karte des Strukturraumes zu generieren. Ähnlich einer Landkarte bildet diese die Distanzen zwischen den Strukturen mit nur geringen Abweichungen ab. Wir fanden ausserdem dass die Anwendung von hierarchischen Clusteringmethoden die Vorhersage von manuell annotierten SCOP Familien mit hoher Genauigkeit erlaubt. Bei der Rekonstruktion von Bäumen aus Distanzdaten ist die Auswahl der richtigen Distanzfunktion der entscheidende Schritt. Die Bäume in dieser Arbeit sind eine deutliche Verbesserung gegenüber dem gegenwärtigen Stand der Technik. Unsere vollautomatische Methode produziert Bäume aus 964 Strukturen und ersetzt damit gängige halbautomatische Methoden die mit c.a. 30 Strukturen arbeiten. Abschliessend haben wir unseren Alignmentansatz benutzt um strukturell und konformationell nichtredundante Untermengen der PDB und Gruppen sehr ähnlicher Strukturen zu erzeugen. Wenn man sich für die globalen Eigenschaften von Proteinenstrukturen interessiert so wie bei der Erstellung von Fragmentbibliotheken zur Strukturvorhersage, Modellierung, oder der Ähnlichkeitssuche, dann sind solche Untermengen deutlich besser geeignet als existierende sequenzbasierte Listen. Wegen der grossen Anzahl an Strukturvergleichen die dafür nötig sind war eine solche Liste bisher nicht verfügbar. Wir haben ein indexbasiertes Suchwerkzeug in Kombination mit unserem Vergleichsalgorithmus verwendet um die komplette PDB zu clustern und gute Repräsentanten auszuwählen. Unsere Lösung weisst eine deutlich höhere strukturelle Homogenität auf als sequenzbasierte Cluster obwohl sie aus weniger Clustern besteht.

This thesis is focused on the development of protein structure alignment algorithms and their applications. That includes the evaluation of existing similarity and distance measures for protein structures, a method for 3D similarity search in a database of protein structures, reconstruction of family trees for kinases, and clustering of the entire Protein Databank. We show that our protein structure alignment method is orders of magnitude faster than existing tools while providing comparable alignment quality. This has allowed us to build SALAMI, a public web server which performs 3D similarity search of protein structures and integrates HANSWURST, a multiple structure alignment tool. SALAMI was recently used in the evaluation of CASP, a community-wide evaluation of protein structure prediction methods. Another application of our alignments was the classification of protein structures, particularly of kinases. Working with the assumption that protein structure is more conserved than sequence, we are be able to resolve distant evolutionary relationships which are beyond the reach of sequence based methods. Based on all vs. all pairwise alignments of 964 proteins, nonlinear mapping was used to create a map of the kinase structure space which most accurately reflects the structural similarity of the proteins. We also found that applying hierarchical clustering methods to structural similarity data allows us to predict the SCOP classifications for kinases with high confidence and perfect accuracy. When reconstructing phylogenetic trees from structural similarity data, finding a good distance measure is the most important step. The trees we present are a significant improvement over the current state of the art. Our fully automated method produced a tree of 964 structures which replaces a semi manual method that was applied to tens of structures. Finally, we have used our alignment tools to compile structurally and conformationally non-redundant subsets of the PDB and clusters of very similar chains. When one is interested in global properties of protein folds for uses such as fragment libraries for structure prediction, modeling, or speeding up structure searches, structurally non redundant databases are much more suitable than sequence based sets. However, due to the large number of alignments required, such a list has not been available in recent years. We have used an index based structure search tool in combination with our fast alignment method to cluster the entire PDB and to select good representatives from each cluster. Our solution exhibits a much higher structural homogeneity than sequence based clusters, even though our solution consists of fewer clusters.