Parameterized Complexity of Asynchronous Border Minimization

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F19%3A00113713" target="_blank" >RIV/00216224:14330/19:00113713 - isvavai.cz</a>

Výsledek na webu

<a href="https://link.springer.com/article/10.1007/s00453-018-0442-5" target="_blank" >https://link.springer.com/article/10.1007/s00453-018-0442-5</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00453-018-0442-5" target="_blank" >10.1007/s00453-018-0442-5</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Parameterized Complexity of Asynchronous Border Minimization

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Parameterized Complexity of Asynchronous Border Minimization

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Algorithmica

ISSN

0178-4617

e-ISSN

—

Svazek periodika

81

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

23

Strana od-do

201-223

Kód UT WoS článku

000455323200009

EID výsledku v databázi Scopus

2-s2.0-85046894462