Efficient algorithms to discover alterations with complementary functional association in cancer

Recent large cancer studies have measured somatic alterations in an unprecedented number of tumours. These large datasets allow the identification of cancer-related sets of genetic alterations by identifying relevant combinatorial patterns. Among such patterns, mutual exclusivity has been employed by several recent methods that have shown its effectiveness in characterizing gene sets associated to cancer. Mutual exclusivity arises because of the complementarity, at the functional level, of alterations in genes which are part of a group (e.g., a pathway) performing a given function. The availability of quantitative target profiles, from genetic perturbations or from clinical phenotypes, provides additional information that can be leveraged to improve the identification of cancer related gene sets by discovering groups with complementary functional associations with such targets. In this work we study the problem of finding groups of mutually exclusive alterations associated with a quantitative (functional) target. We propose a combinatorial formulation for the problem, and prove that the associated computational problem is computationally hard. We design two algorithms to solve the problem and implement them in our tool UNCOVER. We provide analytic evidence of the effectiveness of UNCOVER in finding high-quality solutions and show experimentally that UNCOVER finds sets of alterations significantly associated with functional targets in a variety of scenarios. In particular, we show that our algorithms find sets which are better than the ones obtained by the state-of-the-art method, even when sets are evaluated using the statistical score employed by the latter. In addition, our algorithms are much faster than the state-of-the-art, allowing the analysis of large datasets of thousands of target profiles from cancer cell lines. We show that on two such datasets, one from project Achilles and one from the Genomics of Drug Sensitivity in Cancer project, UNCOVER identifies several significant gene sets with complementary functional associations with targets. Software available at: https://github.com/VandinLab/UNCOVER.Author summary: Sequencing technologies allow the measurement of somatic alterations in a large number of cancer samples. Several methods have been designed to analyze these alterations, but the characterization of the functional effects of such alterations is still challenging. A recent promising approach for such characterization is to combine alteration data with quantitative profiles obtained, e.g., from genetic perturbations. The analysis of these data is complicated by the extreme heterogeneity of alterations in cancer, with different cancer samples exhibiting vastly different alterations. This heterogeneity is due, in part, to the complementarity of alterations in cancer pathways, with alterations in different genes resulting in the same alteration at the functional level. We develop UNCOVER, an efficient method to identify sets of alterations displaying complementary functional association with a quantitative profile. UNCOVER is much more efficient than the state-of-the-art, allowing the identification of complementary cancer related alterations from genome-scale measurements of somatic mutations and genetic perturbations.