Power Graph Analysis Tool

Command line tool for converting graphs
into power graphs

Usage

The command line tool reads widely used graph file formats (i.e. sif) and converts them into power graphs in the BBL format (described below). Several parameters can be given. Please download the archive, unzip it, and check the batch files for further instructions:

BBL format specifications

The BBL format is the main output format of the Power Graph. A BBL file describes nodes, groups of nodes (power nodes), as well as the edges between these groups of nodes (power edges). Each line contains a piece of information of the following type:

• NODE {node identifier} -- Defines a single node
• SET {power node identifier} -- Defines a power node
• IN {power node identifier} {power node identifier} -- Defines a 'in'-relationship between two power nodes or between a node and a power node - The first is contained in the second
• EDGE {node or power node identifier} {node or power node identifier} [{confidence value}] -- Defines a power edge between two power nodes

What can I do with the power graph?

First we recommend reading our paper for examples:
"Unraveling protein networks with Power Graph Analysis"
Loic Royer, Matthias Reimann, Bill Andreopoulos, Michael Schroeder
PLoS Computational Biology, July 2008

Also, before doing power graph analysis computationally, we suggest first to look at them visually on our interactive example page (examples) or using the cytoscape plugin (plugin). What follows is probably of more interest to bioinformaticians and computational biologists.

The command line tool output is the BBL file. This file contains a representation the power graph. The power graph consists of both a hierarchical clustering of the nodes in the network in the form of the power node hierarchy, but as well the stars, cliques, and bicliques connecting these sets in the hierarchy.

Examples of information that can be mined is:

• Look at power nodes that are cliques or the end point of a biclique. Power nodes are usually enriched in nodes having something in common. Depending on the network, that can be:
  
  • domains and motifs in the case of protein interactions
  • common transcription binding sites in the case of bipartite Tf to target genes networks.
  • conserved domain architecture in the case of protein homology/paralogy networks
  • for other networks it can be any property that could be signaled by the topology of the network


• Look at cliques in the network. Cliques are found in the BBL file as power nodes connected to themselves:
  EDGE powernode1 powernode 1


• Also interesting are big bicliques between two large power nodes. Bicliques are found in the BBL file as a single EDGE line between two large power nodes (in the sense that they contain many nodes):
  
  ...
  SET powernode1
  SET powernode2
  IN node1 powernode1
  IN node2 powernode1
  ...
  IN node100 powernode1
  
  IN node101 powernode2
  IN node102 powernode2
  ...
  IN node200 powernode2
  
  EDGE powernode1 powernode 2
  ...
  


• Examine power nodes deep in the hierarchy. These correspond to nodes that are at the core of a group of nodes. This is usually a hint that these nodes have something important in common.
  In the following example power node deep is at depth 4 in the hierarchy:
  
  ...
  IN powernode1 powernode0
  IN powernode2 powernode1
  IN powernode3 powernode2
  IN deep powernode3
  ...
  


• Examine cross-links between two power nodes distant in the hierarchy. While having similar neighbors in the network does not necessarily mean you are directly connected, having different neighbors and yet being connected can be in some cases an interesting pattern to mine (see homology network example in PLoS CB paper). In the following example power node deep1 and deep2 are in very different regions of the network but are linked by a biclique - a systematic link between all their members:
  
  ...
  IN powernode1 powernode0
  IN powernode2 powernode1
  IN powernode3 powernode2
  IN deep1 powernode3
  
  IN powernode5 powernode4
  IN powernode6 powernode5
  IN powernode7 powernode6
  IN deep2 powernode7
  
  EDGE deep1 deep2 ...