skip to main content


Title: Graph Theoretic and Pearson Correlation-Based Discovery of Network Biomarkers for Cancer
Two graph theoretic concepts—clique and bipartite graphs—are explored to identify the network biomarkers for cancer at the gene network level. The rationale is that a group of genes work together by forming a cluster or a clique-like structures to initiate a cancer. After initiation, the disease signal goes to the next group of genes related to the second stage of a cancer, which can be represented as a bipartite graph. In other words, bipartite graphs represent the cross-talk among the genes between two disease stages. To prove this hypothesis, gene expression values for three cancers— breast invasive carcinoma (BRCA), colorectal adenocarcinoma (COAD) and glioblastoma multiforme (GBM)—are used for analysis. First, a co-expression gene network is generated with highly correlated gene pairs with a Pearson correlation coefficient ≥ 0.9. Second, clique structures of all sizes are isolated from the co-expression network. Then combining these cliques, three different biomarker modules are developed—maximal clique-like modules, 2-clique-1-bipartite modules, and 3-clique-2-bipartite modules. The list of biomarker genes discovered from these network modules are validated as the essential genes for causing a cancer in terms of network properties and survival analysis. This list of biomarker genes will help biologists to design wet lab experiments for further elucidating the complex mechanism of cancer.  more » « less
Award ID(s):
1901628
NSF-PAR ID:
10141527
Author(s) / Creator(s):
; ; ; ;
Date Published:
Journal Name:
Data
Volume:
4
Issue:
2
ISSN:
2306-5729
Page Range / eLocation ID:
81
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Alzheimer’s disease (AD) and Parkinson’s disease (PD) are the most common neurodegenerative disorders related to aging. Though several risk factors are shared between these two diseases, the exact relationship between them is still unknown. In this paper, we analyzed how these two diseases relate to each other from the genomic, epigenomic, and transcriptomic viewpoints. Using an extensive literature mining, we first accumulated the list of genes from major genome-wide association (GWAS) studies. Based on these GWAS studies, we observed that only one gene (HLA-DRB5) was shared between AD and PD. A subsequent literature search identified a few other genes involved in these two diseases, among which SIRT1 seemed to be the most prominent one. While we listed all the miRNAs that have been previously reported for AD and PD separately, we found only 15 different miRNAs that were reported in both diseases. In order to get better insights, we predicted the gene co-expression network for both AD and PD using network analysis algorithms applied to two GEO datasets. The network analysis revealed six clusters of genes related to AD and four clusters of genes related to PD; however, there was very low functional similarity between these clusters, pointing to insignificant similarity between AD and PD even at the level of affected biological processes. Finally, we postulated the putative epigenetic regulator modules that are common to AD and PD. 
    more » « less
  2. We consider how to generate graphs of arbitrary size whose chromatic numbers can be chosen (or are well-bounded) for testing graph coloring algorithms on parallel computers. For the distance-1 graph coloring problem, we identify three classes of graphs with this property. The first is the Erdős-Rényi random graph with prescribed expected degree, where the chromatic number is known with high probability. It is also known that the Greedy algorithm colors this graph using at most twice the number of colors as the chromatic number. The second is a random geometric graph embedded in hyperbolic space where the size of the maximum clique provides a tight lower bound on the chromatic number. The third is a deterministic graph described by Mycielski, where the graph is recursively constructed such that its chromatic number is known and increases with graph size, although the size of the maximum clique remains two. For Jacobian estimation, we bound the distance-2 chromatic number of random bipartite graphs by considering its equivalence to distance-1 coloring of an intersection graph. We use a “balls and bins” probabilistic analysis to establish a lower bound and an upper bound on the distance-2 chromatic number. The regimes of graph sizes and probabilities that we consider are chosen to suit the Jacobian estimation problem, where the number of columns and rows are asymptotically nearly equal, and have number of nonzeros linearly related to the number of columns. Computationally we verify the theoretical predictions and show that the graphs are often be colored optimally by the serial and parallel Greedy algorithms. 
    more » « less
  3. Abstract Background Given a collection of coexpression networks over a set of genes, identifying subnetworks that appear frequently is an important research problem known as mining frequent subgraphs. Maximal frequent subgraphs are a representative set of frequent subgraphs; A frequent subgraph is maximal if it does not have a super-graph that is frequent. In the bioinformatics discipline, methodologies for mining frequent and/or maximal frequent subgraphs can be used to discover interesting network motifs that elucidate complex interactions among genes, reflected through the edges of the frequent subnetworks. Further study of frequent coexpression subnetworks enhances the discovery of biological modules and biological signatures for gene expression and disease classification. Results We propose a reverse search algorithm, called RASMA, for mining frequent and maximal frequent subgraphs in a given collection of graphs. A key innovation in RASMA is a connected subgraph enumerator that uses a reverse-search strategy to enumerate connected subgraphs of an undirected graph. Using this enumeration strategy, RASMA obtains all maximal frequent subgraphs very efficiently. To overcome the computationally prohibitive task of enumerating all frequent subgraphs while mining for the maximal frequent subgraphs, RASMA employs several pruning strategies that substantially improve its overall runtime performance. Experimental results show that on large gene coexpression networks, the proposed algorithm efficiently mines biologically relevant maximal frequent subgraphs. Conclusion Extracting recurrent gene coexpression subnetworks from multiple gene expression experiments enables the discovery of functional modules and subnetwork biomarkers. We have proposed a reverse search algorithm for mining maximal frequent subnetworks. Enrichment analysis of the extracted maximal frequent subnetworks reveals that subnetworks that are frequent are highly enriched with known biological ontologies. 
    more » « less
  4. Nitrogen (N) and Water (W) - two resources critical for crop productivity – are becoming increasingly limited in soils globally. To address this issue, we aim to uncover the gene regulatory networks (GRNs) that regulate nitrogen use efficiency (NUE) - as a function of water availability - in Oryza sativa, a staple for 3.5 billion people. In this study, we infer and validate GRNs that correlate with rice NUE phenotypes affected by N-by-W availability in the field. We did this by exploiting RNA-seq and crop phenotype data from 19 rice varieties grown in a 2x2 N-by-W matrix in the field. First, to identify gene-to-NUE field phenotypes, we analyzed these datasets using weighted gene co-expression network analysis (WGCNA). This identified two network modules ("skyblue" & "grey60") highly correlated with NUE grain yield (NUEg). Next, we focused on 90 TFs contained in these two NUEg modules and predicted their genome-wide targets using the N-and/or-W response datasets using a random forest network inference approach (GENIE3). Next, to validate the GENIE3 TF→target gene predictions, we performed Precision/Recall Analysis (AUPR) using nine datasets for three TFs validated in planta . This analysis sets a precision threshold of 0.31, used to "prune" the GENIE3 network for high-confidence TF→target gene edges, comprising 88 TFs and 5,716 N-and/or-W response genes. Next, we ranked these 88 TFs based on their significant influence on NUEg target genes responsive to N and/or W signaling. This resulted in a list of 18 prioritized TFs that regulate 551 NUEg target genes responsive to N and/or W signals. We validated the direct regulated targets of two of these candidate NUEg TFs in a plant cell-based TF assay called TARGET, for which we also had in planta data for comparison. Gene ontology analysis revealed that 6/18 NUEg TFs - OsbZIP23 (LOC_Os02g52780), Oshox22 (LOC_Os04g45810), LOB39 (LOC_Os03g41330), Oshox13 (LOC_Os03g08960), LOC_Os11g38870, and LOC_Os06g14670 - regulate genes annotated for N and/or W signaling. Our results show that OsbZIP23 and Oshox22, known regulators of drought tolerance, also coordinate W-responses with NUEg. This validated network can aid in developing/breeding rice with improved yield on marginal, low N-input, drought-prone soils. 
    more » « less
  5. Background

    Gene co‐expression and differential co‐expression analysis has been increasingly used to study co‐functional and co‐regulatory biological mechanisms from large scale transcriptomics data sets.

    Methods

    In this study, we develop a nonparametric approach to identify hub genes and modules in a large co‐expression network with low computational and memory cost, namely MRHCA.

    Results

    We have applied the method to simulated transcriptomics data sets and demonstrated MRHCA can accurately identify hub genes and estimate size of co‐expression modules. With applying MRHCA and differential co‐expression analysis toE. coliand TCGA cancer data, we have identified significant condition specific activated genes inE. coliand distinct gene expression regulatory mechanisms between the cancer types with high copy number variation and small somatic mutations.

    Conclusion

    Our analysis has demonstrated MRHCA can (i) deal with large association networks, (ii) rigorously assess statistical significance for hubs and module sizes, (iii) identify co‐expression modules with low associations, (iv) detect small and significant modules, and (v) allow genes to be present in more than one modules, compared with existing methods.

     
    more » « less