Quantitative Comparison of Networks

The main idea to quantitatevely characterize the differences in two networks.

Here we use two measures:
The edit score, D_E. Qualitatevely it tells us how many changes/edits one has to do in one network to obtain the other. Assume that we know which nodes in network A and B should be paired. For networks of the same size, we define edit score as the number of insertions or removals of edges (regulatory connections) one has to perform on network A to obtain B.
D_E(A,B) = sum_{i,j}|A_{ij} - B_{ij}|

For example when comparing gene regulatory netowrk of lambda with 186 we obtain $D_E(186,\lambda)=32$. That is, the 186 network of 45 proteins and 64 connections can be constructed by making 32 edits of the connections in a 45 protein subset of the $\lambda$ network (adding/removing a link is a single edit, changing the sign of a connections needs two edits).

The elements $A_{ij}$ and $B_{ij}$ specify whether the direct regulation of $i$ on protein $j$ is positive, negative or absent and are constructed such that each element can keep both positive and negative links. In case we do not know which nodes in networks A and B should be paired, we need to find the optimal identification of nodes between them. To do so, we define an alignment procedure through the Metropolis algorithm designed to reach the minimal distance $D$ between the networks: Given two nodes and their corresponding partners in the other network the elementary step is to switch partners and reevaluate the distance. Iterating this procedure and using simulated annealing the method converges to a global minimum. This yields the minimal distance between the networks, as well as an optimal alignment of the individual nodes.

Signaling difference $D_S$, which aims at capturing both direct (as in $D_E$) and also indirect regulation through a sequence of intermediate proteins. For each pair of proteins ($i,j$), we consider whether $i$ sends a signal to $j$, and if so whether the signal along the shortest path is positive or negative. In this spirit we define the sign of a signal as the product of the signs of all links on the shortest path from $i$ to $j$.

You can compare between

• 5 samples of gene regulatory networks (186, lambda, Yeast, B. Subtilis, P22): Just click on the button with the name (top left corner of each panel) and the network will appear.
• Each of the above networks can be randomized by clicking on "Random" button.
• You can put in your own network, it should be in the form
  a b 1
  c d -1
  b c 1
  First column is the source, second -- target and third is the sign of the link. E.g. a has a positive link to b, and c has a negative link to d. To get your network just paste it in this format in the text field to the left and click on "OK".

Clicking on "Edit Score, D_E" or signaling score "D_S" would give you the difference measures described in "Method" section.

If the "Show Alignment" tick is selected, you will be able to see how the nodes are pared as a result of the minimization of the difference scores D_E or D_S. Also in each graph nodes will be placed/"frozen" in similarly after the minimization procedure.

You can freeze any node by clicking on it with the right button on your mouse,
This is usefull if you want to fix your network somewhere in the center.