A scalable method for discovering significant subnetworks.

Area of Science:

• Systems Biology
• Bioinformatics
• Computational Biology

Background:

• Understanding biological networks is crucial for deciphering complex organism functions.
• High-throughput experiments generate data for network topology but are prone to noise, leading to ambiguous results.
• Identifying frequently occurring subnetworks is key to resolving these ambiguities.

Purpose of the Study:

• To develop a method for finding subnetworks with the highest probability of appearing in a collection of biological networks.
• To introduce the concept of 'most probable subnetworks'.

Main Methods:

• The Significant Subnetworks (SiS) method summarizes interactions using a template network.
• SiS employs dynamic bound tightening and pruning to efficiently search for most probable subnetworks.
• It calculates lower and upper bound scores to assess the quality of potential solutions.

Main Results:

• SiS identifies subnetworks that are highly frequent in large network collections.
• Metabolic network analysis revealed greater subnetwork conservation in eukaryotes than prokaryotes.
• Human transcription regulatory networks showed a large, frequently appearing backbone subnetwork across diverse cell types.

Conclusions:

• The SiS method is highly efficient, outperforming existing methods like MULE by orders of magnitude in speed.
• SiS demonstrates scalability for large datasets and subnetworks, with runtimes from seconds to minutes.
• The identified subnetworks are biologically relevant, showing conservation and consistency across different biological contexts.