Systematic, genome-wide loss-of-function experiments can be used to identify host factors that directly or indirectly facilitate or inhibit the replication of a virus in a host cell. We present an approach that combines an integer linear program and a diffusion kernel method to infer the pathways through which those host factors modulate viral replication. The inputs to the method are a set of viral phenotypes observed in single-host-gene mutants and a background network consisting of a variety of host intracellular interactions. The output is an ensemble of subnetworks that provides a consistent explanation for the measured phenotypes, predicts which unassayed host factors modulate the virus, and predicts which host factors are the most direct interfaces with the virus. We infer host-virus interaction subnetworks using data from experiments screening the yeast genome for genes modulating the replication of two RNA viruses. Because a gold-standard network is unavailable, we assess the predicted subnetworks using both computational and qualitative analyses. We conduct a cross-validation experiment in which we predict whether held-aside test genes have an effect on viral replication. Our approach is able to make high-confidence predictions more accurately than several baselines, and about as well as the best baseline, which does not infer mechanistic pathways. We also examine two kinds of predictions made by our method: which host factors are nearest to a direct interaction with a viral component, and which unassayed host genes are likely to be involved in viral replication. Multiple predictions are supported by recent independent experimental data, or are components or functional partners of confirmed relevant complexes or pathways. Integer program code, background network data, and inferred host-virus subnetworks are available at http: //www. biostat. wisc. edu/~craven/chasman_host_virus/.
Our work is related to methods that address several different categories of problems: finding mechanistic explanations for source-target pairs, subnetwork extraction, candidate gene prioritization, and gene set enrichment. One closely related task is to infer the physical interactions that mediate the observed direct or indirect relationships between a source gene and a target gene. The input to these methods is a set of source-target pairs and a background network consisting of unsigned protein-protein and/or protein-DNA interactions. The output is a subnetwork that provides a connection between each source and target. Most closely related to our work are the approaches that globally infer a subnetwork to account for all given pairs by providing paths between them. The Markov network-based Physical Network Model [11] and the integer programming-based SPINE [12] both infer subnetworks in which each source must be connected to its targets by one or more acyclic pathways, and in which the sign of each edge is also inferred. The Physical Network Model also infers directions for edges. Related methods for signaling network orientation [13]–[15] infer edge directions, but not edge signs or node phenotypes. Yosef et al. [16] infer rooted trees that connect a set of sources with a set of targets. Additionally, some methods account for source-target pairs separately, rather than in a global inferred subnetwork [17], [18]. Others employ genetic interactions or correlation of mRNA expression in addition to protein-protein interactions to infer indirect or direct relationships between genes [19], [20]. Our work has similarities to these approaches, particularly those based on integer linear programming, but differs in some key respects. In our setting, the common target of all hits – the virus – is external to the background network, and the identity of the host factors that interact with it directly must be predicted. Additionally, our background network encompasses a greater variety of biological interactions than the background networks used by these other approaches. Unlike the methods that use mRNA expression profiles as the basis for determining direct or indirect relationships between genes, ours uses only phenotypes derived from a genome-wide mutant assay. Recently, Gitter et al. [21] presented an application of their source-target pair-based method to inferring human signaling pathways involved in influenza A viral infection. In their approach, sources are human proteins that are known to directly interact with a viral component, analogous to the interfaces in our conceptual model. Targets are human genes whose expression is measured over several time points during viral infection. The method orients paths through a protein-protein interaction network from the sources to the targets, preferring paths that contain influenza-relevant genes identified by RNAi experiments. Conceptually, this method infers the signaling pathways that control the host' s transcriptional response to viral infection. In this paper, we look at host-virus interactions from the opposite direction and infer the mechanistic pathways by which suppressed host genes inhibit or enable the normal viral replication cycle. Other related methods address the network extraction task: selecting specific types of connecting structures from a background network when a biologically-motivated node- and/or edge-weighting function is available. The structures include rooted trees [22], variants on Steiner trees [23]–[26], random walks and short paths [27], parallel pathways [28], dense highly-connected subnetworks [29], and undirected subnetworks that provide connections between pairs of genes [30]. Unlike our method, these approaches do not distinguish (or infer) phenotype signs and edge signs, nor do they apply global constraints to the extracted subnetwork other than a global edge minimization. In contrast, we employ global constraints such as an upper bound on the number of interfaces. We do not believe that for our task it is appropriate to assume the entire network will be minimal, which is an assumption made by the Steiner tree and shortest-paths methods. Other methods apply graph kernels or flow algorithms to an interaction network to predict and prioritize additional hit genes [31]–[34]. Notably, Murali et al. [33] predict which genes modulate HIV replication in human cell lines. Like these methods, our approach uses a gene ranking method to prioritize genes for inclusion in the inferred subnetwork. However, these methods themselves do not infer consistent, directed pathways, nor do they predict which host factors directly interact with the virus. Our approach combines a gene prioritization method with a directed network inference method. More distantly related to our work, gene set enrichment techniques are widely used to interpret hit sets identified by high-throughput experiments. These methods identify which pre-defined biological components and processes, such as Gene Ontology annotations or KEGG pathways [35], [36], are represented in a set of genes [37]. In contrast, our method does not restrict our pool of candidate genes and interactions to predefined gene sets. Additionally, gene set enrichment-based methods are typically better suited when the task is to identify common annotations within a gene set, rather than to predict a set of high-precision additional hits or relevant mechanistic interactions among known hits.
The input to our approach consists of a set of viral phenotypes observed in a loss-of-function experiment and a background network of intracellular interactions. When available, we can also take advantage of confirmed relevant interactions curated from the literature. We have developed an integer-linear-programming-based approach to infer a directed subnetwork of interactions that are relevant to virus replication in a host cell. The approach infers subnetworks that have the following properties:
We first describe an experiment in which we assess the accuracy of our approach in predicting whether test genes with held-aside phenotypes are hits or not. We refer to this as the hit-prediction task. Previously, diffusion kernel methods like the one we use in our objective function have been successfully applied to this task, which is also called gene prioritization [31], [33]. Using a leave-one-out methodology, we hold aside the measured phenotype for one gene at a time. The set of genes that are held-aside as test cases for the BMV data set includes 104 hits (49 up and 55 down) and 1074 no-effect genes. The test set for the FHV data set comprises 55 hits (48 up and 7 down) and 991 no-effect genes. We do not test weak-phenotype genes in this evaluation. When a given gene is held aside, it is treated as if its phenotype has the unobserved label, meaning that the inference process is used to predict whether or not the gene is relevant, and, if it is predicted to be relevant, its phenotype label. If the test case is included in the set of literature-curated interactions, then all interactions that involve the test case are held aside as well. We also recalculate the diffusion kernel scores for the entire network for each held-aside test case. To predict the label of a held-aside node, we use our integer programming approach to infer an ensemble of subnetworks. An individual subnetwork may include the held-aside gene and provide a predicted up or down phenotype for it, or it may exclude the gene. We assess our confidence in whether the gene is a hit or not by determining the fraction of subnetworks in which it is predicted to have an up or down phenotype. When this fraction is the same for a set of cases, the node scores computed by the kernel are used as a secondary measure of confidence. By varying a threshold on these confidence values, we can plot a precision-recall curve characterizing the predictive accuracy of our method. Recall is defined as the fraction of true hits in the test set that are predicted to be hits, and precision is defined as the fraction of predicted hits that are truly hits. In this context, we consider precision to be the more important of the two measures, as it is better to to avoid devoting follow-up experiments to false positives. As discussed in the Related Work section, several integer programming methods have been developed to infer signalling and regulatory networks from experimental data that comes in the form of source-target pairs. A key aspect of our approach is that it does not assume that targets are given. Instead, it infers the downstream interfaces. Existing IP approaches are therefore not directly applicable to our own task. However, we consider some components of existing methods that can be substituted into our integer program: namely, two alternative objective functions, and one alternative heuristic for inferring edge signs. Additionally, in this section, we explore the effect of varying some of the previously discussed parameters and constraints of our IP. One motivation for our inference approach is to make predictions about which unassayed host factors may be involved in viral replication. A number of host factors were unable to be assayed using the deletion or doxycycline-repressible mutant libraries, either because the mutant was not part of the library or did not grow under experimental conditions. As these factors cannot be assayed using high-throughput screens, there is a need to identify a high-confidence subset of them for further, lower-throughput experimentation. Toward this end, we use our approach to make predictions about host factors that were not assayed (or not successfully assayed) in the genome-wide BMV screens [1], [4]. We collect an ensemble of 100 inferred subnetworks using all available phenotype data and allowing the use of 97 interfaces. We choose this number of interfaces because it is in the middle of the range tested in our cross-validation experiments, the results of which suggest that prediction accuracy is not significantly affected by a larger number of interfaces. We also seed the network with the literature-curated edges described in the Data section. Out of 1,821 unassayed host factors in the background network, 221 are predicted to be relevant by any of the 100 inferred subnetworks in the ensemble, and 189 receive confidence. Of these, 124 represent ORFs (about 9% of unassayed ORFs/putative ORFs), and 65 represent protein complexes (about 14% of represented protein complexes). Here we discuss independent evidence supporting a selection of these predictions. In numerous cases, the predicted hits include members of pathways of protein complexes known to be involved in BMV replication. In these cases, the inferred subnetworks correctly expanded the relevant complexes with other known components or functional partners that were absent from the given hit sets for technical reasons, such as non-viability of the relevant mutant strain. One example is the inferred inclusion of previously un-implicated components of the cellular ubiquitin-proteasome system, such as the 20S proteasome and components of the 19S regulator complex. While some experimental and literature-curated hits are associated with the proteasome, the predicted hits contribute several more proteasomal proteins. Recent additional experiments, including inhibitor studies and other approaches, have confirmed the involvement of the 20S proteasome, the 19S regulator and other factors in this system in multiple aspects of BMV RNA replication (B. G. and P. A. , unpublished results). Even more important biological validation of our results emerged from additional experimental studies. For example, our ensemble predicts the involvement of Snf7p and Vps4p, both at 0. 99 confidence. These are proteins in the ESCRT pathway, which is involved in membrane bending and scission events in cell division, cell surface receptor down-regulation and other processes [53]. Recent studies initiated independently of the work reported here have confirmed the predicted role of ESCRT pathway, and of Snf7p and Vps4p in particular, in facilitating BMV RNA replication (A. Diaz, X. Wang and P. Ahlquist, manuscript in preparation). The predicted relevant interactions involving Snf7p and Vps4p are shown in Figure 8. A further example is provided by the inferred involvement of Xrn1p, a protein involved in RNA degradation. An independent study confirmed the strong impact of the gene XRN1 on BMV replication by showing that a BMV mutant defective in modifying BMV RNA' s by the addition of a 5' cap could not accumulate RNA in wild type yeast but did so in an xrn1 deletion strain [54]. The subnetworks inferred using our method can be used to predict which host factors are closest to a direct interaction with the virus. For this evaluation, we predict a set of high-confidence host interfaces for BMV. The ability of our methods to predict physical interfaces between host protein networks and viral components is constrained by the limits of current background knowledge, as specifically represented by the input background network of interacting host proteins. Because of such external limitations, some predicted interfaces may not represent actual host-virus interfaces, but instead approximate the host component that would most likely connect with an actual interface if the relevant subnetwork were extended to include currently unrecognized interaction partners. We consider support from domain knowledge that the predicted interfaces are plausibly close to a direct interaction with a viral component. To predict high-confidence interfaces, we infer an ensemble of 100 subnetworks for BMV-yeast interactions, applying the global constraint that only the minimum possible number of interfaces can be used (that is, the smallest number of interfaces such that the IP remains feasible; in this case, 47). We also seed the network with the literature-curated edges described previously, which include four interfaces. Over the entire ensemble, the total number of interfaces used by at least one subnetwork is 51. We designate as “high-confidence” those interfaces that (i) account for more than one hit (other than themselves), (ii) have greater than 0. 75 confidence, and, (iii) are predicted to be an interface with an average of at least 0. 75 confidence across all of the leave-one-out ensembles inferred using a minimum number of interfaces. Our method predicts 14 novel high-confidence yeast interfaces for BMV, as shown in Table 6. We assessed these high-confidence interfaces for plausibility based on their annotated function in the Saccharomyces Genome Database [55]. The value of our subnetwork inference method is supported by the observation that several of the predicted 14 high-confidence interfaces are known interactors with BMV components and many more are closely associated with known interactors. Below we discuss available information on several classes of these predicted interfaces. One significant advantage of our approach is that it enables domain knowledge to be readily incorporated into the inferred subnetworks. Specifically, the IP can incorporate constraints that represent knowledge about host factors and interactions that are known to be involved in viral replication, thereby influencing decisions about the rest of the subnetwork. These constraints were shown in the Computational Methods section. Here, we consider the effect of seeding the subnetworks with interactions from specific host pathways that are known to be involved in BMV replication. This set of domain knowledge, which we have elicited from the relevant literature, comprises 28 interactions among 24 host factors. It also specifies several host factors that should be treated as interfaces. For comparison, we also infer BMV subnetwork ensembles that do not use the literature-curated interactions. Seeding the subnetwork with these interactions does not have any apparent effect on hit-prediction accuracy, as we discussed earlier in the Results section. However, the interactions do appear to have an influence on their local neighborhoods. In examining the 97-interface BMV subnetwork ensemble, we observe a small number of cases in which the supplied interactions and interfaces serve to provide “anchors” that allow us to explain other, related hits. One set of edges extracted from the literature connects the ubiquitin-proteasome pathway to membrane synthesis, and specifies that Ole1p is an interface to BMV. The inferred subnetwork identifies a connection between Ole1p, a fatty acid desaturase, and Acb1p, which is involved in transporting newly synthesized fatty acids; the relevant portion of the subnetwork is shown in Figure 9. The connection between the ubiquitin-proteasome pathway and Acb1p was not identified in any subnetwork inferred without the provided literature-based interactions. Furthermore, Ole1p is not inferred to be relevant at all without the provided interactions. Another component from the literature specifies the chaperone protein Ydj1p is an interface. The inferred subnetwork, shown in Figure 10, identifies upstream connections from the hits Hsf1p and Ure2p to Ydj1p, which were not mentioned in the paper discussing Ydj1p' s relationship to BMV [45]. These inferred connections demonstrate that the inferred subnetwork can be used to predict relevant connections between well-understood components of the network and host factors that have not yet been studied in detail. To supplement our manual analysis of predicted hits and interfaces, we employ the Model Based Gene-Set Analysis (MGSA) tool [69] to evaluate the ability of the inferred subnetwork to better identify relevant functional categories than an analysis of the experimental hits alone. The MGSA method uses a Bayesian network to analyze the representation of all GO terms in a gene set at once. As output, it provides the marginal probability that each GO term accounts for the input gene set. We use MGSA to analyze first the experimental hits and literature-derived relevant genes for BMV that are present in the background network, and second, the experimental hits combined with the predicted hits from the 97-interface inferred subnetwork. We use a probability threshold of 0. 25 because we are willing to tolerate a degree of redundancy in the results, in exchange for the identification of a thorough list of representative GO terms. We further assess the significance of each returned GO term by comparison to the subnetworks inferred from random data. For each GO term, we generate a p-value as the proportion of random subnetworks for which MGSA gives a greater or equal probability. Table 7 presents the GO terms returned by MGSA with probability for the combined set of experimental and predicted hits. The “Experimental Hits” columns show the number of experimental hits associated with each GO term, and MGSA' s probability that the GO term explains the experimental hits alone. Similarly, the “Predicted Hits” columns show the number of additional predicted hits associated with the GO term, and MGSA' s probability that the GO term explains the combined experimental and predicted hit set. The “p-value” column shows the proportion of random subnetworks with equal or greater probability for the GO term as compared to the inferred subnetwork, with asterisks indicating. As shown in Table 8, an additional 15 GO terms are identified by MGSA for the combined hit set, but are not identified for the experimental hits alone. A number of these GO terms represent only predicted hits. Eight of the GO terms receive a from the random subnetwork analysis. This result indicates that our subnetwork inference method predicts hits that (i) are useful for amplifying weak functional signals among the experimental hits, and (ii) are among themselves functionally coherent. Several of the amplified GO terms represent protein complexes or pathways that are recognized for their role in BMV replication. Deadenylation-dependent mRNA decapping factors are also known to be relevant [44], and the perinuclear region of the cytoplasm is the cellular location in which BMV replicates [56]. Among the novel GO terms that contain no experimental hits are represented specific parts of the ubiquitin-proteasome system and ribosome synthesis, both of which we have noted are relevant to BMV replication. One advantage of our method is that we explicitly include protein complexes as nodes in our background network. We propose that doing so allows the inferred subnetworks to provide useful information about cooperative interactions between proteins. We use two Monte Carlo tests to assess the degree to which the representation of complexes among inferred subnetworks, and specifically among inferred interfaces, is due to (i) topological properties of the background network and inference procedure, independent of the experimental data, and (ii) properties of the experimental data, independent of the inference procedure. The details of these experiments are available in Text S3, with results in Tables S3-S4. Considering predicted relevant complexes in the 97-interface BMV subnetwork, 17 out of 65 predicted relevant complexes receive a p-value below 0. 05 from either Monte Carlo test. Of the high-confidence, predicted BMV-yeast interfaces that are protein complexes or are members of complexes, five out of the eight receive a p-value below 0. 05 from either test. These results indicate that the representation of many complexes by our inferred subnetworks are well-supported by predicted hits and are not likely to be artifacts of the background network or chance.
We have presented an approach that aims to elucidate how viruses exploit their host cells. Our approach uses known host intracellular interactions to infer ensembles of directed subnetworks which provide consistent explanations for phenotypes measured in genome-wide loss-of-function assays. This approach is able to represent a rich set of interaction types, in addition to domain knowledge about specific interactions that are known to be relevant. By inferring an ensemble of subnetworks, the approach is able to quantify its certainty about the relevance of various genes and interactions. The value of the subnetworks inferred by our method is that they can be used to (i) predict which unassayed genes may be involved in viral replication, (ii) interpret the role of each hit in modulating the virus, and (iii) guide further experimentation. Our empirical evaluation demonstrates that, using a gene-prioritization method as a sub-component, our method is able to predict phenotypes for unassayed genes with accuracy that is comparable to the gene-prioritization method alone. We also used our method to predict host-virus interfaces and additional relevant host genes for Brome Mosaic Virus, and performed a literature-based analysis of the predicted relevant host factors. While additional experimentation is necessary to confirm our predictions, a number of them are supported by domain knowledge. Among the predicted interfaces, many are known to bind or modify RNA, localize to the site of viral replication, or act in processes that have been previously identified as involved in viral replication. Similarly, many predicted hits are members of known relevant complexes, and a few are supported by independent experiments. These results are also supported by a Gene Ontology analysis which showed that our inferred subnetworks identify more relevant functional categories than the experimental data alone. Our experiments also demonstrated that the predictions made by our inferred networks have high levels of stability given small changes to the input data. There are a number of promising directions in which we plan to extend this work. Among them are applying the method to RNAi studies in more complex host networks and incorporating literature-extracted interactions into the background network. Our supplementary website is located at http: //www. biostat. wisc. edu/~craven/chasman_host_virus/. There we provide integer program code and data in the GAMS language, and visualizations of the background network and inferred BMV subnetworks as Cytoscape [70] files.
Nearly every step of the viral life cycle requires the action or use of host machinery. Genome-wide suppression experiments have been used to identify individual host genes whose products are involved in viral replication. The hit sets identified by such experiments are typically fairly large and difficult to comprehend. We propose a method to infer subnetworks of intracellular interactions that explain the experimental data. These inferred subnetworks make the data more interpretable in terms of the mechanisms of viral replication and can be used to guide further experiments.
systems biology
computer and information sciences
mathematical computing
medicine and health sciences
pathology and laboratory medicine
host-pathogen interactions
virology
biology and life sciences
computing methods
microbiology
computational biology
pathogenesis
computer inferencing
Inferring Host Gene Subnetworks Involved in Viral Replication