A key problem in biology is understanding the work of proteins. While protein sequences have been mostly determined for many organisms, the functions of these proteins and how they work together to accomplish them are much less understood. An important source of information for addressing these questions is protein interaction data. Protein interactions, which, taken together, can be represented as networks or graphs, have been determined on a large scale for several organisms. In this work, we study the relationship between protein function and interaction network topology, focusing on protein-protein physical interaction networks. We address both the task of assigning function to individual proteins and the more global question of the organizational principles underlying these networks.

In the first part of this thesis, we explore the use of physical interaction networks for predicting protein function. We begin by discussing which topological properties of interaction networks should be taken into account by network-based function prediction algorithms, using as illustrations some earlier approaches to this problem. Then, using these desiderata as guidelines, we introduce an original network-flow based algorithm for predicting protein function. This algorithm, FunctionalFlow, takes advantage of both network topology and some measure of locality, and, as a result, has improved performance over previous methods. Finally, we show that performance can be improved substantially as we consider multiple data sources and introduce edge weights to reflect data reliability.

In the second part of this thesis, we take a different view at the topology-function relationship and use known information about protein molecular function to attempt to uncover the organizational principles of physical interaction networks. We examine the networks from the perspective of “pathway schemas,” or recurring patterns of interaction among different types of proteins. Proteins in these schemas tend to act as functional units within diverse biological processes. We discuss computational methods for automatically uncovering statistically overrepresented schemas in protein-protein interaction maps and touch upon the comparative-interactomics aspects of this problem. Coming back to the task of improving our understanding of protein function, we conclude by demonstrating how overrepresented schemas can suggest new insights into the biological function of proteins.