Title: Efficient algorithms to discover alterations with complementary functional association in cancer,
Abstract: 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 effectivenes 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
computation 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 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 one such dataset from project Achilles our methods identify several
significant gene sets with complementary functional associations with targets.