BACKGROUND
the advent of high throughput technologies has driven the development of cell biology over the last decades.
the diffusion of microarrays and next generation sequencing techniques has made available a large amount of data that can be used to increase our understanding of gene expression.
the need to analyse and interpret these data has led to the development of new methods to infer relationships between genes, which require a combination of biological knowledge, statistical modelling and computational techniques.
when the first data on gene expression became available, they were usually analysed considering each gene separately.
however, researchers soon realized that genes act in a concerted manner, and that cellular processes are the result of complex interactions between different genes and molecules.
nowadays, sets of genes that are responsible for many cellular functions have been identified, and are collected in publicly available databases  <cit> .
one of the advantages of these sets of genes, whose function is already known, is that they can be used to interpret the results of new experiments: this has led to the implementation of a large number of methods for gene enrichment analysis  <cit> .
their aim is to compare gene expression levels under two different conditions , and to detect which sets of genes are differentially expressed  in the experimental condition.
to this end, genes are ordered in a list l in decreasing order of differential expression, and enrichment is then tested in different ways.
singular enrichment analysis  <cit>  tests the over or under-representation of functional gene sets within the set of genes defined by the first k top genes in l. the major limitations of this approach lie in the fact that the choice of k is arbitrary, and that the test does not take into account gene expression levels.
gene set enrichment analysis  <cit>  overcomes these limitations, by making use of the whole list l of genes, and testing the tendency of genes belonging to a functional set to occupy positions at the top  of l. a limitation that is common to both single and gene set enrichment analysis, however, is that these methods base computations on the level of overlap between sets of genes only, without considering associations and interactions between genes.
gene networks are an established tool to represent these interactions.
in network inference  <cit> , genes or molecules are represented as nodes of a graph and their interactions are modelled as links between the nodes.
these links can be represented as either a directed or an undirected edge, and a graph is called directed if all edges are directed, undirected if every edge is undirected and partially directed  otherwise  <cit> .
an undirected edge displays association between two genes, while a directed edge posits a direction in the relationship between them.
network estimation represents a difficult task, and many different estimation methods have been proposed  <cit> .
marback et al.
<cit>  classified them into six groups and pointed out that their predictive performance can vary a lot within each group and according to the structure of the network.
in order to integrate evidence on gene associations unveiled by a number of experimental and computational studies into a single network, curated gene networks for different species have been proposed, including yeastnet  <cit>  and funcoup  <cit> .
in an attempt to integrate the information on interactions between genes provided by gene networks into enrichment analyses, researchers have recently developed methods for network enrichment analysis .
the idea, here, is to test enrichment between sets of genes in a network.
shojaie and michaidilis  <cit>  focus mainly on network inference, proposing to represent the gene network with a linear mixed model, so that enrichment tests can be then computed by testing a system of linear hypotheses on the fixed effect parameters of the model.
glaab et al.
<cit> , alexeyenko et al.
<cit>  and mccormack et al.
<cit> , instead, assume that a gene network is already available  and focus their attention on the strategy that can be used to assess enrichment between sets of nodes.
in particular, glaab et al.
<cit>  propose a network enrichment score based on a suitably defined network distance between two sets of nodes, alongside an empirical method for setting a cut-off on this distance.
in contrast to this, alexeyenko et al.
<cit>  and mccormack et al.
<cit>  derive network enrichment scores on the basis of statistical tests against the null distribution of no enrichment.
the advantage of the approach proposed by alexeyenko et al.
and mccormack et al.
is that the assessment of enrichment is based on a significance testing procedure.
the idea of  <cit>  is that the presence of enrichment between two sets of genes, say a and b, can be assessed by comparing the number of links connecting nodes in a and b with a reference distribution, which models the number of links between the same two sets in the absence of enrichment.
both  <cit>  and  <cit>  assume that the reference distribution is approximately normal, and they obtain its mean and variance by means of permutations, i.e., computing the mean and variance of the number of links between a and b in a sequence of random replications of the network.
their tests rely on algorithms that permute the network, and mainly differ between themselves for the fact that each algorithm aims to preserve different topological properties of the original network in the generation of network replicates.
these methods, however, suffer from three limitations.
first of all, they require the simulation of a large number of permuted networks, an activity that can be computationally intensive and highly time consuming .
furthermore, they base the computation of the test on a normal approximation for the reference distribution, whose nature is discrete.
mccormack et al.
<cit>  show that such an approximation is inaccurate when the expected number of links between a and b is small.
a further drawback of these methods is that they have been implemented so far only for undirected networks.
in this work we build upon the approach of  <cit>  and propose an alternative test which we call neat .
the main idea behind this test is that, under the null hypothesis of no enrichment, the number of links between two gene sets a and b follows an hypergeometric distribution.
this enables us to model the reference distribution directly via a discrete distribution, without having to resort to a normal approximation.
neat does not require network permutations to compute mean and variance under the null hypothesis, and is therefore faster than the existing resampling-based methods.
moreover, we develop neat not only for undirected, but also for directed and partially directed networks, thus providing a common framework for the analysis of different types of networks.
methods
the starting point of enrichment analyses is the identification of one or more gene sets of interest.
these target gene sets are typically groups of genes that are differentially expressed between experimental conditions, but they can also be different types of gene sets: e.g., clusters of genes that are functionally similar in a given time course, or genes that are bound by a particular protein in a chip-chip or chip-seq experiment.
enrichment analysis provides a characterization of each target gene set by testing whether some known functional gene sets can be related to it.
methods for gene enrichment analysis assess the relationship between a target gene set and each functional gene set simply by considering the overlap of these two groups.
in contrast to this, network enrichment analysis incorporates an evaluation of the level of association between genes in the target set and genes in the functional gene set into the test.
information on associations and dependences between genes is represented by a network, which consists of a set of n nodes v={v <dig> …,vn} that are connected by edges .
each gene is thus represented as a node vi of the network, and a link between two nodes is drawn to signify interaction between the corresponding genes.
examples of genome-wide curated networks that collect known gene associations are yeastnet  <cit>  and funcoup  <cit> .
a natural way to study the relation between two sets of genes a and b in a network is to consider the presence or absence of links connecting nodes in the two groups  <cit> .
in the inferred network, we expect that individual links may be slightly unstable and noisy.
however, we do expect that the inferred links contain a sign of the relationships between gene sets.
so, although links between individual genes in sets a and b may be noisy, if there is a functional relationship between functions described by sets a and b we expect the number of links between the two groups to be larger  than expected by chance.
if this is the case, we say that there is enrichment between a and b.
links between two nodes of a network can be either directed  or undirected.
the presence of an arrow between two genes implies a directionality in the relation between them, whereas an undirected edge does not provide information on the direction of the relation.
the upcoming subsection considers directed networks.
in this case, one can distinguish two cases: whether genes in the target set regulate genes of the functional set, or genes in the functional gene set regulate genes in the target set .
this distinction does not occur for undirected networks, which are the subject of the next subsection: in this case, a and b are exchangeable, and we simply talk of enrichment “between” a and b. a workflow diagram summarizing the input and the output of neat is shown in fig.
<dig>
fig.
<dig> workflow diagram of a typical network enrichment analysis with neat
enrichment test for directed networks
in a directed network, we assess the presence of enrichment from a to b by considering the number of arrows going from genes in a to genes belonging to b. we denote this by nab.
the observed nab can be thought of as a realization from a random variable nab, with expected value μab.
to assess the relation from a to b, we compare μab with the number of arrows that we would expect to observe from a to b by chance, which we denote as μ <dig>  we say that there is enrichment from a to b if μab is different from μ <dig>  furthermore, we say that there is over-enrichment from a to b if μab is higher than μ <dig>  and under-enrichment  if μab is lower than μ <dig>
we propose a test based on the hypergeometric distribution to assess the significance of this difference.
the motivation behind this choice is the following.
the hypergeometric distribution models the number of successes in a random sample without replacement: in our case, we can mark arrows in the network that reach genes in b as “successful”, and the remaining ones as “unsuccessful”.
then, we can view the arrows that go out from genes in a as a random sample without replacement from the population of arrows present in the graph: if there is no relation  between a and b, then the distribution of nab  is
<dig> nab∼hypergeom,
where the sample size oa is the outdegree of a , the number of successful cases in the population ib is the indegree  of b and the population size iv is the total indegree of the network .
it is certainly possible to imagine alternative choices for the null distribution of nab.
alexeyenko et al.
<cit>  and mccormack et al.
<cit>  assume that nab is normal with mean μ <dig> and variance σ <dig>  and they use network permutations to estimate μ <dig> and σ <dig>  however, the normal distribution is continuous and symmetric, so that their choice implies somehow that the behaviour of nab should be roughly symmetric, and could be well approximated with a continuous random variable.
in addition, estimation of μ <dig> and σ <dig> by means of network permutations can be highly time consuming.
alternatively, one could consider for nab an hypergeometric distribution with different parameters, defined for example, by considering all possible edges in the network  as a population.
we prefer model  over this alternative, because the choice of the parameters therein allows to condition on two quantities that we consider crucial, which are the outdegree of a and the indegree of b. moreover, in our experience so far, we have observed that tests based on alternative parametrizations often result in poor performances.
the null mean and variance of nab can be immediately derived from model .
in particular, in the absence of enrichment we expect to observe, on average, μ0=oaibiv arrows from nodes in a to nodes in b. thus, we expect μ <dig> to increase as the number of arrows leaving a, or reaching b, increases.
biological assessment of enrichment can therefore be carried out by testing the null hypothesis of no enrichment
h0:μab=μ <dig>  against the alternative hypothesis of enrichment
h1:μab≠μ <dig>
in a test with a discrete test statistic and two-sided alternative, such as the one that we propose, the p-value can be computed in different ways .
let t be a discrete test statistic and t be the observed value of t. a first possibility is to compute the p-value for the two-tailed test by doubling the one-tailed p-value, p1= <dig> min, where p <dig> denotes the distribution of t under the null hypothesis.
an evident drawback of this formula, however, is that p <dig> can exceed  <dig>  and therefore p <dig> does not represent a probability.
even though a simple modification p2= min could avoid the problem, we prefer to subtract p <dig> from p <dig>  is non-null for discrete t, and this is the reason why p <dig> can exceed 1) and to compute the p-value using
<dig> p=2min+p0=2minp <dig> p0+p <dig>
which always lies within the interval  <cit>  and differs from p <dig> by a factor equal to p <dig>  a p-value close to  <dig> can be regarded as evidence of enrichment, because it entails that the number of links from a to b is significantly smaller or higher than we would expect it to be in the absence of enrichment.
therefore, for a given type i error probability α, we conclude that there is evidence of enrichment from a to b if p<α, while if p≥α there is not enough evidence of enrichment.
as an example, consider the network in fig.
<dig>  suppose that we are interested to test whether there is enrichment from the set a={ <dig> } to the set b={ <dig> ,7}.
it can be observed that there are  <dig> arrows going out from a, and  <dig> of them reach b. the whole network consists of  <dig> arrows, of which  <dig> reach b. thus, nab= <dig>  oa= <dig>  ib= <dig> and iv= <dig>  the idea behind  is that, if the  <dig> arrows that are going out from a are a random sample  from the  <dig> arrows that are present in the network, then the proportion of arrows reaching b from a should be close to the proportion of arrows reaching b in the whole network, and in the absence of enrichment we should observe on average μ0= <dig>  edges.
in this case, it seems that arrows going out from a tend to reach b more frequently  than other arrows do .
however, the computation of the p-value leads to p= <dig> : the observed nab= <dig> does not provide enough evidence to reject the null hypothesis, so that the conclusion of the test is that there is no enrichment from a to b.
fig.
<dig> example: neat in directed networks.
left: directed network consisting of  <dig> nodes connected by  <dig> arrows.
set a contains nodes  <dig> and  <dig>  and set b nodes  <dig>   <dig> and  <dig> .
right: bipartite representation of the same network: it can be observed that n
ab= <dig>  o
a= <dig>  i
b= <dig> and i
v= <dig>  it follows that μ
0= <dig>  and p= <dig>
we can also consider sets b={ <dig> ,7} and c={ <dig> } , and test enrichment from b to c. in this case, nbc= <dig> arrows out of ob= <dig>  reach c from b, whereas in the whole network ic= <dig> arrows out of dv= <dig>  reach c. the null expectation is here μ0= <dig> ; if we fix the type i error probability equal to α= <dig> %, the p-value p= <dig>  leads to the conclusion that there is enrichment from b to c.
enrichment test for undirected networks
when dealing with undirected networks, the presence of enrichment between a and b is assessed considering the number of edges that connect genes in a to genes in b. we denote this by nab.
given the undirected nature of the links in the network, there is no distinction between indegree and outdegree of a node, and it only makes sense to consider the degree of a node, which is the number of vertices that are linked to that node.
the null distribution  should thus be adapted accordingly.
let us define the total degree ds of a set s as the sum of the degrees of nodes that belong to it: then, in the absence of enrichment we can view nab as the number of successes in a random sample of size da, drawn from a population of size dv.
the null distribution of nab for undirected networks is thus
nab∼hypergeom,  where da, db and dv are the total degrees of sets a,b and v.
the null hypothesis is then that μab=μ0=dadbdv, the alternative that μab≠μ <dig>  the p-value is computed using formula .
as an example, consider the network in fig.
3a and suppose that we are interested to test the presence of enrichment between the pairs of sets ,  and .
sets a and b are linked by nab= <dig> edges, and their degrees are da= <dig> and db= <dig>  while dv= <dig>  thus, μ0= <dig>  and pab= <dig> .
in the same way, it is possible to compute pac= <dig>  and pbc= <dig> .
figure 3b shows the relation between the three sets fixing α= <dig> %: enrichment is present between the pairs  and , but not between sets a and c.
fig.
<dig> example: neat in undirected networks.
left: undirected network with  <dig> nodes.
we are interested to infer the relation between sets a , b  and c .
right: representation of the relations between sets: enrichment is detected between sets a and b  and between sets b and c , but not between sets a and c
enrichment test for partially directed networks
a partially directed network  is a network where both directed and undirected edges are present.
it is possible to view such a network as a directed network, where every undirected edge connecting two nodes v and w represents in fact a pair of arrows, the former going from v to w and the latter from w to v. if such an adaptation is adopted, model  can be applied and partially directed networks can be analysed within neat as directed networks.
software
neat is implemented in the r package neat  <cit> , which can be freely downloaded from cran: https://cran.r-project.org/package=neat.
the manual and a vignette illustrating the package are also available from the same url.
the package allows users to specify the network in different formats, it includes functions to plot and summarize the results of the analysis and is accompanied by a set of data and examples, including the enrichment analysis of the esr gene sets that we discuss in the upcoming section.
RESULTS
performance evaluation
we assess the performance of neat by means of simulations.
table  <dig> summarizes some aspects of these simulations, that are the subject of the next two subsections.
the r scripts and data files for each simulation can be found at https://github.com/m-signo/neat.
we first consider directed networks, and check whether the performance of neat is influenced by the degree distribution of the network, or by the level of overlap between sets of nodes.
we then consider undirected networks, and carry out a comparison of neat with the nea test of  <cit>  and with the lp, la, la+s and np tests of  <cit> .
in simulations s <dig> and s <dig>  we compare the performance of neat in two directed networks with different degree distribution.
in simulation s <dig>  we check the performance of the test for different levels of overlap, ranging from  <dig> to  <dig> %.
in simulations s <dig> and s <dig>  we compare neat to alternative tests in two undirected networks with different degree distribution
we compare the performance of the methods under the null hypothesis by checking whether the empirical distribution of p-values in the absence of enrichment is uniform using the kolmogorov-smirnov test, and by computing the following ratios:
r1=number of enrichments at1%level <dig> ×number of tests whereh0is true  and
r5=number of enrichments at5%level <dig> ×number of tests whereh0is true.
the idea behind r <dig> and r <dig> is that if the null hypothesis h <dig> is true, we expect a good test to reject it with a frequency that is close to α. so, the target value for r <dig> and r <dig> is  <dig>
furthermore, we compare the capacity of different tests to correctly detect enrichments and non-enrichments by computing specificity and sensitivity at α= <dig> % level, and the area under the roc curve .
the specificity is the proportion of correctly detected non-enrichments, and we expect it to be as close as possible to 1−α.
the sensitivity indicates the proportion of correctly detected enrichments, whereas the auc is a measure of the overall capacity of a test to discriminate enrichments and non-enrichments across all values of α. therefore, a test will show a good performance whenever it achieves a specificity close to 1−α, and values of sensitivity and auc as high as possible .
simulation with directed networks
in simulations s <dig> and s <dig>  we generate two random networks with  <dig> nodes and with fixed indegree and outdegree distributions using the algorithm implemented by  <cit> .
the indegree and outdegree distributions of nodes are power law with exponent  <dig> and minimum degree  <dig> in simulation s <dig>  and a mixture of two poisson distributions, with parameters λ1= <dig> and λ2= <dig> and weights q1= <dig> % and q2= <dig> %, in simulation s <dig>
we consider  <dig> sets of nodes whose size ranges between  <dig> and  <dig>  and we test enrichment from a to b and from b to a for every pair of sets: this means that, in total, we compute 50×49= <dig> tests.
in the original networks, no preferential attachment  between any couple of these sets is present; we generate enrichments by increasing or reducing the number of arrows for  <dig> pairs of sets.
in each case, enrichment is created by adding or removing arrows randomly from one group to the other, in such a way that nab increases or reduces by a proportion uniformly ranging from  <dig> to  <dig> %.
table  <dig> performance of neat in simulations s <dig> and s2
p
ks
r
1
r
5
p
ks denotes the p-value of the kolmogorov-smirnov test for uniform distribution, auc is an abbreviation for “area under the roc curve”.
in both simulations, the distribution of p-values under h
<dig> is uniform and the specificity is close to the expected  <dig> % value.
sensitivity and auc are higher in simulation s2
in simulation s <dig> we check whether the proportion of overlap between sets a and b, that we measure with the jaccard index
jab=|a∩b|/|a∪b|,  could have an effect on specificity and sensitivity.
we consider the same network used in simulation s <dig>  and we test enrichment between pairs of sets with fixed size |a|=|b|= <dig>  but with increasing overlap .
under h <dig> we do not modify the network, whereas under h <dig> we introduce enrichments adding  <dig> arrows going from genes in a to genes in b. for every value of overlap, we consider  <dig> test .
figure  <dig> shows that the specificity remains constant and close to  <dig> % for any level of overlap; the sensitivity, on the other hand, is slightly higher when the level of overlap is moderate.
fig.
<dig> specificity and sensitivity in simulation s <dig>  the plot shows the values of specificity and sensitivity for different levels of overlap .
we observe that the specificity of the test does not vary substantially for different levels of overlap, and is always close to  <dig> % as expected.
the sensitivity, instead, slightly reduces as the percentage of overlap increases
simulation with undirected networks
as alternative methods for network enrichment analysis are available for undirected networks only, we compare neat with them in two simulations where we consider undirected networks with  <dig> nodes.
we generate two random networks with fixed degree distribution, using the algorithm implemented by  <cit> ; the degree distribution follows a power law in simulation s <dig> and a mixture of poisson distributions in simulation s <dig>  with the same parameters used in simulations s <dig> and s <dig>  likewise, we consider  <dig> sets of nodes, whose sizes vary between  <dig> and  <dig> nodes.
we test enrichment between every pair of sets a and b, so that the total number of comparisons is here 50×49/2= <dig>  we introduce enrichments for  <dig> pairs of sets by adding or removing edges randomly between them, in such a way that nab is increased or reduced by a proportion uniformly ranging from  <dig> to  <dig> %.
tables  <dig> and  <dig> show the results for simulations s <dig> and s <dig>  respectively.
as concerns the behaviour under the null hypothesis, the distribution of p-values is uniform in both cases for neat and la, and in one case for la+s  and np .
nea and lp, instead, do not produce uniform distributions: as it can be observed from fig.
<dig>  the reason is that the distribution is strongly left-skewed for nea, whereas for lp the distribution is right-skewed .
in both simulations, most of the methods achieve a specificity close to  <dig> % as expected; comparison with the other tests shows that the sensitivity and auc of neat are overall good.
fig.
<dig> histogram of p-values in absence of enrichment in simulation s <dig>  the test of kolmogorov-smirnov indicates that the distribution is uniform for neat , la  and np .
the distribution of p-values is highly left-skewed for nea, and right-skewed for lp
p
ks
r
1
r
5
<dig>
<dig>
<dig> %
<dig> %
<dig>
<dig>
<dig> %
<dig> %
<dig>
<dig> %
<dig>
<dig> %
<dig>
<dig> %
<dig>
<dig> %
the best results for each indicator are in bold.
p
ks denotes the p-value of the kolmogorov-smirnov test for uniform distribution, auc is an abbreviation for “area under the roc curve”.
the distribution of p-values under h
<dig> is evidently not uniform for nea and lp.
neat shows the highest values of sensitivity and auc, and its specificity is close to the target value
p
ks
r
1
r
5
<dig>
<dig>
<dig> %
<dig> %
<dig>
<dig> %
<dig>
<dig>
<dig>
<dig>
the best results for each indicator are in bold.
p
ks denotes the p-value of the kolmogorov-smirnov test for uniform distribution, auc is an abbreviation for “area under the roc curve”.
the distribution of p-values under h
<dig> can be considered uniform for neat, la and np, and is questionable for la+s.
neat shows the highest values of sensitivity and auc, and its specificity is exactly equal to the target value
table  <dig> speed comparison
r package neat
r package neagui
the table compares the time  that each method required to compute  <dig> tests for enrichment in simulations s <dig> and s <dig>  using a processor with  <dig>  ghz cpu frequency.
neat turns out to be by far the fastest method
network enrichment analysis: an application to yeast
the budding yeast saccharomyces cerevisiae is a unicellular eukaryote organism that can be easily grown in laboratory.
because of these features, it represents a model organism that has been extensively studied, and it was the first eukaryote whose genome was completely sequenced  <cit> .
since then, a large number of studies has aimed to detect associations between genes.
in an attempt to collect these results into a unique source, kim et al.
<cit>  developed yeastnet, an undirected gene network that aims to integrate the results of a large number of high-throughput studies on saccharomyces cerevisiae.
in its most recent version , yeastnet comprises  <dig> edges connecting  <dig> genes.
we use this network of known associations in the following analyses.
network enrichment analysis of environmental stress response in yeast
after analysing gene expression patterns of yeast saccharomyces cerevisiae in response to different stressful stimuli, gasch et al.
<cit>  inferred the existence of a set of  <dig> genes that reacted in a similar way to different, hostile environmental changes.
this set of genes, called environmental stress response , is believed to constitute a coordinated, initial reaction to the emergence of any hostile condition in the cell.
it consists of two subgroups of genes, containing genes that are repressed and induced under stressful conditions, respectively.
we take these two gene sets as target sets, and for each of them we test enrichment with the following functional gene sets:  <dig> gene sets that are part of the go slim biological process ontology  and  <dig> known kegg pathways.
at α= <dig> % level, neat detects over-enrichment between  <dig> go slim sets and the set of repressed genes, and between  <dig> go slim sets and the set of induced genes.
furthermore,  <dig> kegg pathways are found to be over-enriched with the set of repressed esr genes, and  <dig> with the set of induced genes.
gasch et al.
<cit>  reports that genes that are repressed in the esr are involved in growth related processes, various aspects of rna metabolism, nucleotide biosyntesis, secretion, encoding of ribosomal proteins and other metabolic processes.
these results are in strong agreement with the list of over-enrichments detected by neat, shown in table  <dig>  as a matter of fact, most of the over-enrichments detected by neat are related to rna transcription, nucleotide secretion and translation of ribosomal proteins , growth-related processes  and further metabolic processes .
n
ab
μ
0
log
the table lists the  <dig> go slim bp gene sets and the  <dig> kegg pathways which the set of repressed esr genes is found to be over-enriched with at  <dig> % significance level
gasch et al.
<cit>  observed that inference for the set of genes that are induced by the esr is more complicated, because most of the genes in this group lack functional annotations.
it is worthwhile to observe that neat detects a large number of enriched kegg pathways .
this preliminary observation points out a major feature of the environmental stress response: the cell reacts to the emergence of different hostile conditions by activating a number of known cellular pathways that involve energy production, metabolic reactions and molecular transportation .
our results for this gene set do not only match the ones of the original study - identifying many processes and pathways that are related to carbohydrate metabolism , fatty acid metabolism , mythocondrial functions and cellular redox reactions , protein folding and degradation  and cellular protection during stressful conditions  - but they also unveil further enrichments that involve molecular transportation  and amino-acid metabolism .
n
ab
μ
0
log
the table lists the  <dig> go slim bp gene sets which the set of induced esr genes is found to be over-enriched with at  <dig> % significance level
n
ab
μ
0
log
the table lists the  <dig> kegg pathways which the set of induced esr genes is found to be over-enriched with at  <dig> % significance level
tables  <dig>   <dig> and  <dig> compare the p-values obtained with neat with those obtained with la+s  <cit> , which, according to the conclusions of  <cit>  and to our own simulations, can be considered as the main competitor of neat.
the tables show a large overlap between the over-enrichments detected by the two methods at a  <dig> % significance level: the two methods jointly detect  <dig> over-enrichments  for the set of repressed esr genes, and  <dig>  for the set of induced esr genes.
there is only a small number of discrepancies between the two methods and these are mostly borderline cases.
in particular, la+s detects  <dig> over-enrichments that are not detected by neat , whereas neat detects  <dig> over-enrichments that are not detected by la+s .
as concerns computing time, neat computed the required task  in  <dig> s, whereas the same computation with la+s required  <dig>  s. in summary, the two methods lead to very similar conclusions, but neat is considerably more efficient.
μ
0
the table reports the gene sets that are found to be over-enriched  by at least one of the two methods.
μ
<dig> denotes the expected value of n
ab in the absence of enrichment.
the last two columns report log
10
p-values for the proposed neat and the la+s test of  <cit> , respectively
μ
0
the table reports the gene sets that are found to be over-enriched  by at least one of the two methods.
μ
<dig> denotes the expected value of n
ab in the absence of enrichment.
the last two columns report log
10
p-values for the proposed neat and the la+s test of  <cit> , respectively
μ
0
the table reports the gene sets that are found to be over-enriched  by at least one of the two methods.
μ
<dig> denotes the expected value of n
ab in absence of enrichment.
the last two columns report log
10
p-values for the proposed neat and the la+s test of  <cit> , respectively
network enrichment analysis of go slim sets: overlap does not imply enrichment
gene ontologies  <cit>  consist of a large number of gene sets, which are involved in different cellular functions or biological processes, or that are active in a specific component of the cell.
these sets of genes are typically employed to enrich sets of differentially expressed genes that have been experimentally detected .
however, network enrichment analysis is a more general instrument, which allows to assess the relation between pairs of gene sets in a network.
one might wonder, for instance, whether gene sets within an ontology tend to be strongly related to each other, or whether there is a strong separation between them.
we consider gene sets in the go slim biological process ontology for saccharomyces cerevisiae .
as a result of the hierarchical structure of gene ontologies,  <dig> gene sets are nested within another group.
we exclude these  <dig> sets from the analysis: the remaining  <dig> gene sets do not have hierarchical relations with each other, and pairs of these sets display overall a low overlap , which is null in most cases .
if overlapping of sets was taken by itself as evidence of a relation between two gene sets, one would therefore conclude that most of these gene sets are unrelated.
if, however, we do not limit our attention to the overlap between pairs of sets, but consider also known associations between genes in the two sets as represented in yeastnet  <cit> , we obtain a different conclusion.
we have used neat to test whether there is enrichment between each pair of sets.
in a random network where no relations between the sets are present, we would expect to detect  <dig> enrichments  out of  <dig> tests for α= <dig> %; instead, we detect  <dig> enrichments,  <dig> times more than expected.
out of these,  <dig> are under-enrichments, and  <dig> are over-enrichments.
an under-enrichment, here, indicates that two go slim sets are poorly connected to each other: the high number of under-enrichments, therefore, might be not particularly surprising or interesting, as we do expect that unrelated gene sets within the ontology are poorly connected.
the high number of over-enrichments, on the other hand, is striking: this indicates that many groups within the ontology are highly connected to each other - something that would occur rather rarely, if there was no relation between the sets.
this result points out a major difference between gene enrichment analysis and network enrichment analysis: whereas in the first case the extent of overlapping between two gene sets is taken by itself as evidence of enrichment, network enrichment analysis bases the evaluation of enrichment on the level of connectivity that exists between the two sets in a network.
of course, the two facts are not completely unrelated.
figure  <dig> shows that there is a certain correlation between overlap of gene sets  and network enrichment, so that we tend to find network enrichment in the presence of higher levels of overlap.
this correlation is, however, low , pointing out that there does not necessarily have to be enrichment for highly overlapping gene sets, and vice versa.
as an example, the go slim sets “cytokinesis” and “nuclear organization” do not share genes, but are detected as enriched  in yeastnet.
this result can be explained by the fact that “nuclear organization” includes genes involved in the assembly and disassembly of the nucleus, which is a preliminary step in cell cytokinesis.
fig.
<dig> relation between overlap  and p-values.
note that p-values are represented on a negative log-scale to enhance readability
CONCLUSIONS
network enrichment analysis is a powerful extension of traditional methods of gene enrichment analysis, that allows to integrate them with the information on connectivity between genes provided by genetic networks.
whereas gene enrichment analysis bases the test for enrichment solely on the overlap between two gene sets and ignores the relationships between individual genes, network enrichment analysis exploits a larger amount of information by making use of gene networks, and it is thus capable to detect enrichment even between two gene sets that do not share genes.
in this paper, we have presented a network enrichment analysis test  that aims to overcome some limitations which affect the network enrichment tests of  <cit> .
first of all, we believe that a normal approximation does not make justice to the discrete nature of nab.
we have shown that this approximation can be avoided if one models nab directly, using a hypergeometric distribution with suitably specified parameters.
in addition, the normal approximation employed by  <cit>  requires the computation of a large number of network permutations to obtain the mean and variance under h0: this operation can be very time consuming for big networks and it makes the computation of the test rather slow.
the use of the hypergeometric distribution, instead, allows to specify the null distribution of nab without resorting to permutations, thus speeding up computations considerably.
a further drawback of existing methods for network enrichment analysis  is that they have been implemented only for undirected networks.
we address this problem by considering different types of networks  and by proposing two different parametrizations, which take into account the different nature of directed and undirected links.
we believe that neat could constitute a flexible and computationally efficient test for network enrichment analysis.
our simulations show that neat has a good capacity to correctly classify enrichments and non-enrichments.
comparison of neat with other methods points out an overall good performance in terms of sensitivity and of specificity, as well as the computational efficiency of the proposed method.
the examples illustrated in the previous section show that neat can retrieve enrichments that were detected with gene enrichment analysis, but it can also unveil further enrichments that would be overlooked, if known associations between genes were ignored.
even though the focus of this paper is on gene regulatory networks, neat is a rather general test: it can be applied to networks that arise in different contexts and disciplines, whenever the interest is to infer the relationship between groups of vertices.
this can include, for example, other types of biological networks, as well as social, economic or technological networks.
abbreviations
aucarea under the roc curve
crancomprehensive r archive network
esrenvironmental stress response
gogene ontology
keggkyoto encyclopedia of genes and genomes
neatnetwork enrichment analysis test

 the advent of high throughput technologies has driven the development of cell biology over the last decades. the diffusion of microarrays and next generation sequencing techniques has made available a large amount of data that can be used to increase our understanding of gene expression. the need to analyse and interpret these data has led to the development of new methods to infer relationships between genes, which require a combination of biological knowledge, statistical modelling and computational techniques. when the first data on gene expression became available, they were usually analysed considering each gene separately. however, researchers soon realized that genes act in a concerted manner, and that cellular processes are the result of complex interactions between different genes and molecules. nowadays, sets of genes that are responsible for many cellular functions have been identified, and are collected in publicly available databases. one of the advantages of these sets of genes, whose function is already known, is that they can be used to interpret the results of new experiments: this has led to the implementation of a large number of methods for gene enrichment analysis. their aim is to compare gene expression levels under two different conditions, and to detect which sets of genes are differentially expressed in the experimental condition. to this end, genes are ordered in a list l in decreasing order of differential expression, and enrichment is then tested in different ways. singular enrichment analysis tests the over or under-representation of functional gene sets within the set of genes defined by the first k top genes in l. the major limitations of this approach lie in the fact that the choice of k is arbitrary, and that the test does not take into account gene expression levels. gene set enrichment analysis overcomes these limitations, by making use of the whole list l of genes, and testing the tendency of genes belonging to a functional set to occupy positions at the top of l. a limitation that is common to both single and gene set enrichment analysis, however, is that these methods base computations on the level of overlap between sets of genes only, without considering associations and interactions between genes. gene networks are an established tool to represent these interactions. in network inference, genes or molecules are represented as nodes of a graph and their interactions are modelled as links between the nodes. these links can be represented as either a directed or an undirected edge, and a graph is called directed if all edges are directed, undirected if every edge is undirected and partially directed otherwise. an undirected edge displays association between two genes, while a directed edge posits a direction in the relationship between them. network estimation represents a difficult task, and many different estimation methods have been proposed. marback et al. classified them into six groups and pointed out that their predictive performance can vary a lot within each group and according to the structure of the network. in order to integrate evidence on gene associations unveiled by a number of experimental and computational studies into a single network, curated gene networks for different species have been proposed, including yeastnet and funcoup. in an attempt to integrate the information on interactions between genes provided by gene networks into enrichment analyses, researchers have recently developed methods for network enrichment analysis. the idea, here, is to test enrichment between sets of genes in a network. shojaie and michaidilis focus mainly on network inference, proposing to represent the gene network with a linear mixed model, so that enrichment tests can be then computed by testing a system of linear hypotheses on the fixed effect parameters of the model. glaab et al., alexeyenko et al. and mccormack et al., instead, assume that a gene network is already available and focus their attention on the strategy that can be used to assess enrichment between sets of nodes. in particular, glaab et al. propose a network enrichment score based on a suitably defined network distance between two sets of nodes, alongside an empirical method for setting a cut-off on this distance. in contrast to this, alexeyenko et al. and mccormack et al. derive network enrichment scores on the basis of statistical tests against the null distribution of no enrichment. the advantage of the approach proposed by alexeyenko et al. and mccormack et al. is that the assessment of enrichment is based on a significance testing procedure. the idea of is that the presence of enrichment between two sets of genes, say a and b, can be assessed by comparing the number of links connecting nodes in a and b with a reference distribution, which models the number of links between the same two sets in the absence of enrichment. both and assume that the reference distribution is approximately normal, and they obtain its mean and variance by means of permutations, i.e., computing the mean and variance of the number of links between a and b in a sequence of random replications of the network. their tests rely on algorithms that permute the network, and mainly differ between themselves for the fact that each algorithm aims to preserve different topological properties of the original network in the generation of network replicates. these methods, however, suffer from three limitations. first of all, they require the simulation of a large number of permuted networks, an activity that can be computationally intensive and highly time consuming. furthermore, they base the computation of the test on a normal approximation for the reference distribution, whose nature is discrete. mccormack et al. show that such an approximation is inaccurate when the expected number of links between a and b is small. a further drawback of these methods is that they have been implemented so far only for undirected networks. in this work we build upon the approach of and propose an alternative test which we call neat. the main idea behind this test is that, under the null hypothesis of no enrichment, the number of links between two gene sets a and b follows an hypergeometric distribution. this enables us to model the reference distribution directly via a discrete distribution, without having to resort to a normal approximation. neat does not require network permutations to compute mean and variance under the null hypothesis, and is therefore faster than the existing resampling-based methods. moreover, we develop neat not only for undirected, but also for directed and partially directed networks, thus providing a common framework for the analysis of different types of networks. methods the starting point of enrichment analyses is the identification of one or more gene sets of interest. these target gene sets are typically groups of genes that are differentially expressed between experimental conditions, but they can also be different types of gene sets: e.g., clusters of genes that are functionally similar in a given time course, or genes that are bound by a particular protein in a chip-chip or chip-seq experiment. enrichment analysis provides a characterization of each target gene set by testing whether some known functional gene sets can be related to it. methods for gene enrichment analysis assess the relationship between a target gene set and each functional gene set simply by considering the overlap of these two groups. in contrast to this, network enrichment analysis incorporates an evaluation of the level of association between genes in the target set and genes in the functional gene set into the test. information on associations and dependences between genes is represented by a network, which consists of a set of n nodes v={v …,vn} that are connected by edges. each gene is thus represented as a node vi of the network, and a link between two nodes is drawn to signify interaction between the corresponding genes. examples of genome-wide curated networks that collect known gene associations are yeastnet and funcoup. a natural way to study the relation between two sets of genes a and b in a network is to consider the presence or absence of links connecting nodes in the two groups. in the inferred network, we expect that individual links may be slightly unstable and noisy. however, we do expect that the inferred links contain a sign of the relationships between gene sets. so, although links between individual genes in sets a and b may be noisy, if there is a functional relationship between functions described by sets a and b we expect the number of links between the two groups to be larger than expected by chance. if this is the case, we say that there is enrichment between a and b. links between two nodes of a network can be either directed or undirected. the presence of an arrow between two genes implies a directionality in the relation between them, whereas an undirected edge does not provide information on the direction of the relation. the upcoming subsection considers directed networks. in this case, one can distinguish two cases: whether genes in the target set regulate genes of the functional set, or genes in the functional gene set regulate genes in the target set. this distinction does not occur for undirected networks, which are the subject of the next subsection: in this case, a and b are exchangeable, and we simply talk of enrichment “between” a and b. a workflow diagram summarizing the input and the output of neat is shown in fig. fig. workflow diagram of a typical network enrichment analysis with neat enrichment test for directed networks in a directed network, we assess the presence of enrichment from a to b by considering the number of arrows going from genes in a to genes belonging to b. we denote this by nab. the observed nab can be thought of as a realization from a random variable nab, with expected value μab. to assess the relation from a to b, we compare μab with the number of arrows that we would expect to observe from a to b by chance, which we denote as μ we say that there is enrichment from a to b if μab is different from μ furthermore, we say that there is over-enrichment from a to b if μab is higher than μ and under-enrichment if μab is lower than μ we propose a test based on the hypergeometric distribution to assess the significance of this difference. the motivation behind this choice is the following. the hypergeometric distribution models the number of successes in a random sample without replacement: in our case, we can mark arrows in the network that reach genes in b as “successful”, and the remaining ones as “unsuccessful”. then, we can view the arrows that go out from genes in a as a random sample without replacement from the population of arrows present in the graph: if there is no relation between a and b, then the distribution of nab is nab∼hypergeom, where the sample size oa is the outdegree of a, the number of successful cases in the population ib is the indegree of b and the population size iv is the total indegree of the network. it is certainly possible to imagine alternative choices for the null distribution of nab. alexeyenko et al. and mccormack et al. assume that nab is normal with mean μ and variance σ and they use network permutations to estimate μ and σ however, the normal distribution is continuous and symmetric, so that their choice implies somehow that the behaviour of nab should be roughly symmetric, and could be well approximated with a continuous random variable. in addition, estimation of μ and σ by means of network permutations can be highly time consuming. alternatively, one could consider for nab an hypergeometric distribution with different parameters, defined for example, by considering all possible edges in the network as a population. we prefer model over this alternative, because the choice of the parameters therein allows to condition on two quantities that we consider crucial, which are the outdegree of a and the indegree of b. moreover, in our experience so far, we have observed that tests based on alternative parametrizations often result in poor performances. the null mean and variance of nab can be immediately derived from model. in particular, in the absence of enrichment we expect to observe, on average, μ0=oaibiv arrows from nodes in a to nodes in b. thus, we expect μ to increase as the number of arrows leaving a, or reaching b, increases. biological assessment of enrichment can therefore be carried out by testing the null hypothesis of no enrichment h0:μab=μ against the alternative hypothesis of enrichment h1:μab≠μ in a test with a discrete test statistic and two-sided alternative, such as the one that we propose, the p-value can be computed in different ways. let t be a discrete test statistic and t be the observed value of t. a first possibility is to compute the p-value for the two-tailed test by doubling the one-tailed p-value, p1= min, where p denotes the distribution of t under the null hypothesis. an evident drawback of this formula, however, is that p can exceed and therefore p does not represent a probability. even though a simple modification p2= min could avoid the problem, we prefer to subtract p from p is non-null for discrete t, and this is the reason why p can exceed 1) and to compute the p-value using p=2min+p0=2minp p0+p which always lies within the interval and differs from p by a factor equal to p a p-value close to can be regarded as evidence of enrichment, because it entails that the number of links from a to b is significantly smaller or higher than we would expect it to be in the absence of enrichment. therefore, for a given type i error probability α, we conclude that there is evidence of enrichment from a to b if p<α, while if p≥α there is not enough evidence of enrichment. as an example, consider the network in fig. suppose that we are interested to test whether there is enrichment from the set a={ } to the set b={,7}. it can be observed that there are arrows going out from a, and of them reach b. the whole network consists of arrows, of which reach b. thus, nab= oa= ib= and iv= the idea behind is that, if the arrows that are going out from a are a random sample from the arrows that are present in the network, then the proportion of arrows reaching b from a should be close to the proportion of arrows reaching b in the whole network, and in the absence of enrichment we should observe on average μ0= edges. in this case, it seems that arrows going out from a tend to reach b more frequently than other arrows do. however, the computation of the p-value leads to p=: the observed nab= does not provide enough evidence to reject the null hypothesis, so that the conclusion of the test is that there is no enrichment from a to b. fig. example: neat in directed networks. left: directed network consisting of nodes connected by arrows. set a contains nodes and and set b nodes and. right: bipartite representation of the same network: it can be observed that n ab= o a= i b= and i v= it follows that μ 0= and p= we can also consider sets b={,7} and c={ }, and test enrichment from b to c. in this case, nbc= arrows out of ob= reach c from b, whereas in the whole network ic= arrows out of dv= reach c. the null expectation is here μ0=; if we fix the type i error probability equal to α= %, the p-value p= leads to the conclusion that there is enrichment from b to c. enrichment test for undirected networks when dealing with undirected networks, the presence of enrichment between a and b is assessed considering the number of edges that connect genes in a to genes in b. we denote this by nab. given the undirected nature of the links in the network, there is no distinction between indegree and outdegree of a node, and it only makes sense to consider the degree of a node, which is the number of vertices that are linked to that node. the null distribution should thus be adapted accordingly. let us define the total degree ds of a set s as the sum of the degrees of nodes that belong to it: then, in the absence of enrichment we can view nab as the number of successes in a random sample of size da, drawn from a population of size dv. the null distribution of nab for undirected networks is thus nab∼hypergeom, where da, db and dv are the total degrees of sets a,b and v. the null hypothesis is then that μab=μ0=dadbdv, the alternative that μab≠μ the p-value is computed using formula. as an example, consider the network in fig. 3a and suppose that we are interested to test the presence of enrichment between the pairs of sets, and. sets a and b are linked by nab= edges, and their degrees are da= and db= while dv= thus, μ0= and pab=. in the same way, it is possible to compute pac= and pbc=. figure 3b shows the relation between the three sets fixing α= %: enrichment is present between the pairs and, but not between sets a and c. fig. example: neat in undirected networks. left: undirected network with nodes. we are interested to infer the relation between sets a, b and c. right: representation of the relations between sets: enrichment is detected between sets a and b and between sets b and c, but not between sets a and c enrichment test for partially directed networks a partially directed network is a network where both directed and undirected edges are present. it is possible to view such a network as a directed network, where every undirected edge connecting two nodes v and w represents in fact a pair of arrows, the former going from v to w and the latter from w to v. if such an adaptation is adopted, model can be applied and partially directed networks can be analysed within neat as directed networks. software neat is implemented in the r package neat, which can be freely downloaded from cran: https://cran.r-project.org/package=neat. the manual and a vignette illustrating the package are also available from the same url. the package allows users to specify the network in different formats, it includes functions to plot and summarize the results of the analysis and is accompanied by a set of data and examples, including the enrichment analysis of the esr gene sets that we discuss in the upcoming section.  performance evaluation we assess the performance of neat by means of simulations. table summarizes some aspects of these simulations, that are the subject of the next two subsections. the r scripts and data files for each simulation can be found at https://github.com/m-signo/neat. we first consider directed networks, and check whether the performance of neat is influenced by the degree distribution of the network, or by the level of overlap between sets of nodes. we then consider undirected networks, and carry out a comparison of neat with the nea test of and with the lp, la, la+s and np tests of. in simulations s and s we compare the performance of neat in two directed networks with different degree distribution. in simulation s we check the performance of the test for different levels of overlap, ranging from to %. in simulations s and s we compare neat to alternative tests in two undirected networks with different degree distribution we compare the performance of the methods under the null hypothesis by checking whether the empirical distribution of p-values in the absence of enrichment is uniform using the kolmogorov-smirnov test, and by computing the following ratios: r1=number of enrichments at1%level ×number of tests whereh0is true and r5=number of enrichments at5%level ×number of tests whereh0is true. the idea behind r and r is that if the null hypothesis h is true, we expect a good test to reject it with a frequency that is close to α. so, the target value for r and r is furthermore, we compare the capacity of different tests to correctly detect enrichments and non-enrichments by computing specificity and sensitivity at α= % level, and the area under the roc curve. the specificity is the proportion of correctly detected non-enrichments, and we expect it to be as close as possible to 1−α. the sensitivity indicates the proportion of correctly detected enrichments, whereas the auc is a measure of the overall capacity of a test to discriminate enrichments and non-enrichments across all values of α. therefore, a test will show a good performance whenever it achieves a specificity close to 1−α, and values of sensitivity and auc as high as possible. simulation with directed networks in simulations s and s we generate two random networks with nodes and with fixed indegree and outdegree distributions using the algorithm implemented by. the indegree and outdegree distributions of nodes are power law with exponent and minimum degree in simulation s and a mixture of two poisson distributions, with parameters λ1= and λ2= and weights q1= % and q2= %, in simulation s we consider sets of nodes whose size ranges between and and we test enrichment from a to b and from b to a for every pair of sets: this means that, in total, we compute 50×49= tests. in the original networks, no preferential attachment between any couple of these sets is present; we generate enrichments by increasing or reducing the number of arrows for pairs of sets. in each case, enrichment is created by adding or removing arrows randomly from one group to the other, in such a way that nab increases or reduces by a proportion uniformly ranging from to %. table performance of neat in simulations s and s2 p ks r 1 r 5 p ks denotes the p-value of the kolmogorov-smirnov test for uniform distribution, auc is an abbreviation for “area under the roc curve”. in both simulations, the distribution of p-values under h is uniform and the specificity is close to the expected % value. sensitivity and auc are higher in simulation s2 in simulation s we check whether the proportion of overlap between sets a and b, that we measure with the jaccard index jab=|a∩b|/|a∪b|, could have an effect on specificity and sensitivity. we consider the same network used in simulation s and we test enrichment between pairs of sets with fixed size |a|=|b|= but with increasing overlap. under h we do not modify the network, whereas under h we introduce enrichments adding arrows going from genes in a to genes in b. for every value of overlap, we consider test. figure shows that the specificity remains constant and close to % for any level of overlap; the sensitivity, on the other hand, is slightly higher when the level of overlap is moderate. fig. specificity and sensitivity in simulation s the plot shows the values of specificity and sensitivity for different levels of overlap. we observe that the specificity of the test does not vary substantially for different levels of overlap, and is always close to % as expected. the sensitivity, instead, slightly reduces as the percentage of overlap increases simulation with undirected networks as alternative methods for network enrichment analysis are available for undirected networks only, we compare neat with them in two simulations where we consider undirected networks with nodes. we generate two random networks with fixed degree distribution, using the algorithm implemented by; the degree distribution follows a power law in simulation s and a mixture of poisson distributions in simulation s with the same parameters used in simulations s and s likewise, we consider sets of nodes, whose sizes vary between and nodes. we test enrichment between every pair of sets a and b, so that the total number of comparisons is here 50×49/2= we introduce enrichments for pairs of sets by adding or removing edges randomly between them, in such a way that nab is increased or reduced by a proportion uniformly ranging from to %. tables and show the results for simulations s and s respectively. as concerns the behaviour under the null hypothesis, the distribution of p-values is uniform in both cases for neat and la, and in one case for la+s and np. nea and lp, instead, do not produce uniform distributions: as it can be observed from fig. the reason is that the distribution is strongly left-skewed for nea, whereas for lp the distribution is right-skewed. in both simulations, most of the methods achieve a specificity close to % as expected; comparison with the other tests shows that the sensitivity and auc of neat are overall good. fig. histogram of p-values in absence of enrichment in simulation s the test of kolmogorov-smirnov indicates that the distribution is uniform for neat, la and np. the distribution of p-values is highly left-skewed for nea, and right-skewed for lp p ks r 1 r 5 % % % % % % % % the best results for each indicator are in bold. p ks denotes the p-value of the kolmogorov-smirnov test for uniform distribution, auc is an abbreviation for “area under the roc curve”. the distribution of p-values under h is evidently not uniform for nea and lp. neat shows the highest values of sensitivity and auc, and its specificity is close to the target value p ks r 1 r 5 % % % the best results for each indicator are in bold. p ks denotes the p-value of the kolmogorov-smirnov test for uniform distribution, auc is an abbreviation for “area under the roc curve”. the distribution of p-values under h can be considered uniform for neat, la and np, and is questionable for la+s. neat shows the highest values of sensitivity and auc, and its specificity is exactly equal to the target value table speed comparison r package neat r package neagui the table compares the time that each method required to compute tests for enrichment in simulations s and s using a processor with ghz cpu frequency. neat turns out to be by far the fastest method network enrichment analysis: an application to yeast the budding yeast saccharomyces cerevisiae is a unicellular eukaryote organism that can be easily grown in laboratory. because of these features, it represents a model organism that has been extensively studied, and it was the first eukaryote whose genome was completely sequenced. since then, a large number of studies has aimed to detect associations between genes. in an attempt to collect these results into a unique source, kim et al. developed yeastnet, an undirected gene network that aims to integrate the results of a large number of high-throughput studies on saccharomyces cerevisiae. in its most recent version, yeastnet comprises edges connecting genes. we use this network of known associations in the following analyses. network enrichment analysis of environmental stress response in yeast after analysing gene expression patterns of yeast saccharomyces cerevisiae in response to different stressful stimuli, gasch et al. inferred the existence of a set of genes that reacted in a similar way to different, hostile environmental changes. this set of genes, called environmental stress response, is believed to constitute a coordinated, initial reaction to the emergence of any hostile condition in the cell. it consists of two subgroups of genes, containing genes that are repressed and induced under stressful conditions, respectively. we take these two gene sets as target sets, and for each of them we test enrichment with the following functional gene sets: gene sets that are part of the go slim biological process ontology and known kegg pathways. at α= % level, neat detects over-enrichment between go slim sets and the set of repressed genes, and between go slim sets and the set of induced genes. furthermore, kegg pathways are found to be over-enriched with the set of repressed esr genes, and with the set of induced genes. gasch et al. reports that genes that are repressed in the esr are involved in growth related processes, various aspects of rna metabolism, nucleotide biosyntesis, secretion, encoding of ribosomal proteins and other metabolic processes. these results are in strong agreement with the list of over-enrichments detected by neat, shown in table as a matter of fact, most of the over-enrichments detected by neat are related to rna transcription, nucleotide secretion and translation of ribosomal proteins, growth-related processes and further metabolic processes. n ab μ 0 log the table lists the go slim bp gene sets and the kegg pathways which the set of repressed esr genes is found to be over-enriched with at % significance level gasch et al. observed that inference for the set of genes that are induced by the esr is more complicated, because most of the genes in this group lack functional annotations. it is worthwhile to observe that neat detects a large number of enriched kegg pathways. this preliminary observation points out a major feature of the environmental stress response: the cell reacts to the emergence of different hostile conditions by activating a number of known cellular pathways that involve energy production, metabolic reactions and molecular transportation. our results for this gene set do not only match the ones of the original study - identifying many processes and pathways that are related to carbohydrate metabolism, fatty acid metabolism, mythocondrial functions and cellular redox reactions, protein folding and degradation and cellular protection during stressful conditions - but they also unveil further enrichments that involve molecular transportation and amino-acid metabolism. n ab μ 0 log the table lists the go slim bp gene sets which the set of induced esr genes is found to be over-enriched with at % significance level n ab μ 0 log the table lists the kegg pathways which the set of induced esr genes is found to be over-enriched with at % significance level tables and compare the p-values obtained with neat with those obtained with la+s, which, according to the conclusions of and to our own simulations, can be considered as the main competitor of neat. the tables show a large overlap between the over-enrichments detected by the two methods at a % significance level: the two methods jointly detect over-enrichments for the set of repressed esr genes, and for the set of induced esr genes. there is only a small number of discrepancies between the two methods and these are mostly borderline cases. in particular, la+s detects over-enrichments that are not detected by neat, whereas neat detects over-enrichments that are not detected by la+s. as concerns computing time, neat computed the required task in s, whereas the same computation with la+s required s. in summary, the two methods lead to very similar conclusions, but neat is considerably more efficient. μ 0 the table reports the gene sets that are found to be over-enriched by at least one of the two methods. μ denotes the expected value of n ab in the absence of enrichment. the last two columns report log 10 p-values for the proposed neat and the la+s test of, respectively μ 0 the table reports the gene sets that are found to be over-enriched by at least one of the two methods. μ denotes the expected value of n ab in the absence of enrichment. the last two columns report log 10 p-values for the proposed neat and the la+s test of, respectively μ 0 the table reports the gene sets that are found to be over-enriched by at least one of the two methods. μ denotes the expected value of n ab in absence of enrichment. the last two columns report log 10 p-values for the proposed neat and the la+s test of, respectively network enrichment analysis of go slim sets: overlap does not imply enrichment gene ontologies consist of a large number of gene sets, which are involved in different cellular functions or biological processes, or that are active in a specific component of the cell. these sets of genes are typically employed to enrich sets of differentially expressed genes that have been experimentally detected. however, network enrichment analysis is a more general instrument, which allows to assess the relation between pairs of gene sets in a network. one might wonder, for instance, whether gene sets within an ontology tend to be strongly related to each other, or whether there is a strong separation between them. we consider gene sets in the go slim biological process ontology for saccharomyces cerevisiae. as a result of the hierarchical structure of gene ontologies, gene sets are nested within another group. we exclude these sets from the analysis: the remaining gene sets do not have hierarchical relations with each other, and pairs of these sets display overall a low overlap, which is null in most cases. if overlapping of sets was taken by itself as evidence of a relation between two gene sets, one would therefore conclude that most of these gene sets are unrelated. if, however, we do not limit our attention to the overlap between pairs of sets, but consider also known associations between genes in the two sets as represented in yeastnet, we obtain a different conclusion. we have used neat to test whether there is enrichment between each pair of sets. in a random network where no relations between the sets are present, we would expect to detect enrichments out of tests for α= %; instead, we detect enrichments, times more than expected. out of these, are under-enrichments, and are over-enrichments. an under-enrichment, here, indicates that two go slim sets are poorly connected to each other: the high number of under-enrichments, therefore, might be not particularly surprising or interesting, as we do expect that unrelated gene sets within the ontology are poorly connected. the high number of over-enrichments, on the other hand, is striking: this indicates that many groups within the ontology are highly connected to each other - something that would occur rather rarely, if there was no relation between the sets. this result points out a major difference between gene enrichment analysis and network enrichment analysis: whereas in the first case the extent of overlapping between two gene sets is taken by itself as evidence of enrichment, network enrichment analysis bases the evaluation of enrichment on the level of connectivity that exists between the two sets in a network. of course, the two facts are not completely unrelated. figure shows that there is a certain correlation between overlap of gene sets and network enrichment, so that we tend to find network enrichment in the presence of higher levels of overlap. this correlation is, however, low, pointing out that there does not necessarily have to be enrichment for highly overlapping gene sets, and vice versa. as an example, the go slim sets “cytokinesis” and “nuclear organization” do not share genes, but are detected as enriched in yeastnet. this result can be explained by the fact that “nuclear organization” includes genes involved in the assembly and disassembly of the nucleus, which is a preliminary step in cell cytokinesis. fig. relation between overlap and p-values. note that p-values are represented on a negative log-scale to enhance readability  network enrichment analysis is a powerful extension of traditional methods of gene enrichment analysis, that allows to integrate them with the information on connectivity between genes provided by genetic networks. whereas gene enrichment analysis bases the test for enrichment solely on the overlap between two gene sets and ignores the relationships between individual genes, network enrichment analysis exploits a larger amount of information by making use of gene networks, and it is thus capable to detect enrichment even between two gene sets that do not share genes. in this paper, we have presented a network enrichment analysis test that aims to overcome some limitations which affect the network enrichment tests of. first of all, we believe that a normal approximation does not make justice to the discrete nature of nab. we have shown that this approximation can be avoided if one models nab directly, using a hypergeometric distribution with suitably specified parameters. in addition, the normal approximation employed by requires the computation of a large number of network permutations to obtain the mean and variance under h0: this operation can be very time consuming for big networks and it makes the computation of the test rather slow. the use of the hypergeometric distribution, instead, allows to specify the null distribution of nab without resorting to permutations, thus speeding up computations considerably. a further drawback of existing methods for network enrichment analysis is that they have been implemented only for undirected networks. we address this problem by considering different types of networks and by proposing two different parametrizations, which take into account the different nature of directed and undirected links. we believe that neat could constitute a flexible and computationally efficient test for network enrichment analysis. our simulations show that neat has a good capacity to correctly classify enrichments and non-enrichments. comparison of neat with other methods points out an overall good performance in terms of sensitivity and of specificity, as well as the computational efficiency of the proposed method. the examples illustrated in the previous section show that neat can retrieve enrichments that were detected with gene enrichment analysis, but it can also unveil further enrichments that would be overlooked, if known associations between genes were ignored. even though the focus of this paper is on gene regulatory networks, neat is a rather general test: it can be applied to networks that arise in different contexts and disciplines, whenever the interest is to infer the relationship between groups of vertices. this can include, for example, other types of biological networks, as well as social, economic or technological networks. abbreviations aucarea under the roc curve crancomprehensive r archive network esrenvironmental stress response gogene ontology keggkyoto encyclopedia of genes and genomes neatnetwork enrichment analysis test 
network enrichment analysis is a powerful method, which allows to integrate gene enrichment analysis with the information on relationships between genes that is provided by gene networks. our simulations indicate that neat is considerably faster than alternative resampling-based methods, and that its capacity to detect enrichments is at least as good as the one of alternative tests. existing tests for network enrichment analysis deal only with undirected networks, they can be computationally slow and are based on normality assumptions. we propose neat, a test for network enrichment analysis. neat is a flexible and efficient test for network enrichment analysis that aims to overcome some limitations of existing resampling-based tests. we discuss applications of neat to network analyses in yeast by testing for enrichment of the environmental stress response target gene set with go slim and kegg functional gene sets, and also by inspecting associations between functional sets themselves. the test is based on the hypergeometric distribution, which naturally arises as the null distribution in this context.
 network enrichment analysis is a powerful method, which allows to integrate gene enrichment analysis with the information on relationships between genes that is provided by gene networks. existing tests for network enrichment analysis deal only with undirected networks, they can be computationally slow and are based on normality assumptions.  we propose neat, a test for network enrichment analysis. the test is based on the hypergeometric distribution, which naturally arises as the null distribution in this context. neat can be applied not only to undirected, but to directed and partially directed networks as well. our simulations indicate that neat is considerably faster than alternative resampling-based methods, and that its capacity to detect enrichments is at least as good as the one of alternative tests. we discuss applications of neat to network analyses in yeast by testing for enrichment of the environmental stress response target gene set with go slim and kegg functional gene sets, and also by inspecting associations between functional sets themselves.  neat is a flexible and efficient test for network enrichment analysis that aims to overcome some limitations of existing resampling-based tests. the method is implemented in the r package neat, which can be freely downloaded from cran. keywords networkenrichment analysisgene expressionhypergeometriceuropean cooperation in science and technologyca15109wit ernst c. issue-copyright-statement© the author 2016 