Parameterized Complexity of Asynchronous Border Minimization

J 2019

Parameterized Complexity of Asynchronous Border Minimization

GANIAN, Robert, Martin KRONEGGER, Andreas PFANDLER a Alexandru POPA

Základní údaje

Originální název

Parameterized Complexity of Asynchronous Border Minimization

Autoři

GANIAN, Robert (203 Česká republika, garant, domácí), Martin KRONEGGER (40 Rakousko), Andreas PFANDLER (40 Rakousko) a Alexandru POPA (642 Rumunsko)

Vydání

Algorithmica, Springer, 2019, 0178-4617

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 0.650

Kód RIV

RIV/00216224:14330/19:00113713

Organizační jednotka

Fakulta informatiky

DOI

http://dx.doi.org/10.1007/s00453-018-0442-5

UT WoS

000455323200009

Klíčová slova anglicky

Parameterized Complexity

Změněno: 14. 5. 2020 10:41, Mgr. Michal Petr

Anotace

V originále

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.

Citovat

GANIAN, Robert, Martin KRONEGGER, Andreas PFANDLER a Alexandru POPA. Parameterized Complexity of Asynchronous Border Minimization. Algorithmica. Springer, 2019, roč. 81, č. 1, s. 201-223. ISSN 0178-4617. Dostupné z: https://dx.doi.org/10.1007/s00453-018-0442-5.

@article{1648239,
   author = {Ganian, Robert and Kronegger, Martin and Pfandler, Andreas and Popa, Alexandru},
   article_number = {1},
   doi = {http://dx.doi.org/10.1007/s00453-018-0442-5},
   keywords = {Parameterized Complexity},
   language = {eng},
   issn = {0178-4617},
   journal = {Algorithmica},
   title = {Parameterized Complexity of Asynchronous Border Minimization},
   url = {https://link.springer.com/article/10.1007/s00453-018-0442-5},
   volume = {81},
   year = {2019}
}

TY  - JOUR
ID  - 1648239
AU  - Ganian, Robert - Kronegger, Martin - Pfandler, Andreas - Popa, Alexandru
PY  - 2019
TI  - Parameterized Complexity of Asynchronous Border Minimization
JF  - Algorithmica
VL  - 81
IS  - 1
SP  - 201-223
EP  - 201-223
PB  - Springer
SN  - 01784617
KW  - Parameterized Complexity
UR  - https://link.springer.com/article/10.1007/s00453-018-0442-5
L2  - https://link.springer.com/article/10.1007/s00453-018-0442-5
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 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.
ER  -

GANIAN, Robert, Martin KRONEGGER, Andreas PFANDLER a Alexandru POPA. Parameterized Complexity of Asynchronous Border Minimization. \textit{Algorithmica}. Springer, 2019, roč.~81, č.~1, s.~201-223. ISSN~0178-4617. Dostupné z: https://dx.doi.org/10.1007/s00453-018-0442-5.

Podrobný výpis o publikaci