The correct diagnosis of cancer patients conventionally depends on the pathologist's experience and ability to distinguish cancer tissue from normal tissue under a microscope. Advances in technology for measuring the abundance of, e.g., proteins and mRNAs in tissue samples make it interesting to search for an optimal subset of these for classification of samples as cancer or normal. We discuss issues of identification of biomarkers that provide distinct signatures for prediction of tissues as cancer or normal, exemplified by our recent study of cancer signalling signatures in human colon cancer characterised with regards to protein abundance using high sensitivity isoelectric focusing. We show that the optimal subset for separation of cancer tissues from normal tissues does not contain any of the proteins in the top quintile in terms of significant difference between the groups according to Mann-Whitney U-test or correlation to the diagnosis. Actually, one of the proteins belongs to the tertile with the lowest significance and correlation. This highlights the weakness of the practice of only looking for significant differences in the abundance of individual proteins and raises the question of how many lifesaving discoveries that have been missed due to it. We also demonstrate how Monte Carlo simulations of the separation with random class assignment can be used to calculate p-values for observing any specific separation by chance and selection of the optimal number of proteins in the subset based on these p-values. Both selection of the optimal number of biomarkers and calculation of p-values corrected for multiple hypothesis testing are essential to obtain a subset of biomarkers that yield robust predictions for clinical use.