Microarrays are a ubiquitous tool in molecular biology with a wide range of applications on a whole-genome scale including high-throughput gene expression analysis, genotyping, and resequencing. Although several different microarray platforms exist, we focus on high-density oligonucleotide arrays, sometimes called DNA chips. One of the advantages of higher density arrays is that they allow the simultaneous measurement of the expression of several thousand genes at once, possibly covering all genes of a species in a single experiment.

Oligonucleotide microarrays consist of short DNA molecules, called probes, affixed or synthesized at specific locations of a solid support. Probes are built, nucleotide-by-nucleotide, by a light-directed combinatorial chemistry. Because of the natural properties of light, the quality of a microarray can be compromised if the physical arrangement of the probes on the array and their synthesis schedule are not carefully designed. This thesis is mainly concerned with the problem of designing the layout of a microarray in such a way that the incidence of the unintended illumination problem is reduced. We call it the microarray layout problem (MLP), using the term layout to refer to where and how the probes are synthesized on the array, i.e., their arrangement and their embeddings.