High-density DNA oligonucleotide microarrays are widely used in biomedical research. In this paper, we describe algorithms to optimize the selection of specific probes for each gene in an entire genome. Having optimized probes for each gene is valuable for two reasons: (1) by minimizing background hybridization, they provide more accurate determinations of true expression levels, and (2) having optimum probes eliminates the need for multiple probes per gene, as is usually done now, thereby decreasing the cost of each microarray and increasing their usage. The criteria for truly optimum probes is easily stated, but they are not computable at present. We have developed a heuristic approach that is efficiently computable and should provide a good approximation to the true optimum set. We have run the program on the complete genomes for several model organisms and deposited the results in a database that is available online ('http://ural.wustl.edu/~lif/probe.pl').