Probe specificity plays a central role in designing accurate microarray hybridization assays. Current literature on specific probe design studies algorithmic approaches and their relationship with hybridization thermodynamics. In this work we address probe specificity properties under a stochastic model assumption and compare the results to actual behavior in genomic data.We develop effcient specificity search algorithms. Our methods incorporate existing transcript expression level data and handle a variety of cross-hybridization models. We analyze the performance of our methods. Applying our algorithm to the entire S. cerevisiae transcriptome we provide probe specificity maps for all yeast ORFs that may be used as the basis for selection of sensitive probes.