Abstract

Study of pairwise genetic interactions such as mutual exclusivity or synthetic lethality has led to the development of targeted anticancer therapies, and mining the network of such interactions is a common approach used to obtain deeper insights into the mechanism of cancer. A number of useful graph clustering-based tools exist to mine interaction networks. These tools find subgraphs or groups of genes wherein each gene belongs to a single subgraph. However, a gene may be present in multiple groups - for instance, a gene can be involved in multiple signalling pathways. We develop a new network mining algorithm, that does not impose this constraint and can provide a novel pathway-centric view. Our approach is based on finding edge-disjoint bipartite subgraphs of highest weights in an input network of genes, where edge weights indicate the significance of the interaction and each set of nodes in every bipartite subgraph is constrained to belong to a single pathway. This problem is NP-hard and we develop an Integer Linear Program to solve this problem. We evaluate our algorithm on breast and stomach cancer data. Our algorithm mines dense between-pathway interactions that are known to play important roles in cancer and are therapeutically actionable. Our algorithm complements existing network mining tools and can be useful to study the mutational landscape of cancer and inform therapy development.