Topology and function in protein interaction networks (thesis)

Abstract:

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.