Algorithm to identify protein complexes from high-throughput data

Abstract

Recent advances in proteomic technologies such as two-hybrid and biochemical purification allow large-scale investigations of protein interactions. The goal of this thesis is to investigate model-based approaches to predict protein complexes from tandem affinity purification experiments. We compare a simple overlapping model to a partitioning model. In addition, we propose a visualization framework to delineate overlapping complexes from experimental data. We propose two models to predict protein complexes from experimental data. Our first model is in some sense the simplest possible one. It is based on frequent itemset mining, which merely counts the incidence of certain sets of proteins within the experimental results. The affinity of two sets of proteins to form clusters is modeled to be independent, regardless of any overlapping members between these sets. Our second model assumes that formation of protein complexes can be reduced to pairwise interactions between proteins. Interactions between proteins are more likely for pairs of proteins if they come from the same cluster. Based on this model, we use Markov Random Field theory to calculate a maximum-likelihood assignment of proteins to clusters.

Neue Forschungsergebnisse zu proteomischen Techniken, zum Beispiel Two-Hybrid und Biochemical Purification, erlauben Untersuchungen von Protein- Interaktionen in grossem Massstab. Diese Arbeit untersucht modellbasierte Ansaetze, um aus Tandem-Affinity-Purification-Experimenten Proteinkomplexe zu berechnen. Wir vergleichen ein einfaches Modell, dass Ueberlappungen zwischen Komplexen zulaesst, mit einem Partitionsmodell. Ausserdem stellen wir ein Visualisierungsverfahren vor, dass ueberlappende Komplexe in experimentell ermittelten Daten darstellt. Wir schlagen zwei Modelle vor, um Proteinkomplexe zu berechnen. Das erste, in gewissem Sinne einfachst moegliche, basiert auf Frequent Itemset Mining und zaehlt das Auftreten von Mengen von Proteinen in den experimentellen Ergebnissen. Wir neben dabei an, dass die Neigung von Proteinen, bestimmte Komplexe zu bilden, fuer unterschiedliche Komplexe statistisch unabhaengig ist, insbesondere auch dann, wenn die gleichen Proteine an den Komplexen beteiligt sind. Komplexe, die einander ueberlappen, sind damit erlaubt. Das zweite Modell stellt das andere Extrem dar und nimmt an, dass Komplexe die Menge von Proteinen partitionieren. Komplexe damit einander nicht ueberlappen koennen und sich Komplexbildung auf rein paarweises Verhalten von Proteinen zurueckfuehren laesst. In diesem Modell ist die Beobachtung einer Interaktion zwischen einem Proteinpaar wahrscheinlicher, wenn beide Proteine miteinander in einem Komplex vorkommen. Beruhend auf diesem Modell nutzen wir Markov Random Fields, um eine Maximum-Likelihood- Schaetzung von Komplexen zu berechnen.