Dense Subgraph Computation Via Stochastic Search: Application to Detect Transcriptional Modules

TitleDense Subgraph Computation Via Stochastic Search: Application to Detect Transcriptional Modules
Publication TypeJournal Articles
Year of Publication2006
AuthorsEverett L, Wang L-S, Hannenhalli S
JournalBioinformaticsBioinformatics
Volume22
Issue14
Paginatione117-e123 - e117-e123
Date Published2006/07/15/
ISBN Number1367-4803, 1460-2059
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—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

URLhttp://bioinformatics.oxfordjournals.org/content/22/14/e117
DOI10.1093/bioinformatics/btl260