Publication details

Parameterized Complexity of Asynchronous Border Minimization

Authors

GANIAN Robert KRONEGGER Martin PFANDLER Andreas POPA Alexandru

Year of publication 2019
Type Article in Periodical
Magazine / Source Algorithmica
MU Faculty or unit

Faculty of Informatics

Citation
Web https://link.springer.com/article/10.1007/s00453-018-0442-5
Doi http://dx.doi.org/10.1007/s00453-018-0442-5
Keywords Parameterized Complexity
Description Microarrays are research tools used in gene discovery as well as disease and cancer diagnostics. Two prominent but challenging problems related to microarrays are the Border Minimization Problem (BMP) and the Border Minimization Problem with given placement (P-BMP). The common task of these two problems is to create so-called probe sequences (essentially a string) in a microarray. Here, the goal of the former problem is to determine an assignment of each probe sequence to a unique cell of the array and afterwards to construct the sequences at their respective cells while minimizing the border length of the probes. In contrast, for the latter problem the assignment of the probes to the cells is already given. In this paper we investigate the parameterized complexity of the natural exhaustive variants of BMP and P-BMP, termed BMPe and P-BMPe respectively, under several natural parameters. We show that BMPe and P-BMPe are in FPT under the following two combinations of parameters: (1) the size of the alphabet (c), the maximum length of a sequence (string) in the input (l) and the number of rows of the microarray (r); and, (2) the size of the alphabet and the size of the border length (o). Furthermore, P-BMPe is in FPT when parameterized by c and l. We complement our tractability results with a number of corresponding hardness results.

You are running an old browser version. We recommend updating your browser to its latest version.

More info