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.