** DNA Array Synthesis**
DNA arrays are synthesized using a photolithographic method similar to
VLSI chip manufacturing. In this context, appropriate regions are activated
by illuminating the array through a series of masks. Due to diffraction,
internal reflection, and scattering, points close to the border between
illuminated and shadowed regions are often subject to unintended
illumination levels. To reduce the amount of unknown synthesized sequences
and simplify interpretation of experimental data, a main objective of DNA
array design is to minimize the total border length of the masks. There
are two degrees of freedom that can be used to minimize border length: the
assignment of probes to array cells (also called placement), and the
geometry of masks.

A sequence of masks is periodic if the masks synthesize nucleotides in a
fixed periodic order, e.g., A,C,T,G,A,C,T,G,... A recent paper by
Hannenhalli, Hubbell, Lipshutz, and Pevzner considers the case of
synchronous array design, in which the sequence of masks is periodic, and
every probe grows by exactly one nucleotide after every 4 masks. Under
this restriction the mask geometry degree of freedom disappears, and the
placement problem becomes equivalent to finding a 1-to-1 assignment of
probes to array cells such that the sum of Hamming distances between all
pairs of adjacent probes is minimized. We are currently investigating
algorithms for finding periodic (but not necessarily synchronous)
sequences of masks minimizing total border length, as well as methods for
solving the combined probe placement and mask definition problem for
non-synchronous synthesis.