Abstract
In this paper, we studied the MINimum-d-Disjunct Submatrix (MIN-d-DS), which can be used to select the minimum number of non-unique probes for viruses identification. We prove that MIN-d-DS is NP-hard for any fixed d. Using d-disjunct matrix, we present an O(logk)-approximation algorithm where k is an upper bound on the maximum number of targets hybridized to a probe. We also present a (1+(d+1)logn)-approximation algorithm to identify at most d targets in the presence of experimental errors. Our approximation algorithms also yield a linear time complexity for the decoding algorithms.
Original language | English |
---|---|
Pages (from-to) | 45-53 |
Number of pages | 9 |
Journal | Journal of Combinatorial Optimization |
Volume | 17 |
Issue number | 1 |
DOIs | |
Publication status | Published - Jan 2009 |
Externally published | Yes |
Keywords
- Non-adaptive group testing
- Non-unique probe
- Pooling designs
- d-disjunct matrix
ASJC Scopus subject areas
- Computer Science Applications
- Discrete Mathematics and Combinatorics
- Control and Optimization
- Computational Theory and Mathematics
- Applied Mathematics