Computational identification of possibly overlapping driver pathways in cancer

Cancer is a heterogeneous disease driven by accumulated somatic mutations. A key challenge in cancer biology is to distinguish cancer-causing driver mutations from inconsequential passenger mutations. To understand the mechanisms of carcinogenesis at the pathway level, it's important to not only identify these mutations but to identify a set of driver genes (modules) that are functional in a driver pathway. Despite the existence of many methods for identifying cancer driver modules, the majority of these methods output non-overlapping modules. This assumption is biologically inaccurate as genes can participate in multiple molecular pathways. This is particularly true for cancer-associated genes as many of them are network hubs connecting a functionally distinct set of genes. It is important to provide combinatorial optimization problem definitions modeling this biological phenomenon and to suggest efficient algorithms for its solution. In this thesis, we provide a formal definition of the Overlapping Driver Module Identi cation in Cancer (ODMIC) problem. We show that the problem is NP-hard. We propose a seed-and-extend based heuristic named DriveWays that identifies overlapping cancer driver modules from the graph built from the IntAct PPI network. DriveWays incorporates mutual exclusivity, coverage, and the network connectivity information of the genes. We show that DriveWays outperforms the state-of-the-art methods in recovering well-known cancer driver genes performed on TCGA pan-cancer data. Additionally, DriveWay's output modules show a stronger enrichment for the reference pathways in almost all cases. Overall, we show that enabling modules to overlap improves the recovery of functional pathways filtered with known cancer drivers, which essentially constitute the reference set of cancer-related pathways.