Identification of key player genes in gene regulatory networks

Maryam Nazarieh, Andreas Wiese, Thorsten Will, Mohamed Hamed, Volkhard Helms

Research output: Contribution to journalArticlepeer-review

30 Scopus citations


Background: Identifying the gene regulatory networks governing the workings and identity of cells is one of the main challenges in understanding processes such as cellular differentiation, reprogramming or cancerogenesis. One particular challenge is to identify the main drivers and master regulatory genes that control such cell fate transitions. In this work, we reformulate this problem as the optimization problems of computing a Minimum Dominating Set and a Minimum Connected Dominating Set for directed graphs. Results: Both MDS and MCDS are applied to the well-studied gene regulatory networks of the model organisms E. coli and S. cerevisiae and to a pluripotency network for mouse embryonic stem cells. The results show that MCDS can capture most of the known key player genes identified so far in the model organisms. Moreover, this method suggests an additional small set of transcription factors as novel key players for governing the cell-specific gene regulatory network which can also be investigated with regard to diseases. To this aim, we investigated the ability of MCDS to define key drivers in breast cancer. The method identified many known drug targets as members of the MDS and MCDS. Conclusions: This paper proposes a new method to identify key player genes in gene regulatory networks. The Java implementation of the heuristic algorithm explained in this paper is available as a Cytoscape plugin at The SageMath programs for solving integer linear programming formulations used in the paper are available at and as supplementary material.

Original languageEnglish
Article number88
JournalBMC Systems Biology
Issue number1
StatePublished - 6 Sep 2016
Externally publishedYes


  • Gene regulatory network
  • Heuristic algorithm
  • Integer linear programming
  • Minimum connected dominating set
  • Minimum dominating set


Dive into the research topics of 'Identification of key player genes in gene regulatory networks'. Together they form a unique fingerprint.

Cite this