Described are methods for the high-throughput discovery and genotyping of nucleotide polymorphisms in DNA, including single nucleotide polymorphism (SNPs) and short deletions and insertions. These methods take advantage of the fact that differences in DNA sequence result in the differential presence of restriction endonuclease digestion sites. Approaches involve isolation of short DNA fragments (“tags”) near restriction endonuclease sites. The presence of one (or two) of these tags indicates that a site was present. Regions of DNA with a restriction site in only one individual create an opportunity for primer extension to produce labeled material, which can be assayed on a platform that employs a collection of nucleic acids. Efficient variant detection microarrays and bead libraries are provided that contain genomic tags with different representations between two populations, so that most elements in the collection of nucleic acids contain a SNP between populations of interest.