  Oligonucleotide arrays are used in a wide range of genomic analyses, such as
gene expression profiling, comparative genomic hybridization, chromatin
immunoprecipitation, SNP detection, etc. During fabrication, the sites of an
oligonucleotide array are selectively exposed to light in order to activate
oligonucleotides for further synthesis. Optical effects can cause unwanted
illumination at masked sites that are adjacent to the sites intentionally
exposed to light. This results in synthesis of unforeseen sequences in masked
sites and compromises interpretation of experimental data. To reduce such
uncertainty, one can exploit freedom in how probes are assigned to array sites.
The border length minimization problem (BLMP) seeks a placement of probes that
minimizes the sum of border lengths in all masks. In this paper, we propose two
parallel algorithms for the BLMP. The proposed parallel algorithms have the
local-search paradigm at their core, and are especially developed for the BLMP.
The results reported show that, for small microarrays with at most 1156 probes,
the proposed parallel algorithms perform better than the best previous
algorithms.
