Discovering maximal cohesive subgraphs and patterns from attributed biological networks

With the availability of vast amounts of protein-protein, protein-DNA interactions, and genome-wide mRNA expression data for several organisms, identifying biological complexes has emerged as a major task in systems biology. Most of the existing approaches for complex identification have focused on utilizing one source of data. Recent research has shown that systematic integration of gene profile data with interaction data yields significant patterns. In this paper, we introduce the problem of mining maximal cohesive subnetworks that satisfy user-defined constraints defined over the gene profiles of the reported subnetworks. Moreover, we introduce the problem of finding maximal cohesive patterns which are sets of coehsive genes. Experiments on Yeast and Human datasets show the effectiveness of the proposed approach by assessing the overlap of the discovered subnetworks with known biological complexes. Moreover, GO enrichment analysis show that the discovered subnetworks are biologically significant. The proposed algorithm takes only seconds to several minutes to run on the Human dataset depending on how stringent the user-defined constraint is.