Towards finding the complete modulome: density constrained biclustering

Large-scale gene expression experiments and interaction networks have become major data sources for discovery in systems biology. In several types of interaction networks, as is widely established, active modules, i.e. functional, simultaneously active groups of genes, are best encoded as highly interconnected regions that are co-expressed and show significant changes in an accompanying set of gene expression experiments. Accordingly, inferring an organism's active modulome, the entirety of active modules, translates to identifying these dense and co-expressed regions, which is NP-hard. We provide a novel algorithm, DCB-Miner, that addresses the corresponding computationally hard problem by means of a carefully designed search strategy, which has been specifically adapted to the topological peculiarities of protein interaction networks. Our algorithm outperforms all prior related approaches on standard datasets from H. sapiens and S. cerevisiae in a Gene Ontology-based competition and finds modules that convey particularly interesting novel biological meaning.