The possibility to collect genomic profiles (gene expression, mutations, ...) from cancer patients paves the way to automatic patient stratification from genomic data to predict survival, risk of relapse or response to a therapy, for example. The stratification rule itself is usually estimated automatically on retrospective cohorts of patients with both genomic information and output, using a regression or classification algorithm. This estimation problem is however challenging from a statistical point of view, since candidate genomic markers (expression, mutations...) usually outnumber the number of patients in the cohorts. In this talk I will illustrate the difficulty of estimating such genomic signatures, and present a few methods we have developed in recent years to improve the estimation of genomic signatures, in particular the use of gene networks and of permutations to learn signatures from gene expression or somatic mutations.