This chapter examines some of the available techniques for analyzing a protein interaction network (PIN) when depicted as an undirected graph. Within this graph, algorithms have been developed which identify “notable” smaller building blocks called network motifs. The authors examine these algorithms by dividing them into two broad categories based on two de?nitions of “notable”: (a) statistically-based methods and (b) frequency-based methods. They describe how these two classes of algorithms differ not only in terms of ef?ciency, but also in terms of the type of results that they report. Some publicly-available programs are demonstrated as part of their comparison. While most of the techniques are generic and were originally proposed for other types of networks, the focus of this chapter is on the application of these methods and software tools to PINs.
TopMotivation
The analysis of protein interaction networks (hereafter abbreviated as PIN) is based on the work on many types of networks, including other biological networks and even the structure between web pages on the World Wide Web. Because of this, we explore the motivation for analyzing a PIN by occasionally digressing to other types of networks.
A PIN can be represented as an undirected graph G such that each node represents a protein and unweighted edges are placed between two nodes if an interaction exists between them. By depicting proteins in this manner, we can examine the patterns of interacting proteins.
Starting at the node-level, one such analysis examines the number of immediate neighbors of each node, which is defined as the degree. Using tools such as the power law, it has been shown that PINs and other biological networks are scale-free based on the distribution of the node degrees (Barabási & Albert, 1999). That is, many nodes have few edges and few nodes are hub nodes and have many edges. In the context of PINs, this means that a random loss of a protein would have a small effect on the overall biological system. However, a focussed attack on a specific protein could have severe consequences if it was a hub node.
Motifs represent the next level in biological network analysis. According to one definition, they are small subgraphs which are repeated and conserved and used to form the building blocks of larger modules (Wolf & Arkin, 2003). However, as suggested by Wolf and Arkin, the separation between motifs and modules is unclear and remains a topic for future work. In their work and the subsequent review by Alon (2007), functionality was the focus of the definition of a motif, and in both cases, the discussion was centered on transcription regulation networks.
An alternate view of motifs is to focus on the topology of the network by giving priority to the configuration of each motif. If motifs are found through their structure, they can then be used to describe the structure and functionality of the PIN. Wuchty, Oltvai, and Barabási (2003) showed that certain topological motifs are important since they are conserved through evolution. To arrive at this conclusion, protein interaction data of yeast (S. cerevisiae) was shown to have certain motifs of two to five nodes which also existed in 5 higher eukaryotes. In a more recent study, the evolution of the yeast PIN was modeled from a “preduplication network” by inferring the duplication and divergence of genes using motifs from a PIN (Presser, Elowitz, Kellis, & Kishony, 2008).