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

Fingerprint

Parameterized Complexity
Microarrays
Minimization Problem
Microarray
Probe
Cell
Assignment
Strings
Tractability
Genes
Hardness
Placement
Diagnostics
Cancer
Complement
Gene

Keywords

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

ASJC Scopus subject areas

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

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

Parameterized Complexity of Asynchronous Border Minimization. / Ganian, Robert; Kronegger, Martin; Pfandler, Andreas; Popa, Alexandru.

In: Algorithmica, 15.05.2018, p. 1-23.

Research output: Contribution to journalArticle

Ganian, Robert ; Kronegger, Martin ; Pfandler, Andreas ; Popa, Alexandru. / Parameterized Complexity of Asynchronous Border Minimization. In: Algorithmica. 2018 ; pp. 1-23.
@article{e280142bb19a4281aeda8a928baa57a7,
title = "Parameterized Complexity of Asynchronous Border Minimization",
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.",
keywords = "Fixed-parameter tractability, Microarrays, NP-hard problem, Parameterized complexity",
author = "Robert Ganian and Martin Kronegger and Andreas Pfandler and Alexandru Popa",
year = "2018",
month = "5",
day = "15",
doi = "10.1007/s00453-018-0442-5",
language = "English",
pages = "1--23",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer New York",

}

TY - JOUR

T1 - Parameterized Complexity of Asynchronous Border Minimization

AU - Ganian, Robert

AU - Kronegger, Martin

AU - Pfandler, Andreas

AU - Popa, Alexandru

PY - 2018/5/15

Y1 - 2018/5/15

N2 - 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.

AB - 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.

KW - Fixed-parameter tractability

KW - Microarrays

KW - NP-hard problem

KW - Parameterized complexity

UR - http://www.scopus.com/inward/record.url?scp=85046894462&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85046894462&partnerID=8YFLogxK

U2 - 10.1007/s00453-018-0442-5

DO - 10.1007/s00453-018-0442-5

M3 - Article

SP - 1

EP - 23

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

ER -