Differential analysis of biological networks

Da Ruan, Alastair Young, Giovanni Montana

Abstract

In cancer research, the comparison of gene expression or DNA methylation networks inferred from healthy controls and patients can lead to the discovery of biological pathways associated to the disease. As a cancer progresses, its signalling and control networks are subject to some degree of localised re-wiring. Being able to detect disrupted interaction patterns induced by the presence or progression of the disease can lead to the discovery of novel molecular diagnostic and prognostic signatures. Currently there is a lack of scalable statistical procedures for two-network comparisons aimed at detecting localised topological differences. We propose the dGHD algorithm, a methodology for detecting differential interaction patterns in two-network comparisons. The algorithm relies on a statistic, the Generalised Hamming Distance (GHD), for assessing the degree of topological difference between networks and evaluating its statistical significance. dGHD builds on a non-parametric permutation testing framework but achieves computationally efficiency through an asymptotic normal approximation. We show that the GHD is able to detect more subtle topological differences compared to a standard Hamming distance between networks. This results in the dGHD algorithm achieving high performance in simulation studies as measured by sensitivity and specificity. An application to the problem of detecting differential DNA co-methylation subnetworks associated to ovarian cancer demonstrates the potential benefits of the proposed methodology for discovering network-derived biomarkers associated with a trait of interest.

Introduction

Traditional cancer research often focuses on "differential expression," identifying individual genes that exhibit varying activity levels between healthy and diseased states. However, biological processes are governed by complex networks of interactions. Disease progression frequently involves the "re-wiring" of these networks—changes in how genes regulate or co-vary with one another—even when average activity levels remain stable.

Detecting these localized topological changes presents significant mathematical and computational challenges. Standard metrics, such as the Hamming Distance, are often too blunt, operating on a binary "all-or-nothing" basis regarding edge existence. Furthermore, establishing statistical significance typically requires exhaustive permutation testing, which is computationally prohibitive for large-scale genomic datasets. This paper introduces the dGHD algorithm, a scalable solution designed to pinpoint these subtle structural shifts.

Methodology

The dGHD algorithm incorporates two primary innovations to overcome the limitations of existing network comparison tools: the Generalised Hamming Distance (GHD) and an asymptotic normal approximation for statistical testing.

Generalised Hamming Distance (GHD)

Unlike the standard Hamming Distance, which only considers whether an edge is present or absent, the GHD incorporates Topological Overlap (TO). This measure evaluates the "neighborhood" of a node pair. If two genes share many common partners in one network but few in another, the GHD flags this as a significant structural change. This approach allows the metric to capture the functional context of a connection rather than just its binary state.

Illustration of HD and GHD. While the standard Hamming Distance (HD) remains constant across variations (b), (c), and (d), the Generalised Hamming Distance (GHD) increases as the topological significance of the re-wiring grows.

Asymptotic Normal Approximation

To determine if a network difference is statistically significant, researchers traditionally rely on shuffling data thousands of times (permutation testing). The authors mathematically demonstrate that for common biological network models (e.g., Scale-Free), the distribution of these permutations follows a Normal (Gaussian) distribution. By deriving the mean and variance of the GHD distribution analytically, the dGHD algorithm can calculate p-values nearly instantaneously, bypassing the "computational wall" of traditional simulations.

The dGHD Algorithm

The algorithm employs an iterative "pruning" process. It begins with a large network and systematically removes nodes that do not contribute to the overall topological difference. This process continues until it isolates a statistically significant "differential subnetwork."

Experimental Validation

Simulation Studies

The algorithm was tested using Random Geometric (RG) and Scale-Free (SF) networks. In these controlled environments, GHD consistently outperformed standard Hamming Distance and other competing tests (such as QAP and CUG), maintaining high sensitivity and specificity even at low noise thresholds. In simulations with 1,000 nodes, the algorithm successfully isolated planted differential subnetworks of 200 nodes.

Ovarian Cancer Application

The researchers applied dGHD to a DNA co-methylation dataset (GSE19711) involving 27,578 CpG islands from 540 women. The algorithm identified a differential subnetwork of 1,642 nodes. Within this subnetwork, six distinct gene communities were discovered. Notably, one community (C5) was heavily enriched with Interleukin-3 (IL-3) signaling pathways, which are linked to tumor suppression and chemotherapy response. Many genes in this subnetwork would have been missed by standard univariate tests because their average methylation levels remained unchanged.

Conclusion and Future Work

The dGHD algorithm provides a powerful, scalable framework for identifying localized re-wiring in biological networks. By leveraging topological overlap and mathematical approximations, it offers a significant improvement in sensitivity and speed over traditional methods.

Future developments may include extending the framework to multi-sample comparisons (e.g., across multiple disease stages) and refining the algorithm to strictly enforce connectivity within the identified subnetworks. While the current model assumes asymptotic normality—a condition met by most biological networks—further validation may be required for more irregular network structures.

Summary updated

Abstract

In cancer research, the comparison of gene expression or DNA methylation networks inferred from healthy controls and patients can lead to the discovery of biological pathways associated to the disease. As a cancer progresses, its signalling and control networks are subject to some degree of localised re-wiring. Being able to detect disrupted interaction patterns induced by the presence or progression of the disease can lead to the discovery of novel molecular diagnostic and prognostic signatures. Currently there is a lack of scalable statistical procedures for two-network comparisons aimed at detecting localised topological differences. We propose the dGHD algorithm, a methodology for detecting differential interaction patterns in two-network comparisons. The algorithm relies on a statistic, the Generalised Hamming Distance (GHD), for assessing the degree of topological difference between networks and evaluating its statistical significance. dGHD builds on a non-parametric permutation testing framework but achieves computationally efficiency through an asymptotic normal approximation. We show that the GHD is able to detect more subtle topological differences compared to a standard Hamming distance between networks. This results in the dGHD algorithm achieving high performance in simulation studies as measured by sensitivity and specificity. An application to the problem of detecting differential DNA co-methylation subnetworks associated to ovarian cancer demonstrates the potential benefits of the proposed methodology for discovering network-derived biomarkers associated with a trait of interest.
BibTeX
@article{ruan2015differential,
  author = {Da Ruan and Alastair Young and Giovanni Montana},
  title = {{Differential analysis of biological networks}},
  journal = {BMC Bioinformatics},
  year = {2015},
  doi = {10.1186/s12859-015-0735-5},
}
Figure