Network Comparison by comparing two different adjacency matrices
2
1
Entering edit mode
8.9 years ago

Is it possible to compare 2 adjacency matrices of 2 different networks to see how much similar or different they are (based on edges similarity or differences).

Adjacency matrices here represent the contextualized network of genes interactions in a drug treated gene expression profile. Activations are represented as 1, Inhibition as -1 and no interaction as 0.

Any help will be appreciated.

Network adjacencyMatrix R • 10k views
1
Entering edit mode
8.9 years ago
Rob 6.8k

If the networks are different, this is, in general, a hard problem (i.e. hard in the computational complexity sense) --- depending on what you want the comparison to measure. As you state, the adjacency matrix is simply a representation of the underlying network, and what you want to do here seems akin to network alignment. If you have labels for all the nodes --- that is, if you know for each node in the underlying network, the node in the other network to which it should correspond, then you can simply permute one of the matrices to match the other (i.e. to put the nodes into correspondence), and then compare the values in the rows / columns directly. However, if you have no mapping (or a highly incomplete one), which is the general case, then you must first find a good alignment / correspondence between these networks. For that, there is a vast wealth of literature depending on the particular variant of the problem you want to solve, but you can start out by looking at "biological network alignment", and seeing some of the references you're able to track down.

1
Entering edit mode
8.9 years ago

Without more information, it's hard to give you precise answers. If you're interested in the topological differences, then as Rob suggested, you can look at network alignment algorithms. You could also compare the values of various statistics such as various centrality measures, degree distributions, presence of various motifs... If the nodes in the two networks match, you could compute similarity measures between the row/column vectors. Finally, you can compute general measures of similarity between two networks using graph kernels (not to be confused with kernels on graph nodes). However, I would also suggest to consider whether the question you're trying to answer by comparing these networks could be answered in a different and maybe easier way.

0
Entering edit mode

"If the nodes in the two networks match, you could compute similarity measures between the row/column vectors"

Some of the nodes are similar in the networks to be compared. Can you explain what do you mean by 'row/column vectors' and how to compute the similarity measures in this case?

0
Entering edit mode

If your two networks have the same nodes, then the rows and columns of the two matrices can be paired because they represent the same nodes. You can then compute any measure of similarity between these pairs of vectors. If you care about all the nodes and only a subset of the nodes are common, you can represent the missing ones in one matrix by introducing corresponding rows and columns filled with 0s.

Are the nodes in you networks genes (i.e. you have gene x gene matrices) or are you dealing with bipartite graphs (i.e. you have gene x drug matrices) ? And what is the question you're trying to address?

0
Entering edit mode

I have a library of gene expression data (many instances of 'Control -> Drug1 -> Treated') I will create the adjacency matrices representing the 'control' and 'treated' networks.

0
Entering edit mode

the library looks like:

Control -> Drug 1 -> Treated
Control -> Drug 2 -> Treated
Control -> Drug N -> Treated


Different cell lines and different drugs.

0
Entering edit mode

I still don't see what your networks/matrices are.

0
Entering edit mode

Network1 (represent control state) and Network2 (represent treated state)

Is it clear now?

0
Entering edit mode

No. What are the nodes? Are they genes? Or alternatively what is represented by the rows and columns of your matrix? Your initial post suggested that rows are genes and columns are conditions and each matrix cell value represent whether the corresponding gene is activated/inhibited under the corresponding condition. However, this could also be interpreted as a gene by gene matrix where the cell values represent whether the two genes are both activated/inhibited.

0
Entering edit mode

Rows are genes, columns are also genes. Activations are represented as 1, Inhibition as -1 and no interaction as 0. Example:

          AANAT  ABCA1    ABCA6
AANAT      0      -1       1
ABCA1      1       0      -1
ABCA6     -1       0       0

0
Entering edit mode

I would have then thought the matrices to be symmetric (e.g. ABCA1-AANAT = AANAT-ABCA1 = 1 means AANAT and ABCA1 are both activated under the condition represented by the matrix) but in your example it's not. Should we then interpret ABCA6-AANAT = -1 to mean AANAT inhibits ABCA6 and AANAT-ABCA6 = 1 to mean that AANAT activates ABCA6 under the same condition ?
Also I am not completely clear on the question you want to answer with this. Do you want to know if your drug of interest gives the same response as the same drug in a reference data set ? If so why is comparing the gene expression profiles unsuitable ?