Next-generation sequencing technologies allow the measurement of somatic mutations in a large number of patients from the same cancer type. One of the main goals in the analysis of these mutations is the identification of mutations associated with clinical parameters, for example survival time. This goal is complicated by the extensive genetic heterogeneity of mutations in cancer, due to the fact that genes and mutations act in the context of subnetworks or pathways.

 

We propose a novel algorithm, NoMAS, that directly finds subnetworks of a large gene-gene interaction network with mutations associated with survival. NoMAS employs a score for subnetworks based on the test statistic of the log-rank test, a widely used statistical test for survival analysis. We tested NoMAS on simulated and cancer data, comparing it to approaches based on single gene scores and to various greedy approaches. Our results show that NoMAS performs better than other approaches and identifies subnetworks with significant association to survival while none of the genes has significant association with survival when considered in isolation.