Email updates

Keep up to date with the latest news and content from Algorithms for Molecular Biology and BioMed Central.

Open Access Open Badges Research

Using graph models to find transcription factor modules: the hitting set problem and an exact algorithm

Songjian Lu* and Xinghua Lu

Author Affiliations

Department of Biomedical Informatics, University of Pittsburgh, Pittsburgh, PA 15219, USA

For all author emails, please log on.

Algorithms for Molecular Biology 2013, 8:2  doi:10.1186/1748-7188-8-2

Published: 16 January 2013


Systematically perturbing a cellular system and monitoring the effects of the perturbations on gene expression provide a powerful approach to study signal transduction in gene expression systems. A critical step of revealing a signal transduction pathway regulating gene expression is to identify transcription factors transmitting signals in the system. In this paper, we address the task of identifying modules of cooperative transcription factors based on results derived from systems-biology experiments at two levels: First, a graph algorithm is developed to identify a minimum set of co-operative TFs that covers the differentially expressed genes under each systematic perturbation. Second, using a clique-finding approach, modules of TFs that tend to consistently cooperate together under various perturbations are further identified. Our results indicate that this approach is capable of identifying many known TF modules based on the individual experiment; thus we provide a novel graph-based method of identifying context-specific and highly reused TF-modules.