PMC:1481596 / 8512-27023 JSONTXT

{"target":"https://pubannotation.org/docs/sourcedb/PMC/sourceid/1481596","sourcedb":"PMC","sourceid":"1481596","source_url":"https://www.ncbi.nlm.nih.gov/pmc/1481596","text":"Results and discussion\nOne way to represent a set of overlapping functional groups is to construct a graph with nodes representing functional groups and edges representing overlaps, i.e., there exists an edge between two functional groups if and only if they share at least one protein. This approach has two shortcomings. First, it is not obvious how to correctly identify functional groups, and second, such a representation does not provide any information about the dynamics of proteins in the network. We propose a graph-theoretical approach, which, under the assumption that the protein interaction network satisfies certain mathematical properties, identifies functional groups and provides a representation of overlaps between functional groups in the form of the Tree of Complexes.\nHere, we first describe the COD method. Then, we demonstrate the utility of our approach by applying the COD method to several examples, derived from high-throughput experiments, TNFα/NF-κB and pheromone signaling pathway interaction networks.\n\nComplex overlap decomposition\nOur method of representing overlapping functional groups, which is depicted in Figure 1, builds on chordal and cograph graph theories. Chordal graphs constitute an important and well studied graph family [18,19]. A chord in a graph is any edge that connects two non-consecutive nodes of a cycle. A chordal graph is a graph which does not contain chordless cycles of length greater than three.\nFigure 1 Complex Overlap Decomposition. A simplified illustration of the Complex Overlap Decomposition (COD) method. An edge, (3, 4), connecting a pair of weak siblings is added to the graph. A fill-in edge between proteins 5 and 8 is added to eliminate all five 4-cycles in the graph: {5, 6, 8, 7}, {1, 5, 7, 8}, {2, 5, 7, 8}, {1, 5, 6, 8}, and {2, 5, 6, 8}. If the modified graph is chordal, all clique tree representations are computed (cf. Methods). Each clique tree representation results in a Tree of Complexes representation, where the Tree of Complexes is constructed by projecting each maximal clique in the modified graph, G*, to a functional group in the original graph G. For example, a four node maximal clique, {1, 2, 5, 8}, in G* is projected to a four node functional group in G, by removing a fill-in edge (5, 8). Each functional group is represented by a Boolean expression, such as (1 ∧ 2) ∧ (5 ∨ 8), which means that the functional group contains two variants of a complex, {1, 2, 5} and {1, 2, 8}. An important property of chordal graphs, which is explored directly in this paper, is that every chordal graph has a corresponding clique tree representation or clique tree [17]. The nodes in the tree are maximal cliques. Moreover, for every node in the graph, a set of maximal cliques that contain this node form a connected subgraph of the clique tree. Thus, there is a mapping between the nodes in the graph and subtrees in the clique tree. The \"connected subgraph\" requirement puts constraints on the topology of the clique tree. In fact, the topology of the tree is determined by the structure of overlaps between the maximal cliques in the graph. Thus, the clique tree captures information about the structure of the overlaps, which is lost in a simple clique intersection graph as shown in the example below.\nExample Consider a hypothetical protein interaction network in Figure 2(a). This network is chordal and its maximal cliques are listed in Figure 2(b). We want to contrast the clique tree representation in Figure 2(d) to a naive representation in Figure 2(c), where every pair of maximal cliques that contain a protein in common is connected by an edge.\nFigure 2 A Hypothetical Protein Interaction Network. (a) A hypothetical protein interaction network. (b) A list of all maximal cliques in the network. (c) A naive representation of overlaps between maximal cliques. Each maximal clique is a node and there is an edge between two maximal cliques if and only if they share a protein. (d) The clique tree representation. Once again, every maximal clique is a node, but the cliques are connected in such a way that the resulting graph is a tree. Moreover, cliques that contain a given protein form a connected subgraph. (e) This color scheme is used to show the subtree of every protein. For example, protein 3 is contained in maximal cliques A, B, and C, which is shown by placing yellow dots above the maximal cliques. While both representations show the overlap between maximal cliques, the interconnection pattern of cliques in the naive representation carries little additional information about the structure of this overlap. On the other hand, a very specific tree-like interconnection pattern in the clique tree representation can expose a special structure of such overlap. For example, consider maximal cliques B through F. In the naive representation, the overlap between these maximal cliques is collapsed to a clique. Thus, the representation treats the maximal cliques and overlaps between them equally. In particular, there is no way to tell that, for example, D occupies a more central position in the network than B. In the clique tree representation this information can be extracted from the relative position of cliques in the tree. For example, B is connected to F by a path that passes through C and D, which means that any protein shared by B and F is also contained in C and D. In other words, the overlap between B and F is entirely contained in the overlap between B and D, which in turn is entirely contained in the overlap between B and C. Thus, there is a correlation between the amount of overlap between maximal cliques and their distance in the clique tree.\nNice properties of the clique tree mentioned above make it a good choice for representation of overlaps between functional groups. However, not every protein interaction network is chordal and maximal cliques may not always be the best way to represent functional groups. For example, in Figure 1, cliques {1, 2, 3} and {1, 2, 4} may correspond to two variants of one complex, where proteins 3 and 4 replace each other, forming one rather than two functional groups. Therefore, in the COD decomposition we relax the assumption that every functional group is a single protein complex (maximal clique) and allow it to contain several protein complexes (maximal cliques). In doing so we have to ensure that a functional group is not just any collection of protein complexes but rather a set of closely related protein complexes which represent possible variants of one complex (such as complexes {1, 2, 3} and {1, 2, 4} in the above example). To capture this systematically we model a functional group with a graph from a family of graphs known as cographs.\nCographs are another well-studied graph family [20]. A cograph can be characterized by an absence of an induced subgraph which is a path of length four (P4), where the length is the number of nodes in the path. Thus, the diameter of a connected cograph is at most two. Subsequently, connected cographs are dense and cliquish, consistently with the assumption made by algorithms that delineate protein complexes. What makes cographs even more attractive is that for every cograph there exists a Boolean expression which describes all the maximal cliques in the graph. (In terms of modular decomposition used in [16] it means that a cograph can be decomposed by modular decomposition without leaving non-trivial non-decomposable prime module.) This Booolean expression describes in a compact and hierarchical way all the possible variants of protein complex within a functional group.\nThe main idea behind COD method is to provide a representation of a functional module, which is analogous to the clique tree, in which nodes are cographs (representing variants of protein complex within a functional group) rather than maximal cliques. If we knew in advance all the functional groups in the module, we could simply connect the proteins within each functional group turning it into a clique and, under the assumption that the resulting graph is chordal, apply clique tree construction algorithm to the graph. Since we do not have predefined functional groups, our algorithm identifies them by adding edges to the graph in such a way that each added edge connects a pair of nodes that putatively belong to the same functional group.\nThe COD method's edge addition strategy and its biological motivation builds on a concept of weak siblings. We call a pair of nodes weak siblings if and only if they are connected to the exactly the same set of neighbors, but are not connected to each other. In terms of protein interaction networks, weak siblings are proteins which interact with the same set of proteins but do not interact with each other. In particular, proteins that can substitute each other in a protein interaction network may have this property. Similarly, a pair of proteins that belong to the same complex but are not connected due to missing data or an experimental error will be represented as weak siblings. Since the weak siblings relationship suggests functional similarity, the COD method takes a first step towards delineation of functional groups by connecting every pair of weak siblings by an edge. As this modification may also eliminate some of the chordless cycles of length four (squares) in the graph, functional group delineation happens simultaneously with transformation of the protein interaction graph into a chordal graph.\nIf, after connecting all pairs of weak siblings, the resulting graph is not chordal, the COD method attempts to transform it to chordal by adding some additional edges. Consistently with our assumption that we connect only nodes corresponding to proteins that could be put in the same functional group, we impose restrictions on this \"fill-in\" process. Namely, we require that, each introduced edge connects a pair of nodes which are close to being weak siblings. In such case the new edge is a diagonal of one or more squares in the graph. We emphasize that adding edges between nodes of longer cycles has no such justification. To summarize our edge addition procedure, our method attempts to eliminate all the squares in the protein interaction network by adding a limited set of diagonals that satisfies following conditions (i) connects potentially functionally equivalent proteins, as measured by the overlap in neighborhoods or distance from being a pair of weak siblings; (ii) ensures that functional groups correspond to cographs; we argue that this condition is guaranteed if the set of added edges does not form a P4 in a maximal clique of the modified graph (cf. Methods);\nIf the modification step succeeds, i.e., the modified graph is chordal, all the clique tree representations of the modified graph are computed and then each clique tree is extended to a Tree of Complexes representation of the original graph. The COD algorithm keeps track of all the edge additions and uses this information to delineate functional groups by projecting each maximal clique onto original network and removing all introduced edges contained in the clique. For example, in the modified graph of Figure 1 a maximal clique with four nodes, {1, 2, 5, 8}, is projected to a functional group by removing an edge connecting proteins 5 and 8. This functional group contains two variants of a protein complex, {1, 2, 5} and {1, 2, 8}, which are compactly represented by a (1 ∧ 2) ∧ (5 ∨ 8) Boolean expression. If, on the other hand, the modified graph is not chordal, the COD method stops without producing the representation. Since the clique tree representation for a chordal graph is not unique, the Tree of Complexes representation that derives from it is not unique either. As all clique trees of a chordal graph have the same set of nodes (the nodes are the maximal cliques in the graph), the difference between clique trees comes from the topology of the tree. The clique tree topology is determined by the \"connected subgraph\" constraints and restriction power of these constraints depends on the structure of the underlying graph, i.e., there are graphs with a unique clique tree representation and there are graphs for which almost any tree that spans all the maximal cliques in the graph is a valid clique tree. As a result a protein interaction network may have several Tree of Complexes representations; all such representations will have the same functional groups but will differ in the way these functional groups are interconnected. For every protein interaction network analyzed bellow we explicitly state all the possible Tree of Complexes representations.\n\nTNFα/NF-κB signaling pathway\nTo illustrate the power of COD in elucidating the dynamics behind protein complexes, we consider the TNFα/NF-κB signaling pathway. The Nuclear Factor κB (NF-κB) family of transcription factors is activated in response to a diverse set of stress stimuli, which includes pro-inflammatory cytokines, e.g., TNFα. In vertebrates, this family includes p50, p52, Rel A, c-Rel, and Rel B, which bind to the DNA in a homo or heterodimeric fashion. The NF-κB activity is regulated by the IκB family of proteins via inhibitory ankyrin repeat domains. This family includes IκBα, IκBβ, and IκB∈. The precursors of p50 (p105) and p52 (pl00) also possess ankyrin repeat domains and thus act as inhibitors. These precursors can also form dimers with other members of the NF-κB family. The activation with the pro-inflammatory cytokine tumor necrosis factor TNFα triggers a signaling cascade, which, in particular, stimulates the activation of the IKKα, IKKβ, and IKKγ functional groups. The IKKs initiate a signal induced degradation of the inhibitors (IκBs), and subsequent nuclear translocation of the transcription factor. Recent TAP experiments [5] provide a wealth of new information regarding this important signaling pathway. Bouwmeester et al. identified 221 molecular associations, out of which only 80 where previously known. Gagneur et al. [16] applied modular decomposition to the network of these associations but the decomposition halted quickly at large non-decomposable modules.\nWe used the COD method to analyze the subnetwork spanning all the paths from NIK (NFκB-inducing kinase phosphorylating IKKα and IKKβ) with at most three edges. For the purpose of the analysis, we contracted all five members of NF-κB family into one node. As the resulting protein interaction network, shown in Figure 3(a), is chordal without weak siblings, functional groups correspond to maximal cliques in the network.\nFigure 3 TNFα/NF-κB Signaling Pathway. The TNFα/NF-κB signaling pathway. (a) The network. (b) The Tree of Complexes representation. The flow of action is visually represented by background colors: green for activators (IKKs) and yellow for inhibitors (IκBs, and p100). The NIK kinase is in the first functional group (A), together with all three members of the IKK complex and p100. Functional group B includes, in addition to p100, the IKKs and two inhibitors IκBα and IκBβ. This group is the beginning of interaction between IKKs and IκBs. Functional group C loses some of the IKKs, continues to show IκB and begins to show interaction between IκBs and NF-κB factors. Finally, in group E we see the entrance of NIK-independent Col-Tpl2 kinase. For this network, there are two alternative Tree of Complexes representations: functional group E can be connected to either D or C. The representation that maximizes the number of leaves is shown in Figure 3(b). One can clearly see the interplay between the activators and inhibitors. Proteins p105 and NF-κB participate in the same functional groups and thus follow the same path in the tree. The same is true for the pair of proteins IkBα and IkBβ. The Tree of Complexes captures this by grouping p105 and NF-κB, and IkBα and IkBβ.\n\nPheromone signaling pathway\nThe yeast Saccharomyces cerevisiae may be present in one of two haploid cell types, which are able to mate. Pheromones released by one type of cell bind to a specific receptor of the other type. This triggers the activation of a scaffold protein-bound mitogen-activated protein kinase (MAPK) cascade and subsequent activation of nuclear proteins that control subsequent cellular events. In a recent paper, Spirin et al. [13] identified a subnetwork of proteins involved in this process within a yeast protein interaction network [21]. We analyzed this subnetwork using the COD to see if our method can extract elements of temporal ordering. The subnetwork identified by Spirin et al. and its Tree of Complexes representation is given in Figure 4. In this case, the protein network is not chordal. First, the COD method identifies and connects a pair of weak siblings, MKKl and MKK2 .Then, to transform the network to a chordal graph, three additional edges are added: (SPH1, SPA2), (FUS3, KSS1), and (STE11, STE7). In this case, some functional groups will contain more than one protein complex.\nFigure 4 Pheromone Signaling Pathway. The pheromone signaling pathway. (a) The network. (b) The Tree of Complexes representation. For the description of the elements of the tree see the text. This network admits six different Tree of Complexes representations: (i) functional group H can be connected to either B or C; (ii) any interconnection pattern that spans groups E, F, and G can be chosen. If we ask for a tree with maximum number of leaves, the number of tree variants is reduced to two (option (i)).\nThe MAPK cascade module consists of three sequentially acting protein kinases: MAP kinase kinase kinase (STE11) MAP kinase kinase (STE7) and MAP kinase (KSS1, FUS3) [22]. MKKl and MKK2 are two redundant protein kinase kinases (most similar to STE7) [23]. Their redundancy is properly captured by the ∨ (OR) in their functional group (H). The MAP kinases KSS1 and FUS3 are two separate kinases both activated by STE7 each of which is essential for a different program: FUS3 – for mating; KSS1 – for the filamentous growth [24]. Once again this is correctly captured by ∨ (OR) in groups F and G. STE5 is a scaffold protein of the MAPK module. It recruits MAPK module kinases (STE11, STE7, FUS3). This is consistent with the central position of a functional group containing STE5 in the tree and relative to the paths of STE7, STE11 and FUS3. Finally, nuclear proteins DIG1 and DIG2 (necessary for transcription inhibition, which are regulated by both FUS3 and KSS1) enter at the endpoint (node F) in the tree.","divisions":[{"label":"title","span":{"begin":0,"end":22}},{"label":"p","span":{"begin":23,"end":790}},{"label":"p","span":{"begin":791,"end":1034}},{"label":"sec","span":{"begin":1036,"end":12656}},{"label":"title","span":{"begin":1036,"end":1065}},{"label":"p","span":{"begin":1066,"end":1458}},{"label":"figure","span":{"begin":1459,"end":2478}},{"label":"label","span":{"begin":1459,"end":1467}},{"label":"caption","span":{"begin":1469,"end":2478}},{"label":"p","span":{"begin":1469,"end":2478}},{"label":"p","span":{"begin":2479,"end":3294}},{"label":"p","span":{"begin":3295,"end":3647}},{"label":"figure","span":{"begin":3648,"end":4414}},{"label":"label","span":{"begin":3648,"end":3656}},{"label":"caption","span":{"begin":3658,"end":4414}},{"label":"p","span":{"begin":3658,"end":4414}},{"label":"p","span":{"begin":4415,"end":5683}},{"label":"p","span":{"begin":5684,"end":6738}},{"label":"p","span":{"begin":6739,"end":7621}},{"label":"p","span":{"begin":7622,"end":8368}},{"label":"p","span":{"begin":8369,"end":9490}},{"label":"p","span":{"begin":9491,"end":10675}},{"label":"p","span":{"begin":10676,"end":12656}},{"label":"sec","span":{"begin":12658,"end":15868}},{"label":"title","span":{"begin":12658,"end":12686}},{"label":"p","span":{"begin":12687,"end":14165}},{"label":"p","span":{"begin":14166,"end":14586}},{"label":"figure","span":{"begin":14587,"end":15333}},{"label":"label","span":{"begin":14587,"end":14595}},{"label":"caption","span":{"begin":14597,"end":15333}},{"label":"p","span":{"begin":14597,"end":15333}},{"label":"p","span":{"begin":15334,"end":15868}},{"label":"title","span":{"begin":15870,"end":15897}},{"label":"p","span":{"begin":15898,"end":16993}},{"label":"figure","span":{"begin":16994,"end":17186}},{"label":"label","span":{"begin":16994,"end":17002}},{"label":"caption","span":{"begin":17004,"end":17186}},{"label":"p","span":{"begin":17004,"end":17186}},{"label":"p","span":{"begin":17187,"end":17503}}],"tracks":[{"project":"2_test","denotations":[{"id":"16722537-15287979-1694488","span":{"begin":7350,"end":7352},"obj":"15287979"},{"id":"16722537-14743216-1694489","span":{"begin":13821,"end":13822},"obj":"14743216"},{"id":"16722537-15287979-1694490","span":{"begin":14023,"end":14025},"obj":"15287979"},{"id":"16722537-14517352-1694491","span":{"begin":16319,"end":16321},"obj":"14517352"},{"id":"16722537-11752246-1694492","span":{"begin":16428,"end":16430},"obj":"11752246"},{"id":"16722537-15567849-1694493","span":{"begin":17670,"end":17672},"obj":"15567849"},{"id":"16722537-8386320-1694494","span":{"begin":17754,"end":17756},"obj":"8386320"},{"id":"16722537-15692041-1694495","span":{"begin":18026,"end":18028},"obj":"15692041"}],"attributes":[{"subj":"16722537-15287979-1694488","pred":"source","obj":"2_test"},{"subj":"16722537-14743216-1694489","pred":"source","obj":"2_test"},{"subj":"16722537-15287979-1694490","pred":"source","obj":"2_test"},{"subj":"16722537-14517352-1694491","pred":"source","obj":"2_test"},{"subj":"16722537-11752246-1694492","pred":"source","obj":"2_test"},{"subj":"16722537-15567849-1694493","pred":"source","obj":"2_test"},{"subj":"16722537-8386320-1694494","pred":"source","obj":"2_test"},{"subj":"16722537-15692041-1694495","pred":"source","obj":"2_test"}]}],"config":{"attribute types":[{"pred":"source","value type":"selection","values":[{"id":"2_test","color":"#ec93dd","default":true}]}]}}