Modular decomposition of protein-protein interaction networks

Abstract

We introduce an algorithmic method, termed modular decomposition, that defines the organization of protein-interaction networks as a hierarchy of nested modules. Modular decomposition derives the logical rules of how to combine proteins into the actual functional complexes by identifying groups of proteins acting as a single unit (sub-complexes) and those that can be alternatively exchanged in a set of similar complexes. The method is applied to experimental data on the pro-inflammatory tumor necrosis factor-alpha (TNF-alpha)/NFkappaB transcription factor pathway.

Figure 1

A graph and its modules. By definition, a module is a set of nodes that have the same neighbors outside the module. In addition to the trivial modules {a},{b},...,{g} and {a,b,c,..,g}, this graph contains the modules {a,b,c}, {a,b},{a,c},{b,c} and {e,f}.

Figure 2

Modular decomposition of the example graph in Figure 1. Modular decomposition gives a labeled tree that represents iterations of particular quotients, here the successive quotients on the modules {a,b,c} and {e,f}. Series are labeled by an asterisk within a circle, parallel by two parallel lines within a circle, and prime by a P within a circle. The prime is advantageously labeled by its structure. The graph can be retrieved from the tree on the right by recursively expanding the modules using the information in the labels. Therefore, the labeled tree can be seen as an exact alternative representation of the graph.

Figure 3

Interpretation of graph and module labels for systematic PCP experiments. (a) Two neighbors in the network are proteins occurring in a same complex. (b) Several potential sets of complexes can be the origin of the same observed network. Restricting interpretation to the simplest model (top right), the series module reads as a logical AND between its members. (c) A module labeled parallel corresponds to proteins or modules working as strict alternatives with respect to their common neighbors. (d) The prime case is a structure where none of the two previous cases occurs. Symbols are as in Figure 2.

Figure 4

Cliques and maximal clique. A clique is a fully connected sub-graph, that is, a set of nodes that are all neighbors of each other. In this example, the whole graph is a clique and consequently any subset of it is also a clique, for example {a,c,d,e} or {b,e}. A maximal clique is a clique that is not contained in any larger clique. Here only {a,b,c,d,e} is a maximal clique.

Figure 5

Three examples of modular decomposition of protein-protein interaction networks. In each case from top to bottom: schema of complexes, the corresponding protein-protein interaction network as determined from PCP experiments, and its modular decomposition (MOD). (a) Protein phosphatase 2A. Parallel modules group proteins that do not interact but are functionally equivalent. Here these are the catalytic Pph21 and Pph22 (module 2) and the regulatory Cdc55 and Rts1 (module 3). (b) RNA polymerases (RNAP) I, II and III. A good layout of the corresponding network gives an intuitive idea of what the constitutive units of the complexes are. Modular decomposition extracts them and makes their logical combinations explicit. (c) Transcriptional regulator complexes (see text for details). Modular decomposition condenses the network to its backbone prime structure (root of the tree) and identifies its constitutive units.

Figure 6

Investigating NFκB variants. Modular decomposition of NFκB members relB, c-rel, p50 and p52 delivers the potential NFκB dimers and tetramers. All combinations are possible (series) except those including both relB and c-rel (parallel), and those including both p50 and p52.

Figure 7

Analysis of the partners of NFκB members in resting cells. (a) Modular decomposition of the network of NFκB members and their partners. The network is composed of the NFκB members as defined in Figure 6 and their interactors. In this step, interactions among the interactors are disregarded. Symbols for the proteins are as defined in [21]. Baits are outlined in green. Modular decomposition organizes the interactors into modules. The root is a prime whose structure is shown in the encircled network. Module 1 and module 2, respectively, group the new interactors into activators and inhibitors of NFκB. (b) Further purifications using IKKα, IκB-α, IκB-β and Cot/Tpl2 as baits resolve the interactions between module 1 and module 2 members and suggest a complex composed of ABIN2 and Cot/Tpl2 as a NFκB modulation mechanism alternative to IKKα, IκB-α, IκB-β.