Hardness and approximation of the asynchronous border minimization problem

Alexandru Popa, Prudence W H Wong, Fencol C C Yung

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

Abstract

We study a combinatorial problem arising from the microarrays synthesis. The objective of the BMP is to place a set of sequences in the array and to find an embedding of these sequences into a common supersequence such that the sum of the "border length" is minimized. A variant of the problem, called P-BMP, is that the placement is given and the concern is simply to find the embedding. Approximation algorithms have been proposed for the problem [21] but it is unknown whether the problem is NP-hard or not. In this paper, we give a comprehensive study of different variations of BMP by presenting NP-hardness proofs and improved approximation algorithms. We show that P-BMP, 1D-BMP, and BMP are all NP-hard. In contrast with the result in [21] that 1D-P-BMP is polynomial time solvable, the interesting implications include (i) the array dimension (1D or 2D) differentiates the complexity of P-BMP; (ii) for 1D array, whether placement is given differentiates the complexity of BMP; (iii) BMP is NP-hard regardless of the dimension of the array. Another contribution of the paper is improving the approximation for BMP from O(n 1/2 log 2 n) to O(n 1/4 log 2n), where n is the total number of sequences.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages164-176
Number of pages13
Volume7287 LNCS
DOIs
Publication statusPublished - 2012
Externally publishedYes
Event9th Annual Conference on Theory and Applications of Models of Computation, TAMC 2012 - Beijing, China
Duration: May 16 2012May 21 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7287 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other9th Annual Conference on Theory and Applications of Models of Computation, TAMC 2012
CountryChina
CityBeijing
Period5/16/125/21/12

Fingerprint

Approximation algorithms
Hardness
Minimization Problem
NP-complete problem
Microarrays
Approximation
Differentiate
Placement
Approximation Algorithms
Computational complexity
Polynomials
NP-hardness
Combinatorial Problems
Microarray
Polynomial time
Synthesis
Unknown

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this

Popa, A., Wong, P. W. H., & Yung, F. C. C. (2012). Hardness and approximation of the asynchronous border minimization problem. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 7287 LNCS, pp. 164-176). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7287 LNCS). https://doi.org/10.1007/978-3-642-29952-0_20

Hardness and approximation of the asynchronous border minimization problem. / Popa, Alexandru; Wong, Prudence W H; Yung, Fencol C C.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 7287 LNCS 2012. p. 164-176 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7287 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Popa, A, Wong, PWH & Yung, FCC 2012, Hardness and approximation of the asynchronous border minimization problem. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). vol. 7287 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7287 LNCS, pp. 164-176, 9th Annual Conference on Theory and Applications of Models of Computation, TAMC 2012, Beijing, China, 5/16/12. https://doi.org/10.1007/978-3-642-29952-0_20
Popa A, Wong PWH, Yung FCC. Hardness and approximation of the asynchronous border minimization problem. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 7287 LNCS. 2012. p. 164-176. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-29952-0_20
Popa, Alexandru ; Wong, Prudence W H ; Yung, Fencol C C. / Hardness and approximation of the asynchronous border minimization problem. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 7287 LNCS 2012. pp. 164-176 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{3510373b2119408ba7cfdac933f166f0,
title = "Hardness and approximation of the asynchronous border minimization problem",
abstract = "We study a combinatorial problem arising from the microarrays synthesis. The objective of the BMP is to place a set of sequences in the array and to find an embedding of these sequences into a common supersequence such that the sum of the {"}border length{"} is minimized. A variant of the problem, called P-BMP, is that the placement is given and the concern is simply to find the embedding. Approximation algorithms have been proposed for the problem [21] but it is unknown whether the problem is NP-hard or not. In this paper, we give a comprehensive study of different variations of BMP by presenting NP-hardness proofs and improved approximation algorithms. We show that P-BMP, 1D-BMP, and BMP are all NP-hard. In contrast with the result in [21] that 1D-P-BMP is polynomial time solvable, the interesting implications include (i) the array dimension (1D or 2D) differentiates the complexity of P-BMP; (ii) for 1D array, whether placement is given differentiates the complexity of BMP; (iii) BMP is NP-hard regardless of the dimension of the array. Another contribution of the paper is improving the approximation for BMP from O(n 1/2 log 2 n) to O(n 1/4 log 2n), where n is the total number of sequences.",
author = "Alexandru Popa and Wong, {Prudence W H} and Yung, {Fencol C C}",
year = "2012",
doi = "10.1007/978-3-642-29952-0_20",
language = "English",
isbn = "9783642299513",
volume = "7287 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "164--176",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

TY - GEN

T1 - Hardness and approximation of the asynchronous border minimization problem

AU - Popa, Alexandru

AU - Wong, Prudence W H

AU - Yung, Fencol C C

PY - 2012

Y1 - 2012

N2 - We study a combinatorial problem arising from the microarrays synthesis. The objective of the BMP is to place a set of sequences in the array and to find an embedding of these sequences into a common supersequence such that the sum of the "border length" is minimized. A variant of the problem, called P-BMP, is that the placement is given and the concern is simply to find the embedding. Approximation algorithms have been proposed for the problem [21] but it is unknown whether the problem is NP-hard or not. In this paper, we give a comprehensive study of different variations of BMP by presenting NP-hardness proofs and improved approximation algorithms. We show that P-BMP, 1D-BMP, and BMP are all NP-hard. In contrast with the result in [21] that 1D-P-BMP is polynomial time solvable, the interesting implications include (i) the array dimension (1D or 2D) differentiates the complexity of P-BMP; (ii) for 1D array, whether placement is given differentiates the complexity of BMP; (iii) BMP is NP-hard regardless of the dimension of the array. Another contribution of the paper is improving the approximation for BMP from O(n 1/2 log 2 n) to O(n 1/4 log 2n), where n is the total number of sequences.

AB - We study a combinatorial problem arising from the microarrays synthesis. The objective of the BMP is to place a set of sequences in the array and to find an embedding of these sequences into a common supersequence such that the sum of the "border length" is minimized. A variant of the problem, called P-BMP, is that the placement is given and the concern is simply to find the embedding. Approximation algorithms have been proposed for the problem [21] but it is unknown whether the problem is NP-hard or not. In this paper, we give a comprehensive study of different variations of BMP by presenting NP-hardness proofs and improved approximation algorithms. We show that P-BMP, 1D-BMP, and BMP are all NP-hard. In contrast with the result in [21] that 1D-P-BMP is polynomial time solvable, the interesting implications include (i) the array dimension (1D or 2D) differentiates the complexity of P-BMP; (ii) for 1D array, whether placement is given differentiates the complexity of BMP; (iii) BMP is NP-hard regardless of the dimension of the array. Another contribution of the paper is improving the approximation for BMP from O(n 1/2 log 2 n) to O(n 1/4 log 2n), where n is the total number of sequences.

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

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

U2 - 10.1007/978-3-642-29952-0_20

DO - 10.1007/978-3-642-29952-0_20

M3 - Conference contribution

SN - 9783642299513

VL - 7287 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 164

EP - 176

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -