Background <p>Most molecular classifications of cancer are based on bulk-tissue profiles that measure an average over many distinct cell types. As such, cancer subtypes inferred from transcriptomic or epigenetic data are strongly influenced by cell-type composition and do not necessarily reflect subtypes defined by cell-type-specific cancer-associated alterations, which could lead to suboptimal cancer classifications.</p> Methods <p>To address this problem, we here propose the novel concept of cell-type-specific combinatorial clustering (CELTYC), which aims to group cancer samples by the molecular alterations they display in specific cell types. We illustrate this concept in the context of DNA methylation data of liver and kidney cancer, deriving in each case novel cancer subtypes and assessing their prognostic relevance against current state-of-the-art prognostic models.</p> Results <p>In both liver and kidney cancer, we reveal improved cell-type-specific prognostic models, not discoverable using standard methods. In the case of kidney cancer, we show how combinatorial indexing of epithelial and immune-cell clusters define improved prognostic models driven by synergy of high mitotic age and altered cytokine signaling. We validate the improved prognostic models in independent datasets and identify underlying cytokine-immune-cell signatures driving poor outcome.</p> Conclusions <p>In summary, cell-type-specific combinatorial clustering is a valuable strategy to help dissect and improve current prognostic classifications of cancer in terms of the underlying cell-type-specific epigenetic and transcriptomic alterations.</p>