How to Reconstruct a Large Genetic Network from $n$ Gene Perturbations in Fewer than $n^2$ Easy Steps

I present an algorithm to reconstruct direct regulatory interactions in gene networks from the effects of genetic perturbations on gene activity. Genomic technology has made feasible large-scale experiments that perturb the activity of many genes and then assess the effect of each individual perturbation on all other genes in an organism. Current experimental techniques can not distinguish between direct and indirect effects of a genetic perturbation. An example of an indirect effect is a gene X encoding a protein kinase, which phosphorylates and activates a transcription factor Y, which then activates transcription of gene Z. X influences the activity of gene Y directly, whereas it influences Z indirectly. To reconstruct a genetic network means to identify, for each gene and within the limits of experimental resolution, the direct effects of a perturbed gene on other genes. One can think of this as identifying the causal structure of the network. I introduce an algorithm that performs this task for networks of arbitrary size and complexity. It is based on a graph representation of a genetic network. Algorithmic complexity in both storage and time is low, less than $O(n^2)$. In practice, the algorithm can reconstruct networks of several thousand genes in mere CPU seconds on a desktop workstation.