PMC:1481596 / 32548-37865 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":"Methods\n\nComputing clique trees\nWe use an elegant and efficient strategy for chordal graph recognition outlined in [19]. We use an algorithm from [25] to compute all clique trees for a chordal graph.\n\nA compact boolean representation of functional groups\nRecall that a functional group corresponds to a maximal clique in the modified protein interaction network, with modifications being addition of edges between every pair of weak siblings and then addition of edges that eliminate all the squares in the graph. The edge addition is such that no maximal clique in the modified graph contains an induced P4 formed entirely by the added edges. Following lemma guarantees that every functional group is a cograph and therefore admits a compact Boolean representation.\nLemma For every functional group, a subgraph of the original graph induced by the members of the group contains an induced P4 if and only if the set of edges added by our algorithm contains an induced P4.\nProof The argument follows from Figure 5. Indeed, (v1, v2, v3, v4) is a P4 in the original graph if and only if (v3, v1, v4, v2) is a P4 formed by the added edges.\nFigure 5 P4. A P4 in the subgraph induced by the members of a functional group corresponds to a P4 in the set of added edges. Solid lines correspond to the original edges and dashed lines correspond to the added edges.\n\nEdge addition\nWe use a reduction to the Minimum Vertex Cover problem to find all minimal sets of up to k edges that eliminate all the squares in the graph.\nEach eliminating set of edges, S = {e1,..., er}, is assigned a cost:\nwhere sim(ei) takes values between 1.0 and 0.0, and measures our confidence in adding ei to the graph. Since the addition of ei = (ui, vi) implies an interaction or functional equivalence between proteins ui and vi, we chose sim(ei) to be the amount of overlap between the neighborhoods of ui and vi, i.e., sim(ei) = , where (vi) denotes a set of neighbors of node vi in the graph. Intuitively, sim(ei) measures how close ui and vi are to being a pair of weak siblings. If ui and vi have the same neighborhoods then sim(ei) = 1.0; as the overlap between the neighborhoods decreases, sim(ei) goes to 0.0. Then, we pick an edge set with the minimum cost from all the edge sets that do not form a P4, which is entirely contained in one of the maximal cliques of the modified graph. The last requirement is necessary to ensure that each functional group is a cograph.\n\nReduction to the minimum vertex cover\nA square in a graph can be eliminated by adding one or both of its diagonals (chords) to the graph. For example, a graph in Figure 6 has two squares: (A, B, C, D) and (A, B, E, D). Note that (B, C, D, E) is not a square as one of its diagonals, (C, E), is an edge in the graph. The square (A, B, C, D) can be eliminated if either edge (A, C) or (B, D) is added to the graph. Furthermore, a single diagonal can eliminate more than one square. For example, the diagonal (B, D)eliminates both squares. We are interested in finding all minimal sets of diagonals of size up to k that eliminate all the squares in the graph.\nFigure 6 VC Reduction. A graph and a corresponding \"square coverage graph\". We reduce the above problem to the Minimum Vertex Cover problem. The squares in the original graph become edges and diagonals become vertices in the new graph. Thus the original graph is transformed to a \"square coverage\" graph, which in turn serves as an input to the Minimum Vertex Cover problem. In the Minimum Vertex Cover problem we are given a graph and are asked to find the smallest set of vertices that cover all the edges in the graph. An edge is covered if at least one of its end points is selected. Coming back to our example, it can be easily seen that {(B, D)} is the minimum vertex cover (Figure 6). Although the Minimum Vertex Cover problem is an NP-hard problem, if the size of the optimum solution is small an efficient algorithm can be obtained. In other words the Minimum Vertex Cover problem is fixed parameter tractable. We use an O(2k(n + m)) algorithm [26] to identify all minimal sets of edges of size up to k that eliminate all the squares in the graph.\n\nGraphs that have tree of complexes representation\nThe COD method is not guaranteed to produce the Tree of Complexes representation for every possible protein interaction network. How can a family of graphs that admit Tree of Complexes representation be characterized? First, we argue that chordal graphs belong to this family. It can be shown that addition of edges that connect weak siblings does not introduce chordless cycles to the graph. Therefore, after all weak siblings are connected the graph is still chordal and thus admits Tree of Complexes representation. Next, we argue that cographs admit Tree of Complexes representation. Our methods eliminates all the squares in the graph, unless every possible set of eliminating edges forms a P4, which is entirely contained in one of the maximal cliques of the modified graph. It can be shown that the latter case is possible only when the original graph contains a P4, and thus is not a cograph. We conjecture that graphs that admit Tree of Complexes representation are exactly those graphs that admit a clique tree representation, with the nodes being maximal cographs rather than maximal cliques.","divisions":[{"label":"title","span":{"begin":0,"end":7}},{"label":"sec","span":{"begin":9,"end":199}},{"label":"title","span":{"begin":9,"end":31}},{"label":"p","span":{"begin":32,"end":199}},{"label":"sec","span":{"begin":201,"end":1355}},{"label":"title","span":{"begin":201,"end":254}},{"label":"p","span":{"begin":255,"end":766}},{"label":"p","span":{"begin":767,"end":971}},{"label":"p","span":{"begin":972,"end":1135}},{"label":"figure","span":{"begin":1136,"end":1355}},{"label":"label","span":{"begin":1136,"end":1144}},{"label":"caption","span":{"begin":1146,"end":1355}},{"label":"p","span":{"begin":1146,"end":1355}},{"label":"sec","span":{"begin":1357,"end":2446}},{"label":"title","span":{"begin":1357,"end":1370}},{"label":"p","span":{"begin":1371,"end":1512}},{"label":"p","span":{"begin":1513,"end":1581}},{"label":"p","span":{"begin":1582,"end":2446}},{"label":"sec","span":{"begin":2448,"end":4162}},{"label":"title","span":{"begin":2448,"end":2485}},{"label":"p","span":{"begin":2486,"end":3104}},{"label":"figure","span":{"begin":3105,"end":3181}},{"label":"label","span":{"begin":3105,"end":3113}},{"label":"caption","span":{"begin":3115,"end":3181}},{"label":"p","span":{"begin":3115,"end":3181}},{"label":"p","span":{"begin":3182,"end":4162}},{"label":"title","span":{"begin":4164,"end":4213}}],"tracks":[]}