TY - JOUR T1 - Dense Subgraph Computation Via Stochastic Search: Application to Detect Transcriptional Modules JF - BioinformaticsBioinformatics Y1 - 2006 A1 - Everett,Logan A1 - Wang,Li-San A1 - Hannenhalli, Sridhar AB - Motivation: 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.Result: 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. Contact:sridharh@pcbi.upenn.edu VL - 22 SN - 1367-4803, 1460-2059 UR - http://bioinformatics.oxfordjournals.org/content/22/14/e117 CP - 14 M3 - 10.1093/bioinformatics/btl260 ER -