Key Pathway Miner

Key Pathway Miner extracts maximal connected sub-networks from biological pathway and network data by integrating gene expression data from omics technologies such as microarrays to identify regions enriched for differential expression and to infer gene interaction and regulatory mechanisms.

Key Features:

• Subnetwork Extraction: Identifies maximal connected sub-networks that contain genes exhibiting differential expression across cases.
• Data Integration: Integrates gene expression data from omics technologies, including microarrays, with biological pathway and network data.
• Parameterized Control: Uses parameters K and L to control the number of outlier genes not dysregulated in certain cases within extracted sub-networks.
• Model Variations: Implements INES (Integrated Network Extraction Strategy) and GLONE (Graph-based Localized Network Exploration) models, both formulated as NP-Hard optimization problems.
• Heuristic Algorithm: Applies a heuristic based on Ant Colony Optimization to approximate solutions for the NP-Hard extraction problems.

Scientific Applications:

• Systems biology: Locating connected regions of coordinated differential expression to elucidate gene interactions and regulatory mechanisms.
• Disease mechanism analysis: Identifying subnetworks associated with cellular processes and disease-related expression changes.
• Condition-specific subnetwork detection: Comparing cases and controls while permitting outliers via the K and L parameters to find condition-specific modules.

Methodology:

Integrates gene expression and network data; formulates extraction as NP-Hard optimization under the INES and GLONE models controlled by parameters K and L; approximates solutions using an Ant Colony Optimization heuristic; evaluated using datasets from Ulitsky et al. 2008.