Identifying gene regulatory networks from experimental data

This paper studies a gene regulatory network model where a gene is activated or inhibited by other genes. To identify the complicated structure of these networks, we propose a methodology for analyzing large, multiple time-series data sets arising in expression analysis, and evaluate it both theoretically and through a case study. We first build a graph representing all putative activation/inhibition relationships between all pairs of genes, and then prune this graph by solving a combinatorial optimization problem to identify a small set of interesting candidate regulatory elements. We implemented this method and applied it into a real data set. For this particular model, we present several algorithmic and complexity results for the maximum gene regulation problem to identify the smallest set of genes that regulate all genes.