Name
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 log2n ) to O (n 1/4 log2n ), where n is the total number of sequences. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-29952-0_20 | TAMC'12 Proceedings of the 9th Annual international conference on Theory and Applications of Models of Computation |
Keywords | Field | DocType |
different variation,border length,improved approximation algorithm,interesting implication,asynchronous border minimization problem,np-hardness proof,comprehensive study,approximation algorithm,microarrays synthesis,combinatorial problem,array dimension,nucleotides,polynomial time,data structure | Minimization problem,Approximation algorithm,Asynchronous communication,Discrete mathematics,Combinatorics,Embedding,Mathematical proof,Eulerian path,Time complexity,Mathematics | Journal |
Citations | PageRank | References |
0 | 0.34 | 19 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexandru Popa | 1 | 70 | 13.34 |
| Prudence W. H. Wong | 2 | 374 | 38.69 |
| Fencol C. C. Yung | 3 | 30 | 4.15 |