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 publicationTheory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Proceedings
Pages164-176
Number of pages13
DOIs
Publication statusPublished - May 18 2012
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)0302-9743
ISSN (Electronic)1611-3349

Other

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Hardness and approximation of the asynchronous border minimization problem'. Together they form a unique fingerprint.

  • Cite this

    Popa, A., Wong, P. W. H., & Yung, F. C. C. (2012). Hardness and approximation of the asynchronous border minimization problem. In Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Proceedings (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