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 language | English |
|---|---|
| Pages (from-to) | 1-23 |
| Number of pages | 23 |
| Journal | Algorithmica |
| DOIs | |
| Publication status | Accepted/In press - May 15 2018 |
Fingerprint
Keywords
- Fixed-parameter tractability
- Microarrays
- NP-hard problem
- Parameterized complexity
ASJC Scopus subject areas
- Computer Science(all)
- Computer Science Applications
- Applied Mathematics
Cite this
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 journal › Article
}
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
AN - SCOPUS:85046894462
SP - 1
EP - 23
JO - Algorithmica
JF - Algorithmica
SN - 0178-4617
ER -