Subnetwork state functions define dysregulated subnetworks in cancer

Abstract

Emerging research demonstrates the potential of protein-protein interaction (PPI) networks in uncovering the mechanistic bases of cancers, through identification of interacting proteins that are coordinately dysregulated in tumorigenic and metastatic samples. When used as features for classification, such coordinately dysregulated subnetworks improve diagnosis and prognosis of cancer considerably over single-gene markers. However, existing methods formulate coordination between multiple genes through additive representation of their expression profiles and utilize fast heuristics to identify dysregulated subnetworks, which may not be well suited to the potentially combinatorial nature of coordinate dysregulation. Here, we propose a combinatorial formulation of coordinate dysregulation and decompose the resulting objective function to cast the problem as one of identifying subnetwork state functions that are indicative of phenotype. Based on this formulation, we show that coordinate dysregulation of larger subnetworks can be bounded using simple statistics on smaller subnetworks. We then use these bounds to devise an efficient algorithm, Crane, that can search the subnetwork space more effectively than existing algorithms. Comprehensive cross-classification experiments show that subnetworks identified by Crane outperform those identified by additive algorithms in predicting metastasis of colorectal cancer (CRC).

FIG. 1.

Additive versus combinatorial coordinate dysregulation. Genes (g) are shown as nodes; interactions between their products are shown as edges. Expression profiles (E) of genes are shown by colormaps. Dark red indicates high expression (H); light green indicates low expression (L). None of the genes can differentiate phenotype and control samples individually. Aggregate subnetwork activity (average expression) for each subnetwork is shown in the row below its gene expression matrix. The aggregate activity of can perfectly discriminate phenotype and control, but the aggregate activity of cannot discriminate at all. For each subnetwork and , each column of the gene expression matrix specifies the subnetwork state in the corresponding sample. The states of both subnetworks can perfectly discriminate phenotype and control (for , up-regulation of g₇ alone or g₅ and g₆ together indicates phenotype; we say state functions LLH and HHL are indicative of phenotype).

FIG. 2.

Neural network model used to utilize subnetworks identified by Crane for classification. Each subnetwork is represented by an input layer neuron, and these neurons are connected to a single output layer neuron.

FIG. 3.

Classification performance of subnetworks identified by Crane in predicting colon cancer metastasis, as compared to single gene markers and subnetworks identified by algorithms that aim to maximize additive coordinate dysregulation. Subnetworks identified by Crane are used to train neural networks (NNs), while those identified by the additive algorithm are used to train NNs, as well as support vector machines (SVMs). In the graphs, horizontal axes show the number of disjoint subnetwork features (with maximum combinatorial or additive coordinate dysregulation) used in classification, and vertical axes show the precision and recall achieved by the classifier.

FIG. 4.

Comparison of the runtimes of Crane and its version that does not prune the subnetwork search space using the theoretical bound on J(.). Note that Crane identifies all subnetworks that are identified by the algorithm without pruning.

FIG. 5.

The effect of parameters on the classification performance of subnetworks discovered by Crane. For all experiments, subnetworks are discovered on GSE3964 and tested on samples of GSE6988. The F-measure of a classifier is computed by increasing the number of subnetworks gradually from 1 to 10 and average F-Measure in these experiments is reported. (A–D) Performance of Crane with respect to parameters d, b, j**, and α, respectively. (A) b = 10, and j** = 0.15. (B) d = 3, and j** = 0.15. (C) b = 10, and d = 3. (D) b = 10, j** = 0.15, and d = 3.

FIG. 6.

Hypothesis-driver subnetwork: interaction diagram illustrating key interactions with gene products from a subnetwork identified by Crane as indicative of CRC metastasis. Shown are the gene products in discovered subnetwork (red circles) and their direct interactions with other proteins. Green lines represent an activating interaction; red lines indicate an inhibitory interaction. Arrows indicate direction of interaction. (Inset) Expression pattern of subnetwork proteins at the level of mRNA.