In this paper, we investigate the underlying common gene expression signatures in related cancer types. Shared expression signatures are investigated in breast and ovarian cancers specifically through the definition of four progressively more difficult classification problems. SHEBA, a stochastic Bayesian inference approach, is introduced to identify highly predictive gene sets in the defined classification problems. The heuristics reduce the computation time required to identify the most informative groups of features in the gene space, while providing a good approximation of comparable exhaustive approaches. The breast and ovarian cancer class could be distinguished well from the other classes of cancers using SHEBA in three of the four classification problems, suggesting the existence of a commonality between their gene expressions. Extensive statistical validation and preliminary biological review of the most predictive gene sets demonstrate their robustness and specificity.