Dense subgraph computation via stochastic search: application to detect transcriptional modules.
BACKGROUND
In a tri-partite biological network of transcription factors, their putative target genes, and the tissues in which the target genes are differentially expressed, a tightly inter-connected (dense) subgraph may reveal knowledge about tissue specific transcription regulation mediated by a specific set of transcription factors-a tissue-specific transcriptional module. This is just one context in which an efficient computation of dense subgraphs in a multi-partite graph is needed.


RESULTS
Here we report a generic stochastic search based method to compute dense subgraphs in a graph with an arbitrary number of partitions and an arbitrary connectivity among the partitions. We then use the tool to explore tissue-specific transcriptional regulation in the human genome. We validate our findings in Skeletal muscle based on literature. We could accurately deduce biological processes for transcription factors via the tri-partite clusters of transcription factors, genes, and the functional annotation of genes. Additionally, we propose a few previously unknown TF-pathway associations and tissue-specific roles for certain pathways. Finally, our combined analysis of Cardiac, Skeletal, and Smooth muscle data recapitulates the evolutionary relationship among the three tissues.
Everett
Logan
L
Penn Center for Bioinformatics, University of Pennsylvania, Philadelphia, PA 19104, USA.
Wang
Li-San
LS
Hannenhalli
Sridhar
S
D000465:Algorithms; D001185:Artificial Intelligence; D001483:Base Sequence; D003198:Computer Simulation; D008957:Models, Genetic; D008969:Molecular Sequence Data; D005810:Multigene Family / Q000235:genetics*; D010363:Pattern Recognition, Automated / Q000379:methods; D017422:Sequence Analysis, DNA / Q000379:methods*; D015398:Signal Transduction / Q000235:genetics*; D013269:Stochastic Processes; D014157:Transcription Factors / Q000235:genetics*; D014158:Transcription, Genetic / Q000235:genetics*
D014157:Transcription Factors