One of the most challenging problems of the post-genomic era is the biological impact of similarities between protein structures. For the comparison of protein structures, it is of interest to find maximal common substructures between pairs of structures. This problem is also relevant for the discovery of biological important structural motifs and structure classification. In this thesis we describe suitable representations of protein structures as contact maps or protein graphs on secondary structure level. Based on these representations graph-theoretical methods are introduced to search for the most common protein topologies or perform pairwise structure alignments. The first chapter gives an introduction and motivation why the thesis is relevant for the field of protein structure analysis. The second part introduces the basic concepts of protein structures and describes the different representations for protein structures. Additionally, short introductions into protein folding and protein structure evolution are presented. The next part addresses the graphtheoretical description of protein topologies. The most common supersecondary structure motifs are defined using different linear notations. In part three the general protein structure alignment problem is examined. It is discussed how structural similarity can be measured and how difficult it is to obtain significance for protein structure alignments. Part five describes a newly developed hierarchical method for non-sequential and gapped protein structure comparison. The basic step of the method is a maximal common subgraph search between protein graphs using a genetic algorithm. The new alignment method is evaluated on manually curated alignments and on large database scans. The last chapter focuses on the exact graph-theoretical solution for the maximal common subgraph problem for protein graphs. The systematic comparison of protein structures resulted in the identification of repeating structural motifs as well as recurring spatial arrangements. Evaluations showed that the proposed methods are able to detect biological meaningful similarities that are not detectable for sequence-based or other state-of-the-art structure alignment methods, and thus provide new insights into evolutionary and functional relationships of protein structures.
Eine der größten Herausforderungen der Bioinformatik in der post-genomischen Ära zu Beginn des neuen Jahrtausends besteht in der Erforschung von evolutionären Zusammenhängen zwischen Proteinstrukturen. Eine wichtige Methode, um Proteinstrukturen miteinander zu vergleichen, ist die Suche nach den größten gemeinsamen Teilstrukturen. Die effiziente Anwendung dieser Methode ist auch für das Auffinden kleinerer Strukturmotive oder für die Klassifikation von Proteinstrukturen von großer Bedeutung. In dieser Arbeit werden verschiedene Darstellungsformen für Proteinstrukturen in Form von Proteingraphen und sogenannten Kontaktmatrizen beschrieben. Ausgehend von diesen Repräsentationen werden Methoden aus der Graphentheorie verwendet, um wichtige Proteintopologien zu finden und um paarweise Vergleiche zwischen Proteinstrukturen durchzuführen. Das erste Kapitel gibt eine kurze Einführung, warum die Suche nach Ähnlichkeiten in Proteinstrukturen wichtig ist. Im zweiten Teil werden die grundlegenden Konzepte zur Beschreibung von Proteinstrukturen zusammen mit den in dieser Arbeit verwendeten Darstellungsformen vorgestellt. Zusätzlich wird eine kurze Einführung in die Faltung von Proteinen und in die Evolution von Proteinstrukturen gegeben. Das dritte Kapitel befasst sich mit der graphtheoretischen Modellierung von Proteintopologien. Die wichtigsten Strukturmotive werden durch lineare Notationen mathematisch eindeutig beschrieben. Im vierten Teil wird das generelle Problem diskutiert, wie man die Ähnlichkeiten zwischen Proteinstrukturen finden kann und wie man diese strukturellen Ähnlichkeiten quantifizieren kann. Im fünften Teil wird eine hierarchische Methode zum Vergleich von Proteinstrukturen vorgestellt, bei der die sequenzielle Anordnung der einzelnen Teilsegmente einer Proteinstruktur nicht berücksichtigt werden müssen und einzelne Teilstrukturen ausgelassen werden können. Der wichtigste Teilschritt dieser Methode ist die Suche nach größten gemeinsamen Teilgraphen in zwei Proteingraphen mit Hilfe eines genetischen Algorithmus. Es wird gezeigt, daß diese neue Methode den meisten bekannten Algorithmen zum Strukturvergleich überlegen ist. Das sechste Kapitel befasst sich mit der exakten graphtheoretischen Lösung für die Suche nach größten gemeinsamen Teilgraphen in Proteingraphen. Die exakte Lösung dieses Problems belegt eindeutig die Qualität des heuristischen Ansatzes, der im Kapitel zuvor beschrieben worden ist. Durch die systematische Untersuchung von Proteinstrukturen konnten Strukturmotive und räumliche Anordnungen gefunden werden, die häufig in verschiedenen Proteinen vorkommen. Die Ergebnisse zeigen, daß die hier vorgestellten Methoden dazu in der Lage sind, biologisch wichtige Ähnlichkeiten zu finden, die mit Hilfe von Sequenzvergleichen allein oder anderen Methoden zum Vergleich von Proteinstrukturen nicht zu finden sind, und daher neue Einsichten in wichtige evolutionäre und funktionelle Zusammenhänge zwischen Proteinen gewähren können.
