@article {38196, title = {Dense Subgraph Computation Via Stochastic Search: Application to Detect Transcriptional Modules}, journal = {BioinformaticsBioinformaticsBioinformaticsBioinformatics}, volume = {22}, year = {2006}, type = {10.1093/bioinformatics/btl260}, abstract = {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{\textemdash}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}, isbn = {1367-4803, 1460-2059}, author = {Everett, Logan and Wang, Li-San and Sridhar Hannenhalli} }