Parameterized Complexity of Asynchronous Border Minimization

Robert Ganian, Martin Kronegger, Andreas Pfandler, Alexandru Popa

Research output: Contribution to journalArticlepeer-review

Abstract

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 BMP e and P-BMP e respectively, under several natural parameters. We show that BMP e and P-BMP e 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 (ℓ) 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-BMP e is in FPT when parameterized by c and ℓ. We complement our tractability results with a number of corresponding hardness results.

Original languageEnglish
Pages (from-to)201-223
Number of pages23
JournalAlgorithmica
Volume81
Issue number1
DOIs
Publication statusPublished - Jan 15 2019

Keywords

  • Fixed-parameter tractability
  • Microarrays
  • NP-hard problem
  • Parameterized complexity

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Parameterized Complexity of Asynchronous Border Minimization'. Together they form a unique fingerprint.

Cite this