Abstract Just like recurrent somatic alterations characterize cancer genes, mutually exclusive or co-occurring alterations across genes suggest functional interactions. Identifying such patterns in large cancer studies thus helps the discovery of unknown interactions. Many studies use Fisher’s exact test or simple permutation procedures for this purpose. These tests assume identical gene alteration probabilities across tumors, which is not true for cancer. We show that violating this assumption yields many spurious co-occurrences and misses many mutual exclusivities. We present DISCOVER, a novel statistical test that addresses the limitations of existing tests. In a comparison with six published mutual exclusivity tests, DISCOVER is more sensitive while controlling its false positive rate. A pan-cancer analysis using DISCOVER finds no evidence for widespread co-occurrence. Most co-occurrences previously detected do not exceed expectation by chance. In contrast, many mutual exclusivities are identified. These cover well known genes involved in the cell cycle and growth factor signaling. Interestingly, also lesser known regulators of the cell cycle and Hedgehog signaling are identified. Availability R and Python implementations of DISCOVER, as well as Jupyter notebooks for reproducing all results and figures from this paper can be found at http://ccb.nki.nl/software/discover .