  A central goal in cancer genomics is to identify the somatic alterations that
underpin tumor initiation and progression. This task is challenging as the
mutational profiles of cancer genomes exhibit vast heterogeneity, with many
alterations observed within each individual, few shared somatically mutated
genes across individuals, and important roles in cancer for both frequently and
infrequently mutated genes. While commonly mutated cancer genes are readily
identifiable, those that are rarely mutated across samples are difficult to
distinguish from the large numbers of other infrequently mutated genes. Here,
we introduce a method that considers per-individual mutational profiles within
the context of protein-protein interaction networks in order to identify small
connected subnetworks of genes that, while not individually frequently mutated,
comprise pathways that are perturbed across (i.e., "cover") a large fraction of
the individuals. We devise a simple yet intuitive objective function that
balances identifying a small subset of genes with covering a large fraction of
individuals. We show how to solve this problem optimally using integer linear
programming and also give a fast heuristic algorithm that works well in
practice. We perform a large-scale evaluation of our resulting method, nCOP, on
6,038 TCGA tumor samples across 24 different cancer types. We demonstrate that
our approach nCOP is more effective in identifying cancer genes than both
methods that do not utilize any network information as well as state-of-the-art
network-based methods that aggregate mutational information across individuals.
Overall, our work demonstrates the power of combining per-individual mutational
information with interaction networks in order to uncover genes functionally
relevant in cancers, and in particular those genes that are less frequently
mutated.
