BACKGROUND
the skeleton of complex systems can be represented as a network where vertices represent entities and edges the relations between these entities.
often it is impossible, or expensive, to determine the network structure by experimental validation of all the interactions between all the vertices.
it is usually more practical to infer the network from surrogate observations.
uncovering the relations between entities from indirect evidence is known as the problem of network inference or reverse engineering of networks from data.
while many algorithms have been developed to infer networks from quantitative data of systems’ entities states, less attention has been placed on methods to infer networks from repeated observations of related sets.
there are many cases in which groups or clusters of interrelated entities are known or can be observed experimentally.
typically such information is much more readily accessible than direct evidence of pair-wise interactions or even quantitative information about the entities under different conditions or time points.
each of these sets of related entities provides some information about the connectivity of the underlying network, and it would be of value to be able to utilize this information to resolve the connectivity of the underlying network connecting these entities.
this inference process applies to a general class of inference problem of broad applicability; however, our motivation comes from problems in systems biology and systems pharmacology.
the tide of high-throughput biological data makes the inference of biological networks both more necessary and possible.
there have been a number of success stories in the application of these methods to understand real biological phenomena.
however, the multitude of components in biological molecular intracellular systems and their combinatorial interactions means that the possible networks that are consistent with observed data are astronomically large.
since we cannot directly observe many components of this system at once, and methods to profile binary interactions are expensive and laborious, the network remains under-determined; there are many networks which can equally well explain the observed data.
however, in recent years the ability to sequence dna, rna and protein, together with the accumulation of prior knowledge about functional and physical relationships between genes and proteins, lends itself to a better ability to infer the underlying networks that govern the phenotype of mammalian cells.
at the same time, a new field is emerging called systems pharmacology.
systems pharmacology aims to integrate knowledge about drugs, drug-drug interactions, drug interactions with cells and organs, and drug relations to adverse events and desired effects in individual patients  <cit> .
however, mining such data from various sources is challenging.
current network inference methods employ a number of different strategies to reduce the search space of network structure solutions.
naturally, each strategy makes certain compromises and assumptions and has particular advantages and limitations  <cit> .
while methods to infer networks from quantitative biological data have been popular, in particular methods such as bayesian networks inference  <cit>  and network inference based on mutual information  <cit> , there has been less focus in systems biology on inferring co-occurence networks from sets of related entities and the applications thereof, while such an approach has been successfully applied more in other fields  <cit> .
in most high-throughput  methods that collect molecular biological data from cells, the underlying network is not known.
typically subsets of related molecular components are observed.
for example, groups of co-expressed genes across different samples and contexts may be identified from transcriptomics data.
another example is groups of proteins which are listed in pull-down proteomics experiments that use immunoprecipitation followed by mass spectrometry  for protein complex identification.
the identified genes or proteins may be regarded as the vertices of the underlying gene regulatory, cell-signaling or protein-protein interaction  networks.
extraction of the underlying network from such data can be achieved in many ways.
in addition, the popular method of gene set enrichment analysis   <cit>  uses libraries of related gene sets stored in the gene matrix transposed  format.
in principle, and in most cases, within gene set libraries, each subset of related genes can provide some coarse local information about the connectivity of an underlying molecular network.
as these gene sets accumulate, the underlying molecular networks that regulate mammalian cells may be resolved based on co-occurrence of genes within sets.
we aim to employ the accumulation of course local information, from high-throughput experiments, to infer fine details of the global network.
here we give this idea a firm foundation and show that given accumulating subsets of related entities, the underlying network can be inferred with high fidelity, and if enough data is available, the network can be inferred completely.
when the subsets of related entities do not provide enough information to infer the network with full confidence, we can extract all the possible information about the connectivity of the underlying network from the related set data to arrive at a best guess which can provide insights into the structure within the data.
the method we present here makes no a priori assumptions about the structure of the network or the nature of the edges.
we begin our approach by grounding the solution in the fundamental principles of statistical mechanics.
we numerically execute the solution on synthetic random networks to demonstrate its power.
we then proceed to apply the method to real-world biological, clinical and social datasets in order to predict direct human protein-protein  interactions inferred from a recent ht-ip/ms dataset  <cit> ; infer a network that connects mouse embryonic stem cell regulators based on data from chip-seq and loss-of-function/gain-of-function followed by expression data; learn a network that connects  <dig> cancer drugs and  <dig> common and severe side-effects extracted from thousands of patient records reported in the aers database; and discover a network that connects authors based on co-authorship of publications listed on pubmed.
methods
exponential random graphs
exponential random graphs models  are a means of generating an ensemble of networks with prescribed statistical properties with the aim of modeling real-world networks.
ergms were introduced by holland and leinhardt  <cit>  and have a long history in complex systems research and are commonly applied in statistics and social science.
ergms have been used for modeling complex brain networks  <cit>  but their use in computational systems biology is scant.
park and newman  <cit>  showed that ergms are the natural extension of the fundamentals of statistical mechanics to network modeling.
here we adopt this formalism.
the set of graphs g represents the sample space of graphs in the model, and, {xi}, i =  <dig> … r, represent a set of r empirical observations.
then a probability distribution p, can be defined over the elements g in g, such that the expectation value of xi takes the empirical values.
the best choice of probability distribution is the one which satisfies the empirical constraints,
∑gpgxig=<xi>,
while admitting no further information about the model graphs, which is achieved by maximizing the gibbs entropy,
s=−∑g∈gpglnpg.
this leads to a probability distribution which is the network equivalent of the boltzman distribution,
pg=e−hgz
where h is the graph hamiltonian function with lagrange multipliers θi,
hg=∑iθixig
and z is the partition function over the set of graphs g,
z=∑ge−hg
this probability distribution defines the exponential random graph model networks which obey the mean constrains of equation  <dig>  but which are otherwise maximally disordered.
dependence graphs
pattison and wasserman  <cit>  showed that ergms can be generated in terms of dependence graphs.
we shall briefly review these graphs here in the context of simply connected undirected networks, as they are relevant to the inference problem we address.
the graphs which represent undirected simply connected networks can be represented by an adjacency matrix gij, which is symmetric and has elements,
gij={1ifviandvjareconnectedbyavertexing0otherwise
the ergms define a probability distribution over g, and a model network, gij may be regarded as a realization of a random variable which is defined as a random selection from g over the probability distribution p. the dependence graph, d, has vertices which correspond to the edges in gij.
the edges of d connect vertices which are not conditionally independent.
so the dependence graph identifies pairs of edges whose presence in the model network depends on each other.
the hammersley-clifford theorem  <cit>  then states that the model probability distribution, p, only depends on the complete subgraphs of the dependence graph.
inference approach
the inference problem addressed here is now phrased in terms of ergms.
given an unknown underlying network, gu, with vertices, v, we consider a set, c, composed of many subsets of the network’s vertices, c=ci,ci⊂v,i= <dig> …,nc, such that c is a field over the set of vertices.
the sets ci consist of vertices which are empirically observed to be related in the network, this could be for example, proteins identified in a mass-spectrometry proteomics pull-down, members of a cell signaling pathway, or co-authors of a publication.
the central assumption is that each of the sets ci identifies a locally connected subgraph of the underlying network.
in these terms, the network inference problem we pose is thus: given the set of nc subsets, c, and no other information, to what extent can we infer the underlying network gu?
to give a specific example, we may consider the results from ht-ip/ms, after appropriate filtering, as identifying a locally connected region of the underlying human protein-protein interactome network  <cit> .
we hypothesize that we can resolve the underlying ppi network given enough observations of sets of proteins identified in different pull-downs.
in these terms, the proteins would be represented by the vertices vi, and the list of proteins identified in each pull-down experiment would correspond to one element of c, while the underlying ppi network would be represented by gu.
we are aware that we are searching for a static configuration of the network, whereas the underlying connectivity in complex systems, including ppis and gene-regulatory networks, is dynamic as it may change over time and under different conditions.
we define our observable graph functions, xi in the following way,
xig={1iftheelementsofciformaconnectedsubgraphofg0otherwise
if we interpret each set as providing course local information on the connectivity of the underlying gu, such that we have a confidence, α, that the elements in each line are locally connected, then the constraints on the ensemble are the following,
∑gpgxig=α
in which case the maximum entropy probability distribution function p identifies an ensemble of networks which have a connectivity consistent with the known input set c but which are otherwise maximally disordered, we shall refer to this as gens.
in our studies of the properties of our inference approach on synthetic networks we shall generate data which identifies locally connected regions of the underlying network and so we shall take the value of α =  <dig>  when we apply our inference approach to data from systems biology the value of α will typically be less than unity as there will generally be only a finite degree of confidence in the connectivity of each local region identified in the data.
the above constraints leading to the probability distribution p can also be seen in terms of a dependence graph, d, for the corresponding ergm.
each set ci contains vertices between which a set of edges are assumed to exist in the underlying network in order to form a locally connected subgraph.
over the ergm ensemble, the presence of each of these edges is conditionally dependent upon the others.
these edges form a complete subgraph of d, and therefore, according to the hammersley-clifford theorem, define the probability distribution p.
in the approach presented here we make no attempt to infer directionality, hence, we take the sample set, g, to consist of simple undirected graphs.
the data contained in, c, constitutes an accumulation of course local information on the connectivity of the underlying network.
even with large amounts of this class of data the network often remains underdetermined, hence there exists a whole ensemble of networks which are consistent with the data.
in order to infer finer details of the underlying network we adopt some of the philosophy of network modeling to take a sample of this ensemble, and then use the properties of this ensemble for inference.
here we take the sample numerically by using an algorithm which generates a random sample of the ensemble.
the algorithm ensures that the sampled network has the local connectivity consistent with the data while minimizing the number of edges.
the edge minimization ensures the strongest signal from the data in the sense that edges only appear in the ensemble as required by the data.
the algorithm works by generating a random sample, of size ng, of the ensemble of networks gens consistent with the data.
according to the assumptions of the inference, the gmt file contains a number nc of lines, ci, each of which consists of vertices which are locally connected in the underlying network.
the algorithm first randomly permutes the order of the lines in the gmt file, then, starting with the empty graph which consists of the set of nodes  and the empty set of edges ei = {}, it builds a network by taking each line and introducing a minimal number of random links that connect the vertices in that line.
the pseudo-code for the algorithm is then:
for i =  <dig> to ng
randomly permute the order of the lines in the gmt file
ei = {}
for j =  <dig> to nc
randomly introduce a minimal number of edges between the vertices ci such that they are connected, and continually append to the set ei
end for i
end for j
calculate the mean adjacency matrix of the ensemble gens
a sample of random networks generated in this fashion constitutes a random sample of gens.
the properties of this ensemble are then used to infer the underlying network gu.
specifically, we calculate the mean adjacency matrix over this ensemble, each element of which corresponds to the probability of the edge being present in a uniformly random draw from the ensemble; this is interpreted as being indicative of the accumulation of information on the presence of the edge in the underlying network.
analytical approximation
the algorithmic sampling of the ensemble gens becomes computationally demanding when inferring networks with many vertices, and large amounts of data.
when applying the approach to infer biological networks from large high-throughput datasets which although sparse, can have thousands of vertices, we look for an efficient analytical approximation to the algorithmic solution.
the approach we take is to analytically mimic the function of the fully executed algorithm that generates the networks, which are samples of gens.
the first order approximation is to treat each ci as generating an independent minimally connected bernoulli random graph, in which each edge has an independent and equal probability of appearing.
then the superposition of all the ci may be regarded as a bernoulli process in which each edge undergoes a series of bernoulli trials with probabilities corresponding to the random graphs generated by each of the elements of c. in this approximation the probability that a given edge is present in gu is given by,
pij=1−Πk1−2αnij,k
where nij,k is the size of the kth elements of c to which both vertices vi and vj belong.
alternative co-occurrence scoring methods
to compare the above methods to other approaches that can be used to construct networks from repeated observations of co-occurence of entities in related sets we compare our approach to two alternatives.
a simple difference of proportions test to measure co-occurrence strength is applied as follows: for two given vertices, a and b, a contingency table can be constructed with f, f, f, and f where f indicates the frequency of lines ci in c where x is true.
we then use the chi-squared test of difference of proportions to test the significance of the co-occurrence.
then the probability of interaction between a and b is calculated as one minus the p-value.
in addition, the simplest possible form of inference from co-occurrence whereby the probability of an edge between a and b is given by the ratio of the number of ci in the gmt file in which both a and b occur to the total number of lines, nc, is also used as a comparison.
bias adjustment
while artificial random networks can be evenly and randomly sampled, real world datasets contain sampling biases where some vertices are measured more often.
for example, well-studied genes/proteins appear in more publications and thus commonly have more reported interactions with other genes/proteins.
this inhomogeneity of information throughout the network means that the inferred interactions are as sensitive to the frequency with which particular vertices are observed as to the strength and specificity of the edges between the vertices.
in order to correct for this and calculate probabilities which are only sensitive to the strength of the interactions, we generate a null distribution for each edge probabilities under the hypothesis of no specific interaction.
this is achieved by calculating the distribution of each edge-probability pij in the network after any information on the network connectivity has been destroyed: the gmt file data is randomly permuted, while preserving its structure by conserving the lengths of each set and the frequency of each element throughout the data, and allowing only one of each type in any given set/line, then all the edge weights are calculated.
this process is repeated to generate the null distribution for each edge weight.
by comparing the actual edge weight to this null distribution, under the hypothesis of no interaction, we obtain a p-value which quantifies the edge-probabilities after correction for the sampling bias.
this p-value is then used as a measure of the strength of the interaction.
combining evidence from multiple gmt files to build a consensus network
we can combine several types of datasets stored in different gmt files to form a consensus network.
by combining two or more different inferred network perspectives we may gain additional insight into the functional associations between related vertices.
when combining data from several sources we rewrite equation  <dig> for the edge probabilities as:
pi,j=1−Πk1−2αni,j,kΠk′1−2α′ni,j,k′…,
where the terms in each square bracket come from each distinct data source and the greek letters are the corresponding confidence parameters.
to compute scores that consider the bias adjustment, the distribution of edge weights from randomly permuted gmt files are generated using the same equation and the same steps described above for inferring probabilities for edges for individual networks.
matthews correlation coefficient to evaluate inferred networks
to evaluate the quality of the predicted edges we use the matthew's correlation coefficient .
mcc is a balanced measure of the quality of binary classifications, and it is equal to unity when the classification is perfect; it is computed by the following equation:
mcc=tp×tn−fp×fntp+fptp+fntn+fptn+fn
where fp and fn are the false positives and negatives respectively, and tp and tn are the true positives and true negatives respectively.
RESULTS
inference of synthetic networks
first we investigate the quality of inference using our approach by applying it to synthetic test networks.
we begin with a randomly generated connected graph serving as the underlying network gu that we wish to infer , which is also represented by its adjacency matrix .
the set c used to generate a gmt file is created by performing short random walks starting on random vertices.
the idea is to infer gu only using the information from c. the ensemble, gens, is generated algorithmically by randomly introducing a minimum number of links in order to connect successive sets of vertices ci.
a small selection of the calculated elements of gens is shown in figure 1c.
the mean adjacency matrix of this ensemble is then calculated .
the elements of the mean adjacency matrix are interpreted as probabilities that a given link is present in gu.
due to the binary nature of the edges, a comparison can be made between the underlying network gu and the mean adjacency matrix, after the application of a threshold value of pt.
a histogram of edge probabilities, pij, shown in figure  <dig>  has a bimodal form which appears to distinguish between edges present in the underlying network  and edges not present in the underlying network .
in addition, on the x-axis we plot the mcc as a function of the threshold pt.
in other words, we plot the mcc where we cut the inferred adjacency matrix to decide which scores will constitute an edge.
if we set a large threshold value there will be only few edges remaining in the network and thus many false negatives and lower mcc.
conversely, as the threshold is reduced to zero the network will tend to completeness and thus will include many false positives.
there is a region of pt where the similarity between the inferred network and the underlying network is greatest.
this region corresponds to the peak of the mcc curve .
the aim of applying the inference approach to such synthetic networks is to investigate the quality of the inference in a case where the underlying network is known.
this investigation requires several steps.
first, because the approach requires a random sample  we must investigate the convergence of the statistics deriving from this sample.
once the rate of convergence is known the required sample size ng for a given degree of convergence is obtained and the method may be reliably applied.
the next step is to examine the quality of inference and its dependence on the properties of the available data.
finally, with a view to the application of our method to problems in systems biology we examine the computational complexity and running time of our approach.
convergence of inferred networks
our inference approach is based on the mean of a random sample of networks which are consistent with our data.
the rate of convergence of this statistic depends on the properties of the data upon which the ensemble is based and so a general convergence rate does not exist.
we can however derive an upper limit to the rate of convergence by considering the convergence in the worst-case-scenario.
in this case there is no information on the connectivity of the underlying network, and therefore the largest possible ensemble of consistent networks and so the slowest rate of convergence.
here we derive the rate of convergence of the mean in this case as the upper limit for the rate of convergence.
in this worst-case every connected network with n edges is a consistent network.
in a random sample of these networks a given edge has a probability 2n of being present in any given network.
effectively, for a given edge, each sampled network constitutes a bernoulli trial, and therefore in a random sample of ne consistent networks, the total number of times any given edge is present, x, follows a binomial distribution with ne trials at a probability of success of p=2n.
if we use our sample to estimate this probability, pest=xne, then the resulting estimate will be distributed by a  binomial distribution with mean, p, and variance given by varxne <dig>  which can be written as, p1−pne.
the signal-to-noise ratio is sometimes written as the ratio of the mean to the variance, so in this case it is given by, snr=pne1−p which we can use to gauge the convergence by requiring that ne is large enough to achieve a certain signal-to-noise ratio.
given that p=2n, it means that the ensemble size must increase in proportion to the number of nodes n, in order to preserve a constant signal-to-noise ratio.
the ensemble size required to achieve a given signal-to-noise ratio in this case can be written as,
ne=n2−1snr <dig>
and this is the formula used to determine the sample size throughout all applications of the algorithm presented here.
the above estimate can be used as an upper limit to the ne required for the mean to converge to a given signal-to-noise ratio in the case of general gmt file data; this is because such gmt data file is more informative, hence the size of the ensemble of consistent networks is smaller, and a smaller sample is required for inferring the underlying network.
we demonstrate this in a plot of the signal-to-noise ratio against the size of the ensemble for inference of a  <dig> node network .
accuracy of inference
having quantified the convergence of the inferred network with the sample size nc,, the next consideration is how similar the inferred network is to the underlying network from which the data derives.
the quality of the inference depends on the data contained in the gmt file.
as the number of lines in the gmt file, nc, increases, the information on the presence of edges accumulates and the inferred network becomes more similar to the underlying network.
the length of the lines in the gmt file also influences the quality of the inference; larger lines provide coarser information on the connectivity of the network and thus are less informative.
finally, the more nodes are in an underlying network the greater the amount data required to infer its structure.
here, for a given number of n odes, n, in a minimally connected network we examine the quality of inference and how it depends on nc, and the length of the lines in the gmt file.
we begin by examining the dependence on the number of lines in the gmt file.
we infer the structure of a minimally connected network with n =  <dig>  from gmt files with a range of  <dig> to  <dig> lines.
to quantify the quality of the inference we use the maximum value of the mcc.
in figure  <dig> we plot the maximum mcc against the number of lines in the gmt file, nc,, using four different methods of inference: 1) the full-algorithm 2) the analytic approximation 3) chi-squared difference of proportions 4) simple co-occurrence.
in each case we see that as nc increases, i.e.
with more data, the accuracy of the inference increases and tends towards ideal inference.
this is when the inferred network is exactly the same as the underlying network.
we also observe that the full algorithm described above is more accurate than the other methods, but the analytic approximation is also more accurate than more basic co-occurrence approaches .
finally we examine the dependence of the accuracy of inference upon the size of the sets  in the gmt file.
in figure  <dig> we plot the mean quality of inference as measured by the maximum mcc.
the four curves correspond to inference from synthetic gmt files with random walks of lengths of   <dig>    <dig>    <dig>   and  <dig>  longer random walks result in gmt files with longer lines, and therefore coarser information on the connectivity of the underlying network.
we see that each curve has the same tendency to increase the quality of inference with increased nc, however, the rate reduces with increasing size of set in gmt file, shorter lines.
in this way we show that for coarser information  more data is required to infer the network.
running time and computational complexity
while the fully executed algorithm is potentially useful, in practice it is not practical due to its computational complexity.
the operations to execute the fully enumerating algorithm depend on ne, nc, and the length of the elements in each ci, which are inherently random so we shall refer to the mean length cavg.
from the structure of the pseudo-code we expect that the number of operations should increase in proportion to each of these three quantities, as well as the number of vertices n, i.e., o. in the case of real data, nc can be of the order of typically  <dig> or  <dig>  and there can be typically thousands of vertices, so the number of operations for this method of inference can be prohibitively large.
for the analytical approximation with equation  <dig>  described under analytical approximation above, the number of operations required for the computation depends on the details of the data as this determines the number of operations.
the number of evaluations increases as o. however, the number of operations required for each evaluation depends on the structure of the data within the gmt file.
comparison of running times between the fully executed algorithm and the approximation is shown in figure 7figure 7; this shows that the analytical approximation is two orders of magnitude faster than algorithmic sampling and therefore more practical for generating networks from real datasets stored as gmt files.
in the next sections we employ the approximation for the inference of ppis from ht-ip/ms data, construct a network of stem cell regulators from chip-seq and loss-of-function/gain-of-function followed by expression data, construct a network between cancer drugs and severe side effects from patient records, as well as construct a co-authorship network connecting researchers from mount sinai school of medicine in new york.
application to ppi prediction from ht-ip/ms data
the identification of binary interactions between proteins is an important task in systems biology.
initially, information on ppi networks in mammalian cells came from targeted experiments involving a small number of proteins.
however, experimental techniques can now explore ppis in human and mouse cells at large-scale.
in addition, large numbers of ppis from small-scale experimental studies are continually aggregated in publicly available databases.
in a recent study, malovannaya et al.
<cit>  reported the results from over  <dig> ht-ip/ms experiments applied to nuclear co-regulators and members of their complexes in human cells.
with this experimental technique, antibodies are used to pull-down a bundle of proteins that can be identified with mass-spectrometry.
a total of  <dig> antibodies were used in  <dig> immuno-precipitation experiments of nuclear extracts from human cell-lines, in the course of which  <dig>  individual protein detections were made.
non-specific binding events significantly contribute to the protein detection data and it is necessary to filter these out; we used the same filter used by the authors of the study  <cit>  which reduced the number of individual protein detections to  <dig> .
because the proteins are bound together in each pull-down, each of the  <dig> experiments may be regarded as identifying a locally connected subgraph of the underlying binary ppi network.
this type of information on the underlying network is equivalent to the class of data discussed above.
the list of proteins identified in each experiment may be identified with the field c, and a mean adjacency matrix may be calculated from equation  <dig>  then finally the sampling bias correction can be made to derive a predicted weighted adjacency matrix.
this matrix quantifies the confidence of each binary direct physical ppi given solely the information on the connectivity of the underlying network derived from the collection of pull-down experiments.
this approach is similar to our recently proposed reanalysis of this dataset since it does not consider the baits used in each experiment to determine direct protein interactions  <cit> .
a large value of pi,j may indicate that there is potentially sufficient information to suggest that protein vi and vj directly physically bind to each other.
however, although large, the amount of data in this ht-ip/ms dataset is not large enough to fully resolve the underlying network of ppis, so a small value of pi,j does not necessarily indicate that the pair of proteins do not directly bind, only that there is not enough information in the dataset to suggest that they do.
as the network is not fully resolved, the results of this inferential process could be used to rank the binary interactions to suggest likelihood of interactions for more targeted validation.
alternatively, the mean adjacency matrix could be used to gain a course grained global view of the human nuclear co-regulation complexome.
to evaluate the reliability of predicted interactions we used benchmarking to compare predicted interactions to known interactions.
benchmarking is important for determining the quality and reliability of network inference approaches, and we attempt here to evaluate our inference approach applied to this data.
the typical approach is to take the union of many current curated ppi databases and treat the interactions therein as true positives.
this is imperfect because these databases contain significant numbers of false positives and false negatives, penalizing inferences that may be discovering correctly unknown interactions.
with these concerns in mind, we followed this procedure to evaluate our inference method.
first we used the list of proteins identified in each pull-down to define the sets of proteins forming a connected subgraph of the underlying ppi network; this defines the subsets ci composing the field c. we then used the approximation shown in equation  <dig> to estimate the mean adjacency matrix.
we then collected ppi data from the following databases: biogrid  <cit> , hprd  <cit> , innatedb  <cit> , intact  <cit> , kegg  <cit> , kea  <cit> , mint  <cit> , mips  <cit> , dip  <cit> , bind  <cit> , biocarta, pdzbase  <cit> , ppid, yu et al.
<cit> , stelzl et al.
<cit> , ewing et al.
<cit> , rual et al.
<cit>  and ma’ayan et al.
<cit> .
we treated this data as the set of true positives and compared our mean adjacency matrix to it.
to evaluate our ability to predict interactions we plotted the receiver operator characteristic curve  and the mcc as a function of the threshold value of pt .
in addition, we observe that prior to the sampling-bias-correction, the distribution of edge weights decays monotonically, whereas after, there is a bimodal distribution  which is reminiscent of the observed histogram shown in figure  <dig> for the random network inference score distribution.
the inhomogeneous distribution of protein frequencies throughout the experimental data suggests a sampling bias.
however, the change in distribution of edge weights from unimodal to bimodal suggests that the bias has been removed to some extent.
this is confirmed by the roc and mcc curves that show that the bias adjustment results in improved accuracy above the uncorrected inference or co-occurrence computed using enrichment analysis with a chi-squared test.
altogether, the predicted network of protein-protein interactions can suggest novel binary physical protein-protein interactions amenable for functional experimental validation.
the top predicted interactions are provided in additional file 1: table s <dig> and on the web at http://www.maayanlab.net/s2n/ppi.html.
to further validate the inferred ppi network, we compared the ability of the predicted interactions to recover known protein complexes listed in the corum database  <cit> .
we filtered the corum database, retaining only those complexes for which at least 80 % of the subunits are detected in the ip/ms data upon which we based our inference.
in addition we retained only those corum complexes which had at least four proteins.
the result was fifty corum protein complexes which could be potentially inferred from the ip/ms data.
for each of these protein complexes, we generated three lists: 1) the known corum complex members; 2) proteins which are inferred to have significant interactions with the complex members either by having interaction-strength above the threshold resulting in maximum mcc with any individual member, or mean interaction strength across all complex member in the 95th percentile; 3) a list of random proteins to provide a scale for the background.
we then performed hierarchical clustering on the complex members and a clustering based on clique membership on the additional proteins that strongly interact with the complex members.
such interactions are visualized in adjacency matrices heatmaps that show that our method recovered many known complexes and is capable of predicting additional members of known complexes .
adjacent to each heatmap of predicted interactions for each complex are connectivity maps in the same order where elements indicate membership in at least one of the ppi databases listed above.
a comparison of these two adjacency matrices shows that the corum complexes are clearly well inferred with our method, and also that we can observe interactions with potential proteins and protein complexes which are currently undiscovered experimentally.
focusing on two such complexes, figure  <dig> shows identified relationship between the mini chromosome maintenance  complex and the proteasome, whereas in figure  <dig> additional components are suggested for the tfiih transcription factor complex.
the relationship between the mcm complex and the proteasome appears to be divided into two mutually exclusive sets of proteasome related components that do not interact with each other.
revealing associations between stem cell regulators
in the past few years a tremendous number of high-content experiments have profiled different aspects of mouse embryonic stem cells.
such experiments include gene-expression microarrays at different conditions, genome-wide histone modification and transcription factor binding to dna using chip-seq, rnai screens for identifying pluripotency regulators, proteomics, phosphoproteomics and microrna profiling.
while these experiments have the potential to fully uncover the regulatory networks governing stem-cell maintenance and differentiation into specific lineages, data integration across regulatory layers to extract new knowledge from such data is challenging  <cit> .
the network inference method we employ here can be utilized for data integration by building networks from various sources of data.
using equation  <dig> we can construct networks that combine information from multiple types of gmt files.
from the stem cell literature we collected publications that reported: a) transcription factor, and other transcriptional regulators, binding to the promoters of target genes as determined by chip-seq or chip-chip experiments; and b) gene expression changes after the knockdown  or over-expression  of these factors and regulators as determined by gene expression arrays.
we then converted such data into two gmt files: the first with each row having a set of transcription factor target genes from each chip-seq or chip-chip experiment, and the second having in each row a set of differentially expressed genes for each factor or regulator from each gene expression loss-of-function  or gain-of-function  experiment.
we then transposed these two files were the target genes are the row labels and the factors and regulators are listed in each row.
finally, we generated three networks: 1) based on the chip data alone ; 2) based on the gene-expression after knockdown or over-expression data ; and 3) based on combined data using equation  <dig> .
the chip network contains four clusters, the first of which includes the known pluripotency maintenance regulators: nanog, oct <dig> and sox2; the second cluster corresponds to the polycomb repressive complex ; the third cluster includes early differentiation regulators including myc and mycn; the remaining cluster is made of klf <dig>  klf <dig> and klf <dig> which likely have overlapping unique set of target genes .
the lof/gof followed by expression network is more difficult to explain.
nanog, oct <dig> and sox <dig> still appear together and are directly connected.
however, the other components appear in other clusters that are more difficult to define based on what is known .
finally, the combined network shows an interesting pattern: the triad, nanog, oct <dig> and sox <dig> appears in the center of two highly connected clusters, one containing other known pluripotency regulators including tbx <dig>  esrrb, klf <dig>  sall <dig> and tcf <dig> whereas the other cluster contains more differentiation components.
it is plausible that the triad of nanog, oct <dig> and sox <dig> is regulating both highly dense circuits keeping the appropriate balance between early differentiation and self-renewal maintenance states.
it is important to point out that the gmt files, both from the chip data and lof/gof gene expression data have large nc, i.e., many rows in each of the two gmt files.
in addition, each row is relatively short, having only few factors or regulator listed in each row.
as seen from the examples applied on random artificial networks, such data should recover networks with high fidelity because it is likely to contain enough information to recover the network.
indeed, histograms of the scores show clear segregation of scores into high and low after applying the bias adjustment .
however, the networks that govern stem cell regulation are mostly unknown so we cannot fully validate these inferred networks.
identifying statistical interactions between drugs and side effects
next, we used the network inference approach to mine statistical interactions from the fda’s spontaneous adverse event reporting system .
this database contains millions of records entered by physicians in the united states recording data from patients.
each record contains a patient record number, the drugs the patient was taking and the adverse events they experienced.
from the database we first extracted the most recent one million records .
to consolidate drug names we converted all entered drug names to their generic names using synonyms from drugbank  <cit>  and drugs.com.
records that contained drug names that could not be mapped to generic drug names were dropped.
this resulted in a loss of about ~20 % of all records.
we then treated the left-over  <dig>  entries from the aers database as the potential set ci where we treated drugs and side-effects as connected subgraphs in the underlying drug-drug, drug/side-effect, and side-effect/side-effect statistical interaction network.
because of the computational complexity of the problem and to save execution time, we only used the most recent  <dig>  records from this dataset to create the actual network we visualize .
the meaning of drug-drug interactions in this context is that these drugs are commonly co-prescribed; side-effect/side-effect interactions mean that the side-effects co-occur; and drug/side-effect interactions are common associations between drugs and side-effects.
in total, the resultant network connected  <dig> drugs and  <dig> side effects.
the visualization of this network as a heatmap adjacency matrix clearly shows that there are clusters of co-prescribed drugs and co-occurring side effects and interactions between these clusters .
to drill down into more specific examples of such interactions we selected a subset made of  <dig> drugs used to treat cancer:  <dig> cytotoxic drugs and  <dig> drugs that target cell signaling pathways.
we connected these drugs to a subset made of  <dig> severe side effects .
this heatmap shows a strong link between chemotherapeutics and cardiovascular related adverse events where cytotoxic cancer therapeutics are commonly co-prescribed with drugs that target cell signaling components.
one of the interesting links that the method uncovered is the strong link between anemia and bortezomib, a cancer drug that is also used to treat other diseases such as lupus.
whether bortezomib is helpful in curbing anemia, causes anemia, or should be prescribed to patients that already have anemia is controversial  <cit> .
it also highlights the fact that side-effect entries in aers are not necessarily indicative of a direct causative relationship, and apparent statistical relations between taking drugs and side effects can appear due to other correlates, and could even appear when the drugs is prescribed to treat the side-effect.
while this network of drugs and side-effects illuminates some initial relationships between approved drugs and the side-effects these drugs elicit, there is much more to explore in this realm.
causative relationships and correlation artifacts may leave their imprint in the network structure as revealed with our method.
for example, the innocent bystander effect may appear as a clique where a group of drugs have a strong connection to a side-effect, but also a strong connection to each other.
this then opens up the possibility of applying additional network analysis to extract causative drug/side-effect relationships from our initial undirected drug/side-effect network.
mount sinai collaboration network
finally, we show how the network inference approach can be applied more broadly to construct other types of networks.
the gmt representation lends naturally to the inference of co-authorship networks where each row in the gmt file derives from a publication where the authors of the publication are listed in each row.
using pubmed e-utilities’ e-search function we searched for the latest  publications that contain an affiliation equal to the term mount sinai school of medicine.
from the returned list of publications, we downloaded the top  <dig>  abstracts returned by the search query and extracted the author list using the e-fetch function.
for each paper, the data was formatted into a gmt file with the pubmed id as the set label and each author of each paper as the members of each set.
after the assembly of the gmt file, the approximation algorithm was applied to the data.
the final network contains only edges with scores higher than  <dig>  .
the network shows known clusters of investigators from various departments identifying many of the relationships we are familiar with and can confirm .
CONCLUSIONS
network inference is a process by which a network is resolved from indirect data.
in cases where direct determination of the network is difficult or impossible it is necessary to use indirect evidence which can be more easily obtained.
here we show that using collections of related entities, which are easy to accumulate, we can resolve the underlying network.
we drew the analogy that the indirect empirical data describes a macrostate, and the ensemble of networks consistent with this data is the available microstates.
as the empirical data accrues there are more constraints and the size of the microstate ensemble shrinks until the underlying network resolves.
we employed the formulation of ergms from park and newman  <cit> , providing a statistical mechanical framework for artificial network models, to derive the appropriate ensemble.
the network ensemble was then used to evaluate the statistical evidence for the underlying network given the data.
we applied the approach to synthetic data we generated as well as to two pertinent specific examples from systems biology, namely ppi prediction and stem-cell regulatory network reconstruction.
in addition we provide one example from systems pharmacology, namely identifying statistical interactions between drugs and side-effects, and one example of co-authorship network, connecting mount sinai investigators.
the networks we reconstructed are not only validated by known interactions but also offer predictions for interactions that are likely real and could be further validated experimentally.
all these networks and datasets are provided on the web at http://www.maayanlab.net/s2n with a web-based open source software tool that can be used to convert any entity-set library to a network.
while useful for addressing problems in current biology and biomedicine, the approach is of general significance and can be applied in other fields that study complex systems.
competing interests
the author declare that they have no competing interests.
authors’ contributions
nrc and am designed the study and wrote the manuscript.
nrc generated all figures and conducted the computational analyses and mathematical derivations.
rd developed the web-site.
mek collected ppi interactions from publicly available resources.
cmt processed the data from aers.
all authors read and approved the final manuscript.
supplementary material
additional file  <dig>
predicted ppis.
click here for file
additional file  <dig>
list of  <dig> complexes.
click here for file
additional file  <dig>
images of predicted  <dig> complexes.
click here for file
acknowledgements
this work was supported in part by nih grants p50gm071558- <dig>  r01dk088541-01a <dig>  rc2lm010994- <dig>  p01dk056492- <dig>  rc4dk090860- <dig>  and r01gm <dig>

 the skeleton of complex systems can be represented as a network where vertices represent entities and edges the relations between these entities. often it is impossible, or expensive, to determine the network structure by experimental validation of all the interactions between all the vertices. it is usually more practical to infer the network from surrogate observations. uncovering the relations between entities from indirect evidence is known as the problem of network inference or reverse engineering of networks from data. while many algorithms have been developed to infer networks from quantitative data of systems’ entities states, less attention has been placed on methods to infer networks from repeated observations of related sets. there are many cases in which groups or clusters of interrelated entities are known or can be observed experimentally. typically such information is much more readily accessible than direct evidence of pair-wise interactions or even quantitative information about the entities under different conditions or time points. each of these sets of related entities provides some information about the connectivity of the underlying network, and it would be of value to be able to utilize this information to resolve the connectivity of the underlying network connecting these entities. this inference process applies to a general class of inference problem of broad applicability; however, our motivation comes from problems in systems biology and systems pharmacology. the tide of high-throughput biological data makes the inference of biological networks both more necessary and possible. there have been a number of success stories in the application of these methods to understand real biological phenomena. however, the multitude of components in biological molecular intracellular systems and their combinatorial interactions means that the possible networks that are consistent with observed data are astronomically large. since we cannot directly observe many components of this system at once, and methods to profile binary interactions are expensive and laborious, the network remains under-determined; there are many networks which can equally well explain the observed data. however, in recent years the ability to sequence dna, rna and protein, together with the accumulation of prior knowledge about functional and physical relationships between genes and proteins, lends itself to a better ability to infer the underlying networks that govern the phenotype of mammalian cells. at the same time, a new field is emerging called systems pharmacology. systems pharmacology aims to integrate knowledge about drugs, drug-drug interactions, drug interactions with cells and organs, and drug relations to adverse events and desired effects in individual patients. however, mining such data from various sources is challenging. current network inference methods employ a number of different strategies to reduce the search space of network structure solutions. naturally, each strategy makes certain compromises and assumptions and has particular advantages and limitations. while methods to infer networks from quantitative biological data have been popular, in particular methods such as bayesian networks inference and network inference based on mutual information, there has been less focus in systems biology on inferring co-occurence networks from sets of related entities and the applications thereof, while such an approach has been successfully applied more in other fields. in most high-throughput methods that collect molecular biological data from cells, the underlying network is not known. typically subsets of related molecular components are observed. for example, groups of co-expressed genes across different samples and contexts may be identified from transcriptomics data. another example is groups of proteins which are listed in pull-down proteomics experiments that use immunoprecipitation followed by mass spectrometry for protein complex identification. the identified genes or proteins may be regarded as the vertices of the underlying gene regulatory, cell-signaling or protein-protein interaction networks. extraction of the underlying network from such data can be achieved in many ways. in addition, the popular method of gene set enrichment analysis uses libraries of related gene sets stored in the gene matrix transposed format. in principle, and in most cases, within gene set libraries, each subset of related genes can provide some coarse local information about the connectivity of an underlying molecular network. as these gene sets accumulate, the underlying molecular networks that regulate mammalian cells may be resolved based on co-occurrence of genes within sets. we aim to employ the accumulation of course local information, from high-throughput experiments, to infer fine details of the global network. here we give this idea a firm foundation and show that given accumulating subsets of related entities, the underlying network can be inferred with high fidelity, and if enough data is available, the network can be inferred completely. when the subsets of related entities do not provide enough information to infer the network with full confidence, we can extract all the possible information about the connectivity of the underlying network from the related set data to arrive at a best guess which can provide insights into the structure within the data. the method we present here makes no a priori assumptions about the structure of the network or the nature of the edges. we begin our approach by grounding the solution in the fundamental principles of statistical mechanics. we numerically execute the solution on synthetic random networks to demonstrate its power. we then proceed to apply the method to real-world biological, clinical and social datasets in order to predict direct human protein-protein interactions inferred from a recent ht-ip/ms dataset; infer a network that connects mouse embryonic stem cell regulators based on data from chip-seq and loss-of-function/gain-of-function followed by expression data; learn a network that connects cancer drugs and common and severe side-effects extracted from thousands of patient records reported in the aers database; and discover a network that connects authors based on co-authorship of publications listed on pubmed. methods exponential random graphs exponential random graphs models are a means of generating an ensemble of networks with prescribed statistical properties with the aim of modeling real-world networks. ergms were introduced by holland and leinhardt and have a long history in complex systems research and are commonly applied in statistics and social science. ergms have been used for modeling complex brain networks but their use in computational systems biology is scant. park and newman showed that ergms are the natural extension of the fundamentals of statistical mechanics to network modeling. here we adopt this formalism. the set of graphs g represents the sample space of graphs in the model, and, {xi}, i =  … r, represent a set of r empirical observations. then a probability distribution p, can be defined over the elements g in g, such that the expectation value of xi takes the empirical values. the best choice of probability distribution is the one which satisfies the empirical constraints, ∑gpgxig=<xi>, while admitting no further information about the model graphs, which is achieved by maximizing the gibbs entropy, s=−∑g∈gpglnpg. this leads to a probability distribution which is the network equivalent of the boltzman distribution, pg=e−hgz where h is the graph hamiltonian function with lagrange multipliers θi, hg=∑iθixig and z is the partition function over the set of graphs g, z=∑ge−hg this probability distribution defines the exponential random graph model networks which obey the mean constrains of equation  but which are otherwise maximally disordered. dependence graphs pattison and wasserman showed that ergms can be generated in terms of dependence graphs. we shall briefly review these graphs here in the context of simply connected undirected networks, as they are relevant to the inference problem we address. the graphs which represent undirected simply connected networks can be represented by an adjacency matrix gij, which is symmetric and has elements, gij={1ifviandvjareconnectedbyavertexing0otherwise the ergms define a probability distribution over g, and a model network, gij may be regarded as a realization of a random variable which is defined as a random selection from g over the probability distribution p. the dependence graph, d, has vertices which correspond to the edges in gij. the edges of d connect vertices which are not conditionally independent. so the dependence graph identifies pairs of edges whose presence in the model network depends on each other. the hammersley-clifford theorem then states that the model probability distribution, p, only depends on the complete subgraphs of the dependence graph. inference approach the inference problem addressed here is now phrased in terms of ergms. given an unknown underlying network, gu, with vertices, v, we consider a set, c, composed of many subsets of the network’s vertices, c=ci,ci⊂v,i= …,nc, such that c is a field over the set of vertices. the sets ci consist of vertices which are empirically observed to be related in the network, this could be for example, proteins identified in a mass-spectrometry proteomics pull-down, members of a cell signaling pathway, or co-authors of a publication. the central assumption is that each of the sets ci identifies a locally connected subgraph of the underlying network. in these terms, the network inference problem we pose is thus: given the set of nc subsets, c, and no other information, to what extent can we infer the underlying network gu? to give a specific example, we may consider the results from ht-ip/ms, after appropriate filtering, as identifying a locally connected region of the underlying human protein-protein interactome network. we hypothesize that we can resolve the underlying ppi network given enough observations of sets of proteins identified in different pull-downs. in these terms, the proteins would be represented by the vertices vi, and the list of proteins identified in each pull-down experiment would correspond to one element of c, while the underlying ppi network would be represented by gu. we are aware that we are searching for a static configuration of the network, whereas the underlying connectivity in complex systems, including ppis and gene-regulatory networks, is dynamic as it may change over time and under different conditions. we define our observable graph functions, xi in the following way, xig={1iftheelementsofciformaconnectedsubgraphofg0otherwise if we interpret each set as providing course local information on the connectivity of the underlying gu, such that we have a confidence, α, that the elements in each line are locally connected, then the constraints on the ensemble are the following, ∑gpgxig=α in which case the maximum entropy probability distribution function p identifies an ensemble of networks which have a connectivity consistent with the known input set c but which are otherwise maximally disordered, we shall refer to this as gens. in our studies of the properties of our inference approach on synthetic networks we shall generate data which identifies locally connected regions of the underlying network and so we shall take the value of α =  when we apply our inference approach to data from systems biology the value of α will typically be less than unity as there will generally be only a finite degree of confidence in the connectivity of each local region identified in the data. the above constraints leading to the probability distribution p can also be seen in terms of a dependence graph, d, for the corresponding ergm. each set ci contains vertices between which a set of edges are assumed to exist in the underlying network in order to form a locally connected subgraph. over the ergm ensemble, the presence of each of these edges is conditionally dependent upon the others. these edges form a complete subgraph of d, and therefore, according to the hammersley-clifford theorem, define the probability distribution p. in the approach presented here we make no attempt to infer directionality, hence, we take the sample set, g, to consist of simple undirected graphs. the data contained in, c, constitutes an accumulation of course local information on the connectivity of the underlying network. even with large amounts of this class of data the network often remains underdetermined, hence there exists a whole ensemble of networks which are consistent with the data. in order to infer finer details of the underlying network we adopt some of the philosophy of network modeling to take a sample of this ensemble, and then use the properties of this ensemble for inference. here we take the sample numerically by using an algorithm which generates a random sample of the ensemble. the algorithm ensures that the sampled network has the local connectivity consistent with the data while minimizing the number of edges. the edge minimization ensures the strongest signal from the data in the sense that edges only appear in the ensemble as required by the data. the algorithm works by generating a random sample, of size ng, of the ensemble of networks gens consistent with the data. according to the assumptions of the inference, the gmt file contains a number nc of lines, ci, each of which consists of vertices which are locally connected in the underlying network. the algorithm first randomly permutes the order of the lines in the gmt file, then, starting with the empty graph which consists of the set of nodes and the empty set of edges ei = {}, it builds a network by taking each line and introducing a minimal number of random links that connect the vertices in that line. the pseudo-code for the algorithm is then: for i =  to ng randomly permute the order of the lines in the gmt file ei = {} for j =  to nc randomly introduce a minimal number of edges between the vertices ci such that they are connected, and continually append to the set ei end for i end for j calculate the mean adjacency matrix of the ensemble gens a sample of random networks generated in this fashion constitutes a random sample of gens. the properties of this ensemble are then used to infer the underlying network gu. specifically, we calculate the mean adjacency matrix over this ensemble, each element of which corresponds to the probability of the edge being present in a uniformly random draw from the ensemble; this is interpreted as being indicative of the accumulation of information on the presence of the edge in the underlying network. analytical approximation the algorithmic sampling of the ensemble gens becomes computationally demanding when inferring networks with many vertices, and large amounts of data. when applying the approach to infer biological networks from large high-throughput datasets which although sparse, can have thousands of vertices, we look for an efficient analytical approximation to the algorithmic solution. the approach we take is to analytically mimic the function of the fully executed algorithm that generates the networks, which are samples of gens. the first order approximation is to treat each ci as generating an independent minimally connected bernoulli random graph, in which each edge has an independent and equal probability of appearing. then the superposition of all the ci may be regarded as a bernoulli process in which each edge undergoes a series of bernoulli trials with probabilities corresponding to the random graphs generated by each of the elements of c. in this approximation the probability that a given edge is present in gu is given by, pij=1−Πk1−2αnij,k where nij,k is the size of the kth elements of c to which both vertices vi and vj belong. alternative co-occurrence scoring methods to compare the above methods to other approaches that can be used to construct networks from repeated observations of co-occurence of entities in related sets we compare our approach to two alternatives. a simple difference of proportions test to measure co-occurrence strength is applied as follows: for two given vertices, a and b, a contingency table can be constructed with f, f, f, and f where f indicates the frequency of lines ci in c where x is true. we then use the chi-squared test of difference of proportions to test the significance of the co-occurrence. then the probability of interaction between a and b is calculated as one minus the p-value. in addition, the simplest possible form of inference from co-occurrence whereby the probability of an edge between a and b is given by the ratio of the number of ci in the gmt file in which both a and b occur to the total number of lines, nc, is also used as a comparison. bias adjustment while artificial random networks can be evenly and randomly sampled, real world datasets contain sampling biases where some vertices are measured more often. for example, well-studied genes/proteins appear in more publications and thus commonly have more reported interactions with other genes/proteins. this inhomogeneity of information throughout the network means that the inferred interactions are as sensitive to the frequency with which particular vertices are observed as to the strength and specificity of the edges between the vertices. in order to correct for this and calculate probabilities which are only sensitive to the strength of the interactions, we generate a null distribution for each edge probabilities under the hypothesis of no specific interaction. this is achieved by calculating the distribution of each edge-probability pij in the network after any information on the network connectivity has been destroyed: the gmt file data is randomly permuted, while preserving its structure by conserving the lengths of each set and the frequency of each element throughout the data, and allowing only one of each type in any given set/line, then all the edge weights are calculated. this process is repeated to generate the null distribution for each edge weight. by comparing the actual edge weight to this null distribution, under the hypothesis of no interaction, we obtain a p-value which quantifies the edge-probabilities after correction for the sampling bias. this p-value is then used as a measure of the strength of the interaction. combining evidence from multiple gmt files to build a consensus network we can combine several types of datasets stored in different gmt files to form a consensus network. by combining two or more different inferred network perspectives we may gain additional insight into the functional associations between related vertices. when combining data from several sources we rewrite equation  for the edge probabilities as: pi,j=1−Πk1−2αni,j,kΠk′1−2α′ni,j,k′…, where the terms in each square bracket come from each distinct data source and the greek letters are the corresponding confidence parameters. to compute scores that consider the bias adjustment, the distribution of edge weights from randomly permuted gmt files are generated using the same equation and the same steps described above for inferring probabilities for edges for individual networks. matthews correlation coefficient to evaluate inferred networks to evaluate the quality of the predicted edges we use the matthew's correlation coefficient. mcc is a balanced measure of the quality of binary classifications, and it is equal to unity when the classification is perfect; it is computed by the following equation: mcc=tp×tn−fp×fntp+fptp+fntn+fptn+fn where fp and fn are the false positives and negatives respectively, and tp and tn are the true positives and true negatives respectively.  inference of synthetic networks first we investigate the quality of inference using our approach by applying it to synthetic test networks. we begin with a randomly generated connected graph serving as the underlying network gu that we wish to infer, which is also represented by its adjacency matrix. the set c used to generate a gmt file is created by performing short random walks starting on random vertices. the idea is to infer gu only using the information from c. the ensemble, gens, is generated algorithmically by randomly introducing a minimum number of links in order to connect successive sets of vertices ci. a small selection of the calculated elements of gens is shown in figure 1c. the mean adjacency matrix of this ensemble is then calculated. the elements of the mean adjacency matrix are interpreted as probabilities that a given link is present in gu. due to the binary nature of the edges, a comparison can be made between the underlying network gu and the mean adjacency matrix, after the application of a threshold value of pt. a histogram of edge probabilities, pij, shown in figure has a bimodal form which appears to distinguish between edges present in the underlying network and edges not present in the underlying network. in addition, on the x-axis we plot the mcc as a function of the threshold pt. in other words, we plot the mcc where we cut the inferred adjacency matrix to decide which scores will constitute an edge. if we set a large threshold value there will be only few edges remaining in the network and thus many false negatives and lower mcc. conversely, as the threshold is reduced to zero the network will tend to completeness and thus will include many false positives. there is a region of pt where the similarity between the inferred network and the underlying network is greatest. this region corresponds to the peak of the mcc curve. the aim of applying the inference approach to such synthetic networks is to investigate the quality of the inference in a case where the underlying network is known. this investigation requires several steps. first, because the approach requires a random sample we must investigate the convergence of the statistics deriving from this sample. once the rate of convergence is known the required sample size ng for a given degree of convergence is obtained and the method may be reliably applied. the next step is to examine the quality of inference and its dependence on the properties of the available data. finally, with a view to the application of our method to problems in systems biology we examine the computational complexity and running time of our approach. convergence of inferred networks our inference approach is based on the mean of a random sample of networks which are consistent with our data. the rate of convergence of this statistic depends on the properties of the data upon which the ensemble is based and so a general convergence rate does not exist. we can however derive an upper limit to the rate of convergence by considering the convergence in the worst-case-scenario. in this case there is no information on the connectivity of the underlying network, and therefore the largest possible ensemble of consistent networks and so the slowest rate of convergence. here we derive the rate of convergence of the mean in this case as the upper limit for the rate of convergence. in this worst-case every connected network with n edges is a consistent network. in a random sample of these networks a given edge has a probability 2n of being present in any given network. effectively, for a given edge, each sampled network constitutes a bernoulli trial, and therefore in a random sample of ne consistent networks, the total number of times any given edge is present, x, follows a binomial distribution with ne trials at a probability of success of p=2n. if we use our sample to estimate this probability, pest=xne, then the resulting estimate will be distributed by a binomial distribution with mean, p, and variance given by varxne which can be written as, p1−pne. the signal-to-noise ratio is sometimes written as the ratio of the mean to the variance, so in this case it is given by, snr=pne1−p which we can use to gauge the convergence by requiring that ne is large enough to achieve a certain signal-to-noise ratio. given that p=2n, it means that the ensemble size must increase in proportion to the number of nodes n, in order to preserve a constant signal-to-noise ratio. the ensemble size required to achieve a given signal-to-noise ratio in this case can be written as, ne=n2−1snr and this is the formula used to determine the sample size throughout all applications of the algorithm presented here. the above estimate can be used as an upper limit to the ne required for the mean to converge to a given signal-to-noise ratio in the case of general gmt file data; this is because such gmt data file is more informative, hence the size of the ensemble of consistent networks is smaller, and a smaller sample is required for inferring the underlying network. we demonstrate this in a plot of the signal-to-noise ratio against the size of the ensemble for inference of a node network. accuracy of inference having quantified the convergence of the inferred network with the sample size nc,, the next consideration is how similar the inferred network is to the underlying network from which the data derives. the quality of the inference depends on the data contained in the gmt file. as the number of lines in the gmt file, nc, increases, the information on the presence of edges accumulates and the inferred network becomes more similar to the underlying network. the length of the lines in the gmt file also influences the quality of the inference; larger lines provide coarser information on the connectivity of the network and thus are less informative. finally, the more nodes are in an underlying network the greater the amount data required to infer its structure. here, for a given number of n odes, n, in a minimally connected network we examine the quality of inference and how it depends on nc, and the length of the lines in the gmt file. we begin by examining the dependence on the number of lines in the gmt file. we infer the structure of a minimally connected network with n =  from gmt files with a range of to lines. to quantify the quality of the inference we use the maximum value of the mcc. in figure we plot the maximum mcc against the number of lines in the gmt file, nc,, using four different methods of inference: 1) the full-algorithm 2) the analytic approximation 3) chi-squared difference of proportions 4) simple co-occurrence. in each case we see that as nc increases, i.e. with more data, the accuracy of the inference increases and tends towards ideal inference. this is when the inferred network is exactly the same as the underlying network. we also observe that the full algorithm described above is more accurate than the other methods, but the analytic approximation is also more accurate than more basic co-occurrence approaches. finally we examine the dependence of the accuracy of inference upon the size of the sets in the gmt file. in figure we plot the mean quality of inference as measured by the maximum mcc. the four curves correspond to inference from synthetic gmt files with random walks of lengths of and longer random walks result in gmt files with longer lines, and therefore coarser information on the connectivity of the underlying network. we see that each curve has the same tendency to increase the quality of inference with increased nc, however, the rate reduces with increasing size of set in gmt file, shorter lines. in this way we show that for coarser information more data is required to infer the network. running time and computational complexity while the fully executed algorithm is potentially useful, in practice it is not practical due to its computational complexity. the operations to execute the fully enumerating algorithm depend on ne, nc, and the length of the elements in each ci, which are inherently random so we shall refer to the mean length cavg. from the structure of the pseudo-code we expect that the number of operations should increase in proportion to each of these three quantities, as well as the number of vertices n, i.e., o. in the case of real data, nc can be of the order of typically or and there can be typically thousands of vertices, so the number of operations for this method of inference can be prohibitively large. for the analytical approximation with equation  described under analytical approximation above, the number of operations required for the computation depends on the details of the data as this determines the number of operations. the number of evaluations increases as o. however, the number of operations required for each evaluation depends on the structure of the data within the gmt file. comparison of running times between the fully executed algorithm and the approximation is shown in figure 7figure 7; this shows that the analytical approximation is two orders of magnitude faster than algorithmic sampling and therefore more practical for generating networks from real datasets stored as gmt files. in the next sections we employ the approximation for the inference of ppis from ht-ip/ms data, construct a network of stem cell regulators from chip-seq and loss-of-function/gain-of-function followed by expression data, construct a network between cancer drugs and severe side effects from patient records, as well as construct a co-authorship network connecting researchers from mount sinai school of medicine in new york. application to ppi prediction from ht-ip/ms data the identification of binary interactions between proteins is an important task in systems biology. initially, information on ppi networks in mammalian cells came from targeted experiments involving a small number of proteins. however, experimental techniques can now explore ppis in human and mouse cells at large-scale. in addition, large numbers of ppis from small-scale experimental studies are continually aggregated in publicly available databases. in a recent study, malovannaya et al. reported the results from over ht-ip/ms experiments applied to nuclear co-regulators and members of their complexes in human cells. with this experimental technique, antibodies are used to pull-down a bundle of proteins that can be identified with mass-spectrometry. a total of antibodies were used in immuno-precipitation experiments of nuclear extracts from human cell-lines, in the course of which individual protein detections were made. non-specific binding events significantly contribute to the protein detection data and it is necessary to filter these out; we used the same filter used by the authors of the study which reduced the number of individual protein detections to. because the proteins are bound together in each pull-down, each of the experiments may be regarded as identifying a locally connected subgraph of the underlying binary ppi network. this type of information on the underlying network is equivalent to the class of data discussed above. the list of proteins identified in each experiment may be identified with the field c, and a mean adjacency matrix may be calculated from equation  then finally the sampling bias correction can be made to derive a predicted weighted adjacency matrix. this matrix quantifies the confidence of each binary direct physical ppi given solely the information on the connectivity of the underlying network derived from the collection of pull-down experiments. this approach is similar to our recently proposed reanalysis of this dataset since it does not consider the baits used in each experiment to determine direct protein interactions. a large value of pi,j may indicate that there is potentially sufficient information to suggest that protein vi and vj directly physically bind to each other. however, although large, the amount of data in this ht-ip/ms dataset is not large enough to fully resolve the underlying network of ppis, so a small value of pi,j does not necessarily indicate that the pair of proteins do not directly bind, only that there is not enough information in the dataset to suggest that they do. as the network is not fully resolved, the results of this inferential process could be used to rank the binary interactions to suggest likelihood of interactions for more targeted validation. alternatively, the mean adjacency matrix could be used to gain a course grained global view of the human nuclear co-regulation complexome. to evaluate the reliability of predicted interactions we used benchmarking to compare predicted interactions to known interactions. benchmarking is important for determining the quality and reliability of network inference approaches, and we attempt here to evaluate our inference approach applied to this data. the typical approach is to take the union of many current curated ppi databases and treat the interactions therein as true positives. this is imperfect because these databases contain significant numbers of false positives and false negatives, penalizing inferences that may be discovering correctly unknown interactions. with these concerns in mind, we followed this procedure to evaluate our inference method. first we used the list of proteins identified in each pull-down to define the sets of proteins forming a connected subgraph of the underlying ppi network; this defines the subsets ci composing the field c. we then used the approximation shown in equation  to estimate the mean adjacency matrix. we then collected ppi data from the following databases: biogrid, hprd, innatedb, intact, kegg, kea, mint, mips, dip, bind, biocarta, pdzbase, ppid, yu et al., stelzl et al., ewing et al., rual et al. and ma’ayan et al.. we treated this data as the set of true positives and compared our mean adjacency matrix to it. to evaluate our ability to predict interactions we plotted the receiver operator characteristic curve and the mcc as a function of the threshold value of pt. in addition, we observe that prior to the sampling-bias-correction, the distribution of edge weights decays monotonically, whereas after, there is a bimodal distribution which is reminiscent of the observed histogram shown in figure for the random network inference score distribution. the inhomogeneous distribution of protein frequencies throughout the experimental data suggests a sampling bias. however, the change in distribution of edge weights from unimodal to bimodal suggests that the bias has been removed to some extent. this is confirmed by the roc and mcc curves that show that the bias adjustment results in improved accuracy above the uncorrected inference or co-occurrence computed using enrichment analysis with a chi-squared test. altogether, the predicted network of protein-protein interactions can suggest novel binary physical protein-protein interactions amenable for functional experimental validation. the top predicted interactions are provided in additional file 1: table s and on the web at http://www.maayanlab.net/s2n/ppi.html. to further validate the inferred ppi network, we compared the ability of the predicted interactions to recover known protein complexes listed in the corum database. we filtered the corum database, retaining only those complexes for which at least 80 % of the subunits are detected in the ip/ms data upon which we based our inference. in addition we retained only those corum complexes which had at least four proteins. the result was fifty corum protein complexes which could be potentially inferred from the ip/ms data. for each of these protein complexes, we generated three lists: 1) the known corum complex members; 2) proteins which are inferred to have significant interactions with the complex members either by having interaction-strength above the threshold resulting in maximum mcc with any individual member, or mean interaction strength across all complex member in the 95th percentile; 3) a list of random proteins to provide a scale for the background. we then performed hierarchical clustering on the complex members and a clustering based on clique membership on the additional proteins that strongly interact with the complex members. such interactions are visualized in adjacency matrices heatmaps that show that our method recovered many known complexes and is capable of predicting additional members of known complexes. adjacent to each heatmap of predicted interactions for each complex are connectivity maps in the same order where elements indicate membership in at least one of the ppi databases listed above. a comparison of these two adjacency matrices shows that the corum complexes are clearly well inferred with our method, and also that we can observe interactions with potential proteins and protein complexes which are currently undiscovered experimentally. focusing on two such complexes, figure shows identified relationship between the mini chromosome maintenance complex and the proteasome, whereas in figure additional components are suggested for the tfiih transcription factor complex. the relationship between the mcm complex and the proteasome appears to be divided into two mutually exclusive sets of proteasome related components that do not interact with each other. revealing associations between stem cell regulators in the past few years a tremendous number of high-content experiments have profiled different aspects of mouse embryonic stem cells. such experiments include gene-expression microarrays at different conditions, genome-wide histone modification and transcription factor binding to dna using chip-seq, rnai screens for identifying pluripotency regulators, proteomics, phosphoproteomics and microrna profiling. while these experiments have the potential to fully uncover the regulatory networks governing stem-cell maintenance and differentiation into specific lineages, data integration across regulatory layers to extract new knowledge from such data is challenging. the network inference method we employ here can be utilized for data integration by building networks from various sources of data. using equation  we can construct networks that combine information from multiple types of gmt files. from the stem cell literature we collected publications that reported: a) transcription factor, and other transcriptional regulators, binding to the promoters of target genes as determined by chip-seq or chip-chip experiments; and b) gene expression changes after the knockdown or over-expression of these factors and regulators as determined by gene expression arrays. we then converted such data into two gmt files: the first with each row having a set of transcription factor target genes from each chip-seq or chip-chip experiment, and the second having in each row a set of differentially expressed genes for each factor or regulator from each gene expression loss-of-function or gain-of-function experiment. we then transposed these two files were the target genes are the row labels and the factors and regulators are listed in each row. finally, we generated three networks: 1) based on the chip data alone; 2) based on the gene-expression after knockdown or over-expression data; and 3) based on combined data using equation . the chip network contains four clusters, the first of which includes the known pluripotency maintenance regulators: nanog, oct and sox2; the second cluster corresponds to the polycomb repressive complex; the third cluster includes early differentiation regulators including myc and mycn; the remaining cluster is made of klf klf and klf which likely have overlapping unique set of target genes. the lof/gof followed by expression network is more difficult to explain. nanog, oct and sox still appear together and are directly connected. however, the other components appear in other clusters that are more difficult to define based on what is known. finally, the combined network shows an interesting pattern: the triad, nanog, oct and sox appears in the center of two highly connected clusters, one containing other known pluripotency regulators including tbx esrrb, klf sall and tcf whereas the other cluster contains more differentiation components. it is plausible that the triad of nanog, oct and sox is regulating both highly dense circuits keeping the appropriate balance between early differentiation and self-renewal maintenance states. it is important to point out that the gmt files, both from the chip data and lof/gof gene expression data have large nc, i.e., many rows in each of the two gmt files. in addition, each row is relatively short, having only few factors or regulator listed in each row. as seen from the examples applied on random artificial networks, such data should recover networks with high fidelity because it is likely to contain enough information to recover the network. indeed, histograms of the scores show clear segregation of scores into high and low after applying the bias adjustment. however, the networks that govern stem cell regulation are mostly unknown so we cannot fully validate these inferred networks. identifying statistical interactions between drugs and side effects next, we used the network inference approach to mine statistical interactions from the fda’s spontaneous adverse event reporting system. this database contains millions of records entered by physicians in the united states recording data from patients. each record contains a patient record number, the drugs the patient was taking and the adverse events they experienced. from the database we first extracted the most recent one million records. to consolidate drug names we converted all entered drug names to their generic names using synonyms from drugbank and drugs.com. records that contained drug names that could not be mapped to generic drug names were dropped. this resulted in a loss of about ~20 % of all records. we then treated the left-over entries from the aers database as the potential set ci where we treated drugs and side-effects as connected subgraphs in the underlying drug-drug, drug/side-effect, and side-effect/side-effect statistical interaction network. because of the computational complexity of the problem and to save execution time, we only used the most recent records from this dataset to create the actual network we visualize. the meaning of drug-drug interactions in this context is that these drugs are commonly co-prescribed; side-effect/side-effect interactions mean that the side-effects co-occur; and drug/side-effect interactions are common associations between drugs and side-effects. in total, the resultant network connected drugs and side effects. the visualization of this network as a heatmap adjacency matrix clearly shows that there are clusters of co-prescribed drugs and co-occurring side effects and interactions between these clusters. to drill down into more specific examples of such interactions we selected a subset made of drugs used to treat cancer: cytotoxic drugs and drugs that target cell signaling pathways. we connected these drugs to a subset made of severe side effects. this heatmap shows a strong link between chemotherapeutics and cardiovascular related adverse events where cytotoxic cancer therapeutics are commonly co-prescribed with drugs that target cell signaling components. one of the interesting links that the method uncovered is the strong link between anemia and bortezomib, a cancer drug that is also used to treat other diseases such as lupus. whether bortezomib is helpful in curbing anemia, causes anemia, or should be prescribed to patients that already have anemia is controversial. it also highlights the fact that side-effect entries in aers are not necessarily indicative of a direct causative relationship, and apparent statistical relations between taking drugs and side effects can appear due to other correlates, and could even appear when the drugs is prescribed to treat the side-effect. while this network of drugs and side-effects illuminates some initial relationships between approved drugs and the side-effects these drugs elicit, there is much more to explore in this realm. causative relationships and correlation artifacts may leave their imprint in the network structure as revealed with our method. for example, the innocent bystander effect may appear as a clique where a group of drugs have a strong connection to a side-effect, but also a strong connection to each other. this then opens up the possibility of applying additional network analysis to extract causative drug/side-effect relationships from our initial undirected drug/side-effect network. mount sinai collaboration network finally, we show how the network inference approach can be applied more broadly to construct other types of networks. the gmt representation lends naturally to the inference of co-authorship networks where each row in the gmt file derives from a publication where the authors of the publication are listed in each row. using pubmed e-utilities’ e-search function we searched for the latest publications that contain an affiliation equal to the term mount sinai school of medicine. from the returned list of publications, we downloaded the top abstracts returned by the search query and extracted the author list using the e-fetch function. for each paper, the data was formatted into a gmt file with the pubmed id as the set label and each author of each paper as the members of each set. after the assembly of the gmt file, the approximation algorithm was applied to the data. the final network contains only edges with scores higher than. the network shows known clusters of investigators from various departments identifying many of the relationships we are familiar with and can confirm.  network inference is a process by which a network is resolved from indirect data. in cases where direct determination of the network is difficult or impossible it is necessary to use indirect evidence which can be more easily obtained. here we show that using collections of related entities, which are easy to accumulate, we can resolve the underlying network. we drew the analogy that the indirect empirical data describes a macrostate, and the ensemble of networks consistent with this data is the available microstates. as the empirical data accrues there are more constraints and the size of the microstate ensemble shrinks until the underlying network resolves. we employed the formulation of ergms from park and newman, providing a statistical mechanical framework for artificial network models, to derive the appropriate ensemble. the network ensemble was then used to evaluate the statistical evidence for the underlying network given the data. we applied the approach to synthetic data we generated as well as to two pertinent specific examples from systems biology, namely ppi prediction and stem-cell regulatory network reconstruction. in addition we provide one example from systems pharmacology, namely identifying statistical interactions between drugs and side-effects, and one example of co-authorship network, connecting mount sinai investigators. the networks we reconstructed are not only validated by known interactions but also offer predictions for interactions that are likely real and could be further validated experimentally. all these networks and datasets are provided on the web at http://www.maayanlab.net/s2n with a web-based open source software tool that can be used to convert any entity-set library to a network. while useful for addressing problems in current biology and biomedicine, the approach is of general significance and can be applied in other fields that study complex systems. competing interests the author declare that they have no competing interests. authors’ contributions nrc and am designed the study and wrote the manuscript. nrc generated all figures and conducted the computational analyses and mathematical derivations. rd developed the web-site. mek collected ppi interactions from publicly available resources. cmt processed the data from aers. all authors read and approved the final manuscript. supplementary material additional file predicted ppis. click here for file additional file list of complexes. click here for file additional file images of predicted complexes. click here for file acknowledgements this work was supported in part by nih grants p50gm071558- r01dk088541-01a rc2lm010994- p01dk056492- rc4dk090860- and r01gm 
given experimental observations of such sets, we infer the underlying network connecting these entities by generating an ensemble of networks consistent with the data. often it is impossible, or expensive, to determine the network structure by experimental validation of the binary interactions between every vertex pair. exponential random graphs are used to generate and sample the ensemble of consistent networks, and we take an algorithmic approach to numerically execute the inference method. the network inference method presented here can be applied to resolve different types of networks in current systems biology and systems pharmacology as well as in other fields of research. the skeleton of complex systems can be represented as networks where vertices represent entities, and edges represent the relations between these entities. this type of data is ubiquitous in the field of systems biology and in other areas of complex systems research. it is usually more practical to infer the network from surrogate observations. while many algorithms have been developed to infer networks from quantitative data, less attention has been paid to methods which infer networks from repeated co-occurrence of entities in related sets. the effectiveness of the method is demonstrated on synthetic data before employing this inference approach to problems in systems biology and systems pharmacology, as well as to construct a co-authorship collaboration network. network inference is the process by which an underlying network of relations between entities is determined from indirect evidence. here we present a general method for network inference from repeated observations of sets of related entities. we predict direct protein-protein interactions from high-throughput mass-spectrometry proteomics, integrate data from chip-seq and loss-of-function/gain-of-function followed by expression data to infer a network of associations between pluripotency regulators, extract a network that connects cancer drugs to each other and to severe adverse events by mining the fda’s adverse events reporting systems, and construct a co-authorship network that connects mount sinai school of medicine investigators.
 the skeleton of complex systems can be represented as networks where vertices represent entities, and edges represent the relations between these entities. often it is impossible, or expensive, to determine the network structure by experimental validation of the binary interactions between every vertex pair. it is usually more practical to infer the network from surrogate observations. network inference is the process by which an underlying network of relations between entities is determined from indirect evidence. while many algorithms have been developed to infer networks from quantitative data, less attention has been paid to methods which infer networks from repeated co-occurrence of entities in related sets. this type of data is ubiquitous in the field of systems biology and in other areas of complex systems research. hence, such methods would be of great utility and value.  here we present a general method for network inference from repeated observations of sets of related entities. given experimental observations of such sets, we infer the underlying network connecting these entities by generating an ensemble of networks consistent with the data. the frequency of occurrence of a given link throughout this ensemble is interpreted as the probability that the link is present in the underlying real network conditioned on the data. exponential random graphs are used to generate and sample the ensemble of consistent networks, and we take an algorithmic approach to numerically execute the inference method. the effectiveness of the method is demonstrated on synthetic data before employing this inference approach to problems in systems biology and systems pharmacology, as well as to construct a co-authorship collaboration network. we predict direct protein-protein interactions from high-throughput mass-spectrometry proteomics, integrate data from chip-seq and loss-of-function/gain-of-function followed by expression data to infer a network of associations between pluripotency regulators, extract a network that connects cancer drugs to each other and to severe adverse events by mining the fda’s adverse events reporting systems, and construct a co-authorship network that connects mount sinai school of medicine investigators. the predicted networks and online software to create networks from entity-set libraries are provided online at http://www.maayanlab.net/s2n.  the network inference method presented here can be applied to resolve different types of networks in current systems biology and systems pharmacology as well as in other fields of research. 