title: Exact reconstruction of gene regulatory networks using compressive sensing.
abstract: BACKGROUND
  We consider the problem of reconstructing a gene regulatory network structure from limited time series gene expression data, without any a priori knowledge of connectivity. We assume that the network is sparse, meaning the connectivity among genes is much less than full connectivity. We develop a method for network reconstruction based on compressive sensing, which takes advantage of the network's sparseness.
  
  
  RESULTS
  For the case in which all genes are accessible for measurement, and there is no measurement noise, we show that our method can be used to exactly reconstruct the network. For the more general problem, in which hidden genes exist and all measurements are contaminated by noise, we show that our method leads to reliable reconstruction. In both cases, coherence of the model is used to assess the ability to reconstruct the network and to design new experiments. We demonstrate that it is possible to use the coherence distribution to guide biological experiment design effectively. By collecting a more informative dataset, the proposed method helps reduce the cost of experiments. For each problem, a set of numerical examples is presented.
  
  
  CONCLUSIONS
  The method provides a guarantee on how well the inferred graph structure represents the underlying system, reveals deficiencies in the data and model, and suggests experimental directions to remedy the deficiencies.
authors.affiliation: Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, 94720, CA, USA. yhchang@berkeley.edu.
authors.forename: Young Hwan
authors.initials: YH
authors.lastname: Chang
authors.affiliation: Department of Biomedical Engineering and the Center for Spatial Systems Biomedicine, Oregon Health and Science University, Portland, OR, USA. grayjo@ohsu.edu.
authors.forename: Joe W
authors.initials: JW
authors.lastname: Gray
authors.affiliation: Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, 94720, CA, USA. tomlin@eecs.berkeley.edu.|Faculty Scientist, Life Sciences Division, Lawrence Berkeley National Laboratory, Berkeley, CA, USA. tomlin@eecs.berkeley.edu.
authors.forename: Claire J
authors.initials: CJ
authors.lastname: Tomlin
mesh_terms: D000465:Algorithms; D001943:Breast Neoplasms / Q000235:genetics*; D019295:Computational Biology / Q000379:methods*; D005260:Female; D020869:Gene Expression Profiling / Q000379:methods; D053263:Gene Regulatory Networks; D006801:Humans; D008954:Models, Biological; D015398:Signal Transduction; D013997:Time Factors