Significant Subgraph Detection in Multi-omics Networks for Disease Pathway Identification

Abstract

Chronic obstructive pulmonary disease (COPD) is one of the leading causes of death in the United States. COPD represents one of many areas of research where identifying complex pathways and networks of interacting biomarkers is an important avenue toward studying disease progression and potentially discovering cures. Recently, sparse multiple canonical correlation network analysis (SmCCNet) was developed to identify complex relationships between omics associated with a disease phenotype, such as lung function. SmCCNet uses two sets of omics datasets and an associated output phenotypes to generate a multi-omics graph, which can then be used to explore relationships between omics in the context of a disease. Detecting significant subgraphs within this multi-omics network, i.e., subgraphs which exhibit high correlation to a disease phenotype and high inter-connectivity, can help clinicians identify complex biological relationships involved in disease progression. The current approach to identifying significant subgraphs relies on hierarchical clustering, which can be used to inform clinicians about important pathways involved in the disease or phenotype of interest. The reliance on a hierarchical clustering approach can hinder subgraph quality by biasing toward finding more compact subgraphs and removing larger significant subgraphs. This study aims to introduce new significant subgraph detection techniques. In particular, we introduce two subgraph detection methods, dubbed Correlated PageRank and Correlated Louvain, by extending the Personalized PageRank Clustering and Louvain algorithms, as well as a hybrid approach combining the two proposed methods, and compare them to the hierarchical method currently in use. The proposed methods show significant improvement in the quality of the subgraphs produced when compared to the current state of the art.

Keywords: Louvain; PageRank; graph clustering; multi-omics graph; subgraph detection.

Figure 1

Hybrid clustering procedure. The first iteration (1) uses the global graph provided by SmCCNet, with subsequent iterations (2+) using the cluster generated by PageRank in its place.

Figure 2

Graph comparison between (A) two sample graphs, G₁ (left) and G₂ (right); (B) shows the heatmap visualization of the edit distances between G₁ and G₂, with the green regions representing similarity between he graphs and gray regions representing differences; the ration between the regions visually represents how similar the two graphs are.

Figure 3

Correlated PageRank results: (A) shows the randomized search results for the sequential approach to Correlated PageRank; (B) shows a distribution of |ρ| for subgraphs identified by sequential Correlated PageRank with randomized seed selection; (C) shows randomized search results for the simultaneous approach to Correlated PageRank; (D) shows a distribution of |ρ| for subgraphs identified by simultaneous Correlated PageRank with randomized seed selection; (E) shows randomized search results for simultaneous Correlated PageRank with selected strong seeds only; (F) shows a distribution of |ρ| for simultaneous Correlated PageRank with strong seeds.

Figure 4

Correlated Louvain results: (A) shows a distribution of |ρ| produced by the Correlated Louvain method with k₄ = 0.8; (B) shows the same distribution but with singleton clusters removed, only showing subgraphs with |V| ≥ 2.

Figure 5

Level effect of Correlated Louvain: (A) shows the intermediate clustering of cluster 21 with k₄ = 0.8, representing the common behavior of intermediate clusters; (B) shows uncommon behavior or intermediate clusters, such as cluster 1 with k₄ = 0.2.

Figure 6

Change in correlation (A) and subnet size (B) of subnets produced by PageRank in each iteration.

Figure 7

Visual comparison of subnet 175 with other top subnets.