# pvalue calculation of protein-protein network with permutation test

Note: this question has also been asked on Biostars

I have performed a network recreation analysis based on the interactions of proteins from String db.

I wanted to know if the interactions have significance by reshuffling the proteins with permutation against the background network. Since, its first time for me to perform permutation test on PPI, Can someone guide me to a tool or a tutorial to perform permutation test on newly created PPI network.

I tried looking at a youtube tutorial and read some articles like this one, but they were not very useful for my purpose.

• What kind of permutation test you want to do with your network? What do you want to permutate (and in which programming language)? In R you could use boost to permute – llrs Sep 21 '17 at 10:42
• Please edit your question and explain exactly what type of permutation you need. Do you need to keep the edges the same and randomize the nodes? The nodes the same and the edges randomized? Randomize both but keep the same number of nodes/edges? Something else? – terdon Sep 21 '17 at 12:22
• There is probably not a tool so you'll have to code it yourself. You need to provide more information to help everyone help you. How did you come across this list of proteins? Having a list of differentially expressed proteins that are known to interact in STRING might be enough to prove your hypothesis. Do you have an appreciation for when permutations are appropriate? Will doing permutations help prove or disprove your hypothesis? What do you mean by reshuffling the proteins? See Terdon's comment. Are you permuting the proteins in your list and not the sample labels? – pstew Sep 28 '17 at 15:39

It is probably necessary to correct for the degree distribution of the network, I am not sure that a tool such as the Mantel test will quite do this (as suggested by user Michael G.). In naturally occurring networks degree distribution is a strong confounder.

Then again I am not totally sure what shape your data is in or what the question is. You mention a background network, but I am not sure what this is or how you want to use it. Possibly your network reconstruction is a subset of your background network? In which case you just define the rule for how your subsample is drawn and then you compare it to permuted networks.

However, here is some fairly crude but serviceable R code that implements a general purpose network rewiring test, using igraph. I am not using a background network as again I'm not sure what it is.

(Python also has igraph so should be similar rewire() function)

compute_measure = function(network) {
# i don't know what you are measuring, so you have to write this function.
# this function takes a graph object as input
# this function returns a single numeric value (whatever you're measuring) as output
}

# "net" is a network of the graph type from igraph

measure = compute_measure(net)

num_perms = 1000

perm_measures = c()

for (i in 1:num_perms) {
# permute the network by rewiring, rewire 10x as many times as edges
# to ensure saturation
perm_net = rewire(net, with = keeping_degseq(niter = gsize(net) * 10))
perm_measures[i] = compute_measure(perm_net)
}

# one-sided monte carlo p value is proportion of rewirings (plus one) greater than your measure
p_value = (1 + length(which(perm_measures >= measure))) / num_perms


If on the other hand you are just trying to come up with a single permutation of the edges of your network to compare against, you can run rewire() only once to get that permuted network. It depends on what question you are trying to answer, and what null hypothesis you're trying to get a p value for.

Two answers: What you have asked for is a straight Mantel's test. You could read up on the test, it is traditionally used to assess genetic vs geographic distance but could be applied. This is easy to do in R:

mantel.test(m1, m2, nperm = 999, graph = FALSE,
alternative = "two.sided",  ...)


You will need to import your data (recommend csv) and parse to a data.frame both for your observed (m1) and expected (m2). Its easy.

The documentation is here. My advice is to think carefully about the contruction of the matrix: its an everything versus everything comparison.

Alternative approach My personal choice would be to use a covariance/correlation matrix. That can be done in R too, but you need to understand what covariance is and how it relates to your problem. If you don't really get covariance, I'd leave it. Hence I'll avoid putting code down - but is part of ggplot2.

Please note, I don't supply detailed codes (I'm not your supervisor), unless its Perl, which this isn't