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.

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.

ADD COMMENT
• link
updated 23 months ago by
Ram
44k
•
written 8.9 years ago by
Rob
6.8k

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.

"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?

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?

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.

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.

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 ?

"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?

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?

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.

the library looks like:

Different cell lines and different drugs.

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

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

Is it clear now?

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.

Rows are genes, columns are also genes. Activations are represented as

`1`

, Inhibition as`-1`

and no interaction as`0`

. Example: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 ?