title: Graph-Based Approaches to Protein StructureComparison - From Local to Global Similarity
title: Graph-basierte Ansätze zum Vergleich von Proteinstrukturen - Von lokaler zu globaler Ähnlichkeit
Creators: name: Mernberger, Marco
Publisher: name: Philipps-Universität Marburg
Year: 2012
Subjects: Protein structure comparison
Graph comparison
Graphvergleich
Proteinbindetaschen
structure distance measures
Proteinstrukturvergleich
Informatik
protein binding pockets
Protein-Ligand-Interaction
Protein-Ligand-Wechselwirkung
Proteinbindung
Struktur-Distanzmaße
Proteine

description: Die vergleichende Analyse von
      Protein-Strukturdaten ist ein zentraler Aspekt der
      strukturellen Bioinformatik. Das Heranziehen von
      struktureller Information erlaubt es, Rückschlüsse auf die
      Funktion unbekannter Proteine zu ziehen, besonders in Fällen,
      wo keine erkennbare Sequenzhomologie zu anderen Proteinen zu
      finden ist. Für die Funktion eines Enzyms ist die
      Faltungsstruktur vermutlich weniger bedeutsam als die
      strukturelle Konformation des katalytischen Zentrums oder der
      Oberflächenregionen, an denen die Interaktion mit
      Bindepartnern, Substraten und Liganden stattfindet. Eine
      vergleichende Analyse dieser Regionen ist daher besonders
      interessant um die Funktion eines Proteins zu ermitteln, da
      strukturelle Einschränkungen aufgrund der Anforderungen der
      katalysierten biochemischen Reaktion die Wahrscheinlichkeit
      einer strukturellen Ähnlichkeit erhöhen. Darüber hinaus ist
      die vergleichende Analyse von Proteinbindetaschen von
      besonderem Interesse in der pharmazeutischen Chemie, um
      mögliche Kreuzreaktivitäten zu erkennen und ein tieferes
      Verständnis für den Katalysemechanismus zu erlangen. Von
      einem algorithmischen Standpunkt betrachtet, kann der
      Vergleich struktureller Daten, oder allgemeiner, komplexer
      Objekte, durch unterschiedliche methodische Prinzipien
      angegangen werden. Globale Methoden zielen auf einen
      Vergleich der kompletten Struktur als Ganzes ab, während
      lokale Methoden das Problem auf den multiplen Vergleich
      lokaler Substrukturen verlegen. Vor dem Hintergrund des
      Vergleichs von Proteinstrukturen ist nicht a priori bekannt,
      welche Strategie sinnvoller ist. In dieser Dissertation
      wurden mehrere konzeptionell unterschiedliche algorithmische
      Ansätze basierend auf lokalen, globalen und semi- globalen
      Strategien entwickelt, mit dem Ziel strukturelle Daten,
      genauer, Proteinbindetaschen zu vergleichen. Die Verwendung
      von Graphen zur Modellierung von Proteinstrukturen hat eine
      lange Tradition in der strukturellen Bioinformatik. Seit
      einiger Zeit werden Graphen auch zur Modellierung von
      Proteinbindetaschen verwendet. Die Algorithmen, die hier
      entwickelt wurden, basieren auf diesem Modellierungskonzept,
      daher kann man diese Methoden vom informatischen Standpunkt
      aus auch als lokale, globale und semi-globale Ansätze zum
      Vergleich von Graphen auffassen. Die Algorithmen wurden
      hauptsächlich unter der Prämisse entwickelt, einen mehr
      approximativen Vergleich von Proteinbindetaschen zu erlauben
      um der strukturellen Dynamik von Proteinstrukturen Rechnung
      zu tragen. Eine Motivation dafür war es, unter Umständen
      weniger offensichtliche Ähnlichkeiten zu finden, die durch
      rigidere Methoden übersehen werden können. Die entwickelten
      Ansätze wurden anschließend auf verschiedenen typischen
      Problemen der strukturellen Bioinformatik angewendet und ihre
      Performanz zu untersuchen und zu vergleichen. Jeder der
      entwickelten Ansätze war in der Lage, Verbesserungen
      gegenüber bestehende Methoden basierend auf den gleichen
      Prinzipien zu erzielen. Ein weiterer wichtiger Aspekt dieser
      Arbeit war es, herauszufinden, welches methodische Konzept am
      besten geeignet ist für den Vergleich von
      Proteinbindetaschen. Dieser Frage wird im Rahmen dieser
      Dissertation nachgegangen.
description: The comparative analysis of protein
      structure data is a central aspect of structural
      bioinformatics. Drawing upon structural information allows
      the inference of function for unknown proteins even in cases
      where no apparent homology can be found on the sequence
      level. Regarding the function of an enzyme, the overall fold
      topology might less important than the specific structural
      conformation of the catalytic site or the surface region of a
      protein, where the interaction with other molecules, such as
      binding partners, substrates and ligands occurs. Thus, a
      comparison of these regions is especially interesting for
      functional inference, since structural constraints imposed by
      the demands of the catalyzed biochemical function make them
      more likely to exhibit structural similarity. Moreover, the
      comparative analysis of protein binding sites is of special
      interest in pharmaceutical chemistry, in order to predict
      cross-reactivities and gain a deeper understanding of the
      catalysis mechanism. From an algorithmic point of view, the
      comparison of structured data, or, more generally, complex
      objects, can be attempted based on different methodological
      principles. Global methods aim at comparing structures as a
      whole, while local methods transfer the problem to multiple
      comparisons of local substructures. In the context of protein
      structure analysis, it is not a priori clear, which strategy
      is more suitable. In this thesis, several conceptually
      different algorithmic approaches have been developed, based
      on local, global and semi-global strategies, for the task of
      comparing protein structure data, more specifically protein
      binding pockets. The use of graphs for the modeling of
      protein structure data has a long standing tradition in
      structural bioinformatics. Recently, graphs have been used to
      model the geometric constraints of protein binding sites. The
      algorithms developed in this thesis are based on this
      modeling concept, hence, from a computer scientist's point of
      view, they can also be regarded as global, local and
      semi-global approaches to graph comparison. The developed
      algorithms were mainly designed on the premise to allow for a
      more approximate comparison of protein binding sites, in
      order to account for the molecular flexibility of the protein
      structures. A main motivation was to allow for the detection
      of more remote similarities, which are not apparent by using
      more rigid methods. Subsequently, the developed approaches
      were applied to different problems typically encountered in
      the field of structural bioinformatics in order to assess and
      compare their performance and suitability for different
      problems. Each of the approaches developed during this work
      was capable of improving upon the performance of existing
      methods in the field. Another major aspect in the experiments
      was the question, which methodological concept, local, global
      or a combination of both, offers the most benefits for the
      specific task of protein binding site comparison, a question
      that is addressed throughout this thesis.