Bioinformatics Vol. 17 no. 12 2001
Pages 1183-1197
© 2001 Oxford University Press
How to reconstruct a large genetic network from n gene perturbations in fewer than n2 easy steps
University of New Mexico and The Santa Fe Institute, University of New Mexico, Department of Biology, 167A Castetter Hall, Albuquerque, NM 817131-1091, USA
Received on February 2, 2001
; revised on April 30, 2001
; accepted on May 28, 2001
Motivation: The reconstruction of genetic networks is the holy grail of functional genomics. Its core task is to identify the causal structure of a gene network, that is, to distinguish direct from indirect regulatory interactions among gene products. In other words, to reconstruct a genetic network is to identify, for each network gene, which other genes and their activity the gene influences directly. Crucial to this task are perturbations of gene activity. Genomic technology permits large-scale experiments perturbing the activity of many genes and assessing the effect of each perturbation on all other genes in a genome. However, such experiments cannot distinguish between direct and indirect effects of a genetic perturbation.
Results: I present an algorithm to reconstruct direct regulatory interactions in gene networks from the results of gene perturbation experiments. The algorithm is based on a graph representation of genetic networks and applies to networks of arbitrary size and complexity. Algorithmic complexity in both storage and time is low, less than O(n2). In practice, the algorithm can reconstruct networks of several thousand genes in mere CPU seconds on a desktop workstation.
Availability: A perl implementation of the algorithm is given in the Appendix.
Contact: wagnera{at}unm.edu
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  L. A. Cogburn, T. E. Porter, M. J. Duclos, J. Simon, S. C. Burgess, J. J. Zhu, H. H. Cheng, J. B. Dodgson, and J. Burnside Functional Genomics of the Chicken A Model Organism Poult. Sci., October 1, 2007; 86(10): 2059 - 2094. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 F. Markowetz, D. Kostka, O. G. Troyanskaya, and R. Spang Nested effects models for high-dimensional phenotyping screens Bioinformatics, July 1, 2007; 23(13): i305 - i312. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. Bansal, G. D. Gatta, and D. di Bernardo Inference of gene regulatory networks and compound mode of action from time course gene expression profiles Bioinformatics, April 1, 2006; 22(7): 815 - 822. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
F. Markowetz, J. Bloch, and R. Spang Non-transcriptional pathway features reconstructed from secondary effects of RNA interference Bioinformatics, November 1, 2005; 21(21): 4026 - 4032. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 J. H. Nadeau, L. C. Burrage, J. Restivo, Y.-H. Pao, G. Churchill, and B. D. Hoit Pleiotropy, Homeostasis, and Functional Networks Based on Assays of Cardiovascular Traits in Genetically Randomized Populations Genome Res., September 1, 2003; 13(9): 2082 - 2091. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 J. Tegner, M. K. S. Yeung, J. Hasty, and J. J. Collins Reverse engineering gene networks: Integrating genetic perturbations with dynamical modeling PNAS, May 13, 2003; 100(10): 5944 - 5949. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. Wagner Estimating Coarse Gene Network Structure from Large-Scale Gene Perturbation Data Genome Res., February 1, 2002; 12(2): 309 - 315. [Abstract] [Full Text] [PDF]
|
|