Seminár z teoretickej informatiky

Fri 11 Oct. 2013, 11:00

Title: The Border Minimization Problem
Speaker: Alexandru Popa, Masarykova univerzita, Brno

We study a combinatorial problem arising from microarrays synthesis. 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.