Active module identification in intracellular networks using a memetic algorithm with a new binary decoding scheme

Dong Li, Zhisong Pan, Guyu Hu, Zexuan Zhu, Shan He

TL;DR

This paper introduces a novel memetic algorithm for identifying "active modules" – connected subnetworks in biological networks that exhibit significant changes under specific conditions. Their key innovation is a new binary encoding/decoding scheme that efficiently ensures module connectedness, a crucial but often overlooked aspect, leading to improved performance and accuracy compared to existing methods.

What Problem Does This Paper Address?

Biological systems are incredibly complex, with molecules interacting in intricate networks to carry out cellular functions. Understanding these networks is key to deciphering how cells respond to stimuli, develop diseases, or function normally. "Active modules" are particularly interesting because they represent groups of interacting molecules whose activity changes significantly under certain conditions, potentially revealing underlying regulatory and signaling mechanisms.

The challenge lies in computationally identifying these modules. Previous approaches often struggled with two main issues:

  1. Ensuring Connectedness: Biological modules are typically expected to be connected. However, many algorithms, especially those using simple binary encodings, could identify sets of highly "active" but disconnected nodes, which are less biologically meaningful.
  2. Search Efficiency: Standard optimization algorithms (like simulated annealing or genetic algorithms) often use generic search operators that aren't tailored for the specific problem of active module identification, leading to suboptimal speed and accuracy.

Methods

The authors propose a Memetic Algorithm (MA), which combines a global search strategy (like a genetic algorithm) with a local search mechanism. Their core contributions are:

  • Novel Binary Encoding/Decoding Scheme: Instead of traditional binary representations that can lead to disconnected modules, they introduce a scheme that explicitly ensures connectedness. This involves using a binary vector where each element indicates a node's inclusion in a module. The "decoding" step then uses a Connected Components Finding (CCF) algorithm, specifically employing Breadth-First Search (BFS), to extract only the connected subnetworks from the selected nodes. This makes the process computationally tractable and easier to implement than previous methods that relied on complex data structures like HashMaps to track connectedness.
  • Local Search Operator: They designed a local search operator that is integrated into the MA. This operator intelligently perturbs candidate solutions (modules) by adding or removing nodes, guided by the objective of improving the module's score while respecting module size constraints (minimum and maximum). This local refinement step helps the algorithm converge faster and find better solutions.
  • Module Size Constraints: To avoid overly small or large modules that might be difficult to interpret, they incorporated explicit thresholds (Nmin and Nmax) into the local search to constrain the size of the identified modules.

Datasets

The paper evaluates their proposed algorithm on:

  • Simulated Interaction Network: A network with 500 nodes and 1000 edges was used to specifically validate the module connectedness property.
  • Yeast PPI Network: A real-world protein-protein interaction (PPI) network with 329 nodes and 358 edges was used. Gene expression data from a specific perturbation (GAL80 gene deletion) was applied to this network.
  • Human PPI Network: Two large human PPI networks were used: one from BioGRID (362,775 interactions) and another from STRING (8,548,002 interactions). Gene expression data related to Th17 cell differentiation was utilized.

Key Insights and Ideas

  • Connectedness is Crucial: The paper strongly emphasizes that simply finding highly scored nodes is insufficient; the biological relevance of an "active module" hinges on its interconnectedness. Their novel decoding scheme directly addresses this.
  • Tailoring Metaheuristics: Generic metaheuristic operators can be inefficient. By designing operators (like the local search) specifically for active module identification, they achieve better performance.
  • Memetic Algorithms Offer a Sweet Spot: Combining global exploration (MA's evolutionary part) with focused local refinement (MA's local search) provides a powerful approach for complex optimization problems like this.
  • Module Size Matters for Interpretation: The inclusion of explicit size constraints is a practical step towards generating modules that are not only statistically significant but also biologically interpretable.

Key Results

  • Improved Module Quality: The proposed Memetic Algorithm (MA) consistently achieved higher module scores compared to standard Genetic Algorithms (GA) and Simulated Annealing (SA) on both simulated and real-world datasets. Statistical analysis (ANOVA and t-test) confirmed these significant improvements.
  • Faster Convergence: The MA demonstrated faster convergence to stable solutions compared to GA, as visualized by their convergence rate plots. This is attributed to the local search operator guiding the search more effectively.
  • Guaranteed Connectedness: The new encoding/decoding scheme successfully ensured that all identified modules were connected, a critical improvement over baseline methods that could produce disconnected sets of nodes. Figures 1 and 2 visually demonstrate this difference on simulated data.
  • Biological Relevance: When applied to real human PPI networks, the identified modules showed enrichment in biologically relevant pathways (e.g., Th17 cell differentiation, Fc-epsilon receptor signaling), validating the biological significance of their findings.

Limitations and Future Work

  • Network Model: The authors acknowledge that their current approach primarily deals with undirected and unweighted networks. Future work could extend their methods to handle directed and weighted networks, which are more representative of many biological systems.
  • EA Sophistication: While their MA is effective, they note that more advanced evolutionary algorithm techniques could potentially further improve efficiency, especially for very large-scale networks.
  • Edge Properties: The paper mentions that edge confidence scores and directions could influence results, suggesting that incorporating these into the model might yield even more refined insights.

Summary updated

Abstract

Active modules are connected regions in biological network which show significant changes in expression over particular conditions. The identification of such modules is important since it may reveal the regulatory and signaling mechanisms that associate with a given cellular response. In this paper, we propose a novel active module identification algorithm based on a memetic algorithm. We propose a novel encoding/decoding scheme to ensure the connectedness of the identified active modules. Based on the scheme, we also design and incorporate a local search operator into the memetic algorithm to improve its performance. The effectiveness of proposed algorithm is validated on both small and large protein interaction networks.
BibTeX
@inproceedings{li2017active,
  author = {Dong Li and Zhisong Pan and Guyu Hu and Zexuan Zhu and Shan He},
  title = {{Active module identification in intracellular networks using a memetic algorithm with a new binary decoding scheme}},
  booktitle = {BMC Genom},
  year = {2017},
  url = {https://openreview.net/forum?id=wLkWaJftYX},
}
Figure