Parameterized Complexity of Asynchronous Border Minimization

Robert Ganian, Martin Kronegger, Andreas Pfandler, Alexandru Popa

Research output: Contribution to journalArticle

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

Original languageEnglish
Pages (from-to)1-23
Number of pages23
JournalAlgorithmica
DOIs
Publication statusAccepted/In press - May 15 2018

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

    Ganian, R., Kronegger, M., Pfandler, A., & Popa, A. (Accepted/In press). Parameterized Complexity of Asynchronous Border Minimization. Algorithmica, 1-23. https://doi.org/10.1007/s00453-018-0442-5