Graph-based approaches to protein structure- and function prediction

Abstract

The three-dimensional structure of a protein is determined by the network of covalent and non-covalent interactions. An exact description of the governing forces requires taking into account quantum effects which makes the system too complex for most computational analyses. Depending on the application, a simpler representation can make such analyses feasible while still capturing the relevant aspects of the system. Here we explore a number of applications which are based on representing a protein as a graph of interacting residues. This representation makes it possible to apply algorithms from graph theory to common protein analysis problems such as structure alignment and structure prediction. Part 1: Multiple Structure Alignment and the Sample Mean of Graphs. In contrast to the alignment of sequences, structure-based alignments allow us to look further back in evolutionary time. For the pairwise case, it has been shown that graph-based methods yield very sensitive alignments which are able to detect remote evolutionary relationships. Here we extend this approach to the case of aligning multiple proteins represented as graphs. This gives rise to a mathematically rigorous definition of the optimal multiple alignment. We analytically derive that calculating an optimal alignment is equivalent to calculating the sample mean of a set of graphs. This sample mean theory for graphs has recently been developed and makes a number of powerful algorithms applicable to protein structure analysis. We propose a new multiple structure alignment algorithm based on the sample mean theory and compare its performance to current alternative methods. We show that our algorithm is more efficient than other graph-based algorithms while retaining the same advantages. Part 2: Consensus Prediction of Residue-Residue Contacts. Accurate prediction of the non-covalent interactions in a protein is equivalent to predicting the three-dimensional structure. Here we present a contact prediction method which is based on calculating the graph-mean of a number of input predictions to create a consensus prediction. Our method predicts contacts more accurately than any individual method. This shows that even though many state-of-the-art methods already make use of consensus information for template picking and model selection, consensus information at the contact level can be further exploited to improve current structure prediction methods. Part 3: The Structural Impact of Cancer-Associated Mutations in Oncogenes and Tumor Suppressors. We applied computational methods to study the effects of somatic mutations on known and predicted protein structures of well-known cancer genes. We obtain significant differences between mutations in oncogenes and in tumor suppressors. While mutations in oncogenes tend to occur at the protein surface, are highly clustered and directly affect sites important for protein function, mutations in tumor suppressors tend to affect primarily protein stability. We also find that the alteration of oncogenic activity is often associated with mutations at ATP or GTP binding sites. With these results we can confirm and statistically validate the hypotheses for the gain-of-function and loss-of-function mechanisms of oncogenes and tumor suppressors, respectively. We further show that the differences in the mutational patterns can be used to predict for previously uncharacterized genes whether they likely function as an oncogene or a tumor suppressor.

Die dreidimensionale Struktur eines Proteins wird bestimmt durch die kovalenten und nicht-kovalenten Wechselwirkungen seiner Aminosäuren. Die genaue Beschreibung dieser Wechselwirkungen erfordert die Berücksichtigung von Quanteneffekten, was das System zu komplex für viele Analysen macht. Ja nach Anwendung kann ein geeigneteres Modell gewählt werden, das die Komplexität reduziert und gleichzeitig die für die Anwendung relevanten Eigenschaften erhält. In dieser Arbeit erforschen wir die Darstellung von Proteinen als Netzwerk von interagierenden Aminosäuren. Diese Graphendarstellung hat den Vorteil, dass sie die Anwendung von Methoden aus der Graphentheorie erlaubt und gleichzeitig die Information über die Tertiärstruktur erhält. Auf der Grundlage dieser Darstellung entwickeln wir neue Methoden für drei wichtige Probleme in der Strukturbiologie: Die Vorhersage der Struktur aus der Sequenz, der Vergleich von Strukturen und die Analyse der Auswirkungen von Mutationen auf die Proteinstruktur und -funktion. In Teil 1 zeigen wir, wie eine graphentheoretisch motivierte Definition des multiplen Strukturalignmentproblems auf eine überraschende Parallele zur Theorie des arithmetischen Mittels von Graphen führt. Wir zeigen, dass die Berechnung des Graph-Mittels äquivalent zur Berechnung des optimalen Strukturalignments ist und wie sich dies in einer neuen multiplen Strukturalignmentmethode ausnutzen lässt. In Teil 2 verwenden wir die Graph-Mittel-Theorie, um eine Methode zur konsensbasierten Vorhersage von Intraproteinkontakten zu entwicklen. Wir zeigen, dass mit Hilfe dieser Methode, Kontakte innerhalb von Proteinen besser vorhergesagt werden können, als mit jeder anderen aktuell verfügbaren Methode. In Teil 3 zeigen wir, wie Strukturinformationen genutzt werden können, um die Auswirkungen von Krebsmutationen funktionell zu analysieren. Für einen Datensatz von ungefähr 2000 Mutationen analysieren wir deren Auswirkung auf die jeweilige Proteinstruktur. Wir zeigen, dass die Mutationsmuster in Onkogenen sich stark von denen in Tumorsuppressoren unterscheiden. Dies führt zu einer Methode, mit deren Hilfe sich anhand der Mutationsmuster prediktive Aussagen machen lassen, ob ein unbekanntes Protein sich im Krebs-Zusammenhang wie ein Onkogen oder ein Tumorsupporessor verhält. Wir spannen mit dieser Arbeit den Bogen von Sequenzinformation über Struktur hin zur funktionellen Analyse. Je mehr sich der aktuelle Trend der immer schnelleren Generierung von Sequenzdaten fortsetzt, desto mehr werden effiziente Methoden zur strukturellen und funktionellen Analyse, wie die hier gezeigten, an Bedeutung gewinnen.