### 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

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

Research output: Contribution to journal › Article

*Algorithmica*, pp. 1-23. https://doi.org/10.1007/s00453-018-0442-5

}

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 -