### 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 ^{2}n), where n is the total number of sequences.

Original language | English |
---|---|

Title of host publication | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Pages | 164-176 |

Number of pages | 13 |

Volume | 7287 LNCS |

DOIs | |

Publication status | Published - 2012 |

Externally published | Yes |

Event | 9th Annual Conference on Theory and Applications of Models of Computation, TAMC 2012 - Beijing, China Duration: May 16 2012 → May 21 2012 |

### Publication series

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

Volume | 7287 LNCS |

ISSN (Print) | 03029743 |

ISSN (Electronic) | 16113349 |

### Other

Other | 9th Annual Conference on Theory and Applications of Models of Computation, TAMC 2012 |
---|---|

Country | China |

City | Beijing |

Period | 5/16/12 → 5/21/12 |

### Fingerprint

### ASJC Scopus subject areas

- Computer Science(all)
- Theoretical Computer Science

### Cite this

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*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

}

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 -