Identification of key player genes in gene regulatory networks.
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.



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.



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 http://apps.cytoscape.org/apps/mcds . The SageMath programs for solving integer linear programming formulations used in the paper are available at https://github.com/maryamNazarieh/KeyRegulatoryGenes and as supplementary material.
Center for Bioinformatics, Saarland University, Saarbruecken, Germany.|Graduate School of Computer Science, Saarland University, Saarbruecken, Germany.
Maryam
M
Nazarieh
Max Planck Institut fuer Informatik (MPII), Saarbruecken, Germany.
Andreas
A
Wiese
Center for Bioinformatics, Saarland University, Saarbruecken, Germany.|Graduate School of Computer Science, Saarland University, Saarbruecken, Germany.
Thorsten
T
Will
Center for Bioinformatics, Saarland University, Saarbruecken, Germany.|Institute for Biostatistics and Informatics in Medicine and Ageing Research, University of Rostock, Rostock, Germany.
Mohamed
M
Hamed
Center for Bioinformatics, Saarland University, Saarbruecken, Germany. volkhard.helms@bioinformatik.uni-saarland.de.
Volkhard
0000-0002-2180-9154
V
Helms
D000818:Animals; D001943:Breast Neoplasms / Q000235:genetics; D002453:Cell Cycle / Q000235:genetics; D004926:Escherichia coli / Q000166:cytology / Q000235:genetics; D053263:Gene Regulatory Networks; D000066506:Heuristics; D006801:Humans; D051379:Mice; D012441:Saccharomyces cerevisiae / Q000166:cytology / Q000235:genetics; D012984:Software; D049490:Systems Biology / Q000379:methods*
Gene regulatory network; Heuristic algorithm; Integer linear programming; Minimum connected dominating set; Minimum dominating set