Dense subgraph computation via stochastic search: application to detect transcriptional modules

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Biological networks, particularly tri-partite graphs, are crucial for understanding gene regulation.
• Identifying dense subgraphs can uncover tissue-specific transcriptional modules.
• Efficient computation of dense subgraphs is needed in multi-partite biological networks.

Purpose of the Study:

• To develop a generic stochastic search method for computing dense subgraphs in multi-partite graphs.
• To apply this method to explore tissue-specific transcriptional regulation in the human genome.
• To identify novel transcription factor (TF)-pathway associations and tissue-specific pathway roles.

Main Methods:

• A generic stochastic search algorithm was implemented to find dense subgraphs.
• The method was applied to a tri-partite biological network comprising transcription factors, target genes, and tissue expression data.
• Findings were validated using literature data for skeletal muscle and comparative analysis across cardiac, skeletal, and smooth muscle tissues.

Main Results:

• The method successfully identified tissue-specific transcriptional modules.
• Biological processes for transcription factors were accurately deduced from tri-partite clusters.
• Several novel TF-pathway associations and tissue-specific pathway roles were proposed.
• Analysis of cardiac, skeletal, and smooth muscle data revealed evolutionary relationships among these tissues.

Conclusions:

• The developed stochastic search method is effective for discovering dense subgraphs in complex biological networks.
• This approach provides valuable insights into tissue-specific transcriptional regulation and TF-pathway interactions.
• The findings contribute to a deeper understanding of human genome function and tissue evolution.