Web servers, databases, and algorithms for the analysis of protein interaction networks

Thesis (S.M.)--Massachusetts Institute of Technology, Computational and Systems Biology Program, 2013.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.Cataloged from student-submitted PDF version of thesis.Includes bibliographical references (p. 41-44).Understanding the cell as a system has become one of the foremost challenges in the post-genomic era. As a result of advances in high-throughput (HTP) methodologies, we have seen a rapid growth in new types of data at the whole-genome scale. Over the last decade, HTP experimental techniques such as yeast two-hybrid assays and co-affinity purification couple with mass spectrometry have generated large amounts of data on protein-protein interactions (PPI) for many organisms. We focus on the sub-domain of systems biology related to understanding the interactions between proteins that ultimately drive all cellular processes. Representing PPIs as a protein interaction network has proved to be a powerful tool for understanding PPIs at the systems level. In this representation, each node represents a protein and each edge between two nodes represents a physical interaction between the corresponding two proteins. With this abstraction, we present algorithms for the prediction and analysis of such PPI networks as well as web servers and databases for their public availability: 1. In many organisms, the coverage of experimental determined PPI data remains relatively noisy and limited. Given two protein sequences, we describe an algorithm, called Struct2Net, to predict if two proteins physically interact, using insights from structural biology and logistic regression. Furthermore, we create a community-wide web-resource that predicts interactions between any protein sequence pair and provides proteome-wide pre-computed PPI predictions for Homo sapiens, Drosophila melanogaster, and Saccharomyces cerevisiae. 2. Comparative analysis of PPI networks across organisms can provide valuable insights into evolutionary conservation. We describe an algorithm, called IsoRank, for global alignment of multiple PPI networks. The algorithm first constructs an eigenvalue problem that models the network and sequence similarity constraints. The solution of the problem describes a k partite graph that is further processed to find the alignments. Furthermore, we create a communitywide web database, called IsoBase, that provides network alignments and orthology mappings for the most commonly studied eukaryotic model organisms: Homo sapiens, Mus musculus, Drosophila melanogaster, Caenorhabditis elegans, and Saccharomyces cerevisiae.by Daniel K. Park.S.M