Module discovery by exhaustive search for densely connected, co-expressed regions in biomolecular interaction networks

Abstract

Background: Computational prediction of functionally related groups of genes (functional modules) from large-scale data is an important issue in computational biology. Gene expression experiments and interaction networks are well studied large-scale data sources, available for many not yet exhaustively annotated organisms. It has been well established, when analyzing these two data sources jointly, modules are often reflected by highly interconnected (dense) regions in the interaction networks whose participating genes are co-expressed. However, the tractability of the problem had remained unclear and methods by which to exhaustively search for such constellations had not been presented.

Methodology/principal findings: We provide an algorithmic framework, referred to as Densely Connected Biclustering (DECOB), by which the aforementioned search problem becomes tractable. To benchmark the predictive power inherent to the approach, we computed all co-expressed, dense regions in physical protein and genetic interaction networks from human and yeast. An automatized filtering procedure reduces our output which results in smaller collections of modules, comparable to state-of-the-art approaches. Our results performed favorably in a fair benchmarking competition which adheres to standard criteria. We demonstrate the usefulness of an exhaustive module search, by using the unreduced output to more quickly perform GO term related function prediction tasks. We point out the advantages of our exhaustive output by predicting functional relationships using two examples.

Conclusion/significance: We demonstrate that the computation of all densely connected and co-expressed regions in interaction networks is an approach to module discovery of considerable value. Beyond confirming the well settled hypothesis that such co-expressed, densely connected interaction network regions reflect functional modules, we open up novel computational ways to comprehensively analyze the modular organization of an organism based on prevalent and largely available large-scale datasets.

Availability: Software and data sets are available at http://www.sfu.ca/~ester/software/DECOB.zip.

Figure 1. This figure refers to the definition of a densely connected bicluster (see Methods section, definition 1) referring to the parameters (density) and (co-expression constraints).

The input for the core algorithm is the interaction network of the organism (here, as a toy example, genes A,B,C,D,E,F,G,H,I,J and K) together with gene expression dataset containing (logarithmic) fold changes of genes across a set of experimental conditions (here: the table below the interaction network). On the right, we display the set of densely connected biclusters which refer to the datasets on the left. The densely connected biclusters contain at least times the amount of possible edges and its genes are co-expressed in at least different experimental conditions () with a difference of at most ().

Figure 2. Runtimes of our algorithm for varying, biologically relevant choices of the parameters involved in our framework.

The most important observation is that we have runtimes of at most a few minutes for all choices of (density).

Figure 3. Two real case examples of a Yeast (left) and a Human (right) module as inferred by application of DECOB and further filtering by GO terms of specific interest.

The Yeast module on the left was obtained by screening the output of DECOB for modules which are enriched with the GO term “Chromatin Assembly” (GO:0006333). The Human module on the left was obtained by screening the output of DECOB for modules which are enriched with the GO term “Wnt Receptor Signaling Pathway through Beta-Catenin” (GO:0060070).

Figure 4. Illustration of the DECOB algorithm on a simplified example consisting of six genes and three gene expression conditions.

DECOB constraints are specified by: (density), (maximum difference in expression) and (number of expression conditions). The algorithmic strategy is to traverse the lattice of all subnetworks in a breadth-first fashion. Any subnetwork which is not a densely connected biclusters can be discarded due to that every densely connected bicluster necessarily has a densely connected bicluster as a parent ( = subnetwork contained in the original one, see definitions 1 and 3 and the surrounding discussions). For esthetical reasons, we have omitted B-C-D-E although, as a child of the densely connected bicluster B-C-D, it is also examined. B-C-D-E, just as A-B-D-E will be discarded since it violates the density constraint.