Network legos: building blocks of cellular wiring diagrams

Publicly available datasets provide detailed and large-scale information on multiple types of molecular interaction networks in a number of model organisms. The wiring diagrams composed of these interaction networks capture a static view of cellular state. An important challenge in systems biology is obtaining a dynamic perspective on these networks by integrating them with gene expression measurements taken under multiple conditions. We present a top-down computational approach to identify building blocks of molecular interaction networks by: (i) integrating gene expression measurements for a particular disease state (e.g., leukemia) or experimental condition (e.g., treatment with growth serum) with molecular interactions to reveal an active network, which is the network of interactions active in the cell in that disease state or condition; and (ii) systematically combining active networks computed for different experimental conditions using set-theoretic formulae to reveal network legos, which are modules of coherently interacting genes and gene products in the wiring diagram. We propose efficient methods to compute active networks, systematically mine candidate legos, assess the statistical significance of these candidates, arrange them in a directed acyclic graph (DAG), and exploit the structure of the DAG to identify true network legos. We describe methods to assess the stability of our computations to changes in the input and to recover active networks by composing network legos. We analyze two human datasets using our method. A comparison of three leukemias demonstrates how a biologist can use our system to identify specific differences between these diseases. A larger-scale analysis of 13 distinct stresses illustrates our ability to compute the building blocks of the interaction networks activated in response to these stresses. Source code implementing our algorithms is available under version 2 of the GNU General Public License at http://bioinformatics.cs.vt.edu/ murali/software/network-lego.