The Border Minimization Problem

The synthesis is done by a light-directed chemical process. The
objective is to minimize unintended illumination that may contaminate
the quality of experiments. Unintended illumination is measured by a
notion called border length and the problem is called Border
Minimization Problem (BMP). The objective of the BMP is to place a set
of probe sequences in the array and find an embedding (deposition of
nucleotides/residues to the array cells) such that the sum of border
length is minimized. A variant of the problem, called P-BMP, is that
the placement is given and the concern is simply to find the
embedding. Approximation algorithms have been previously proposed for
the problem but it is unknown whether the problem is NP-hard or not.
In this talk, we present hardness and approximation results for
different variations of BMP and P-BMP.