TCS Journal 2007 Journal Article
Non-unique probe selection and group testing
- Feng Wang
- Hongwei David Du
- Xiaohua Jia
- Ping Deng
- Weili Wu
- David MacCallum
A minimization problem that has arisen from the study of non-unique probe selection with group testing technique is as follows: Given a binary matrix, find a d -disjunct submatrix with the minimum number of rows and the same number of columns. We show that when every probe hybridizes to at most two viruses, i. e. , every row contains at most two 1s, this minimization is still MAX SNP-complete, but has a polynomial-time approximation with performance ratio 1 + 2 / ( d + 1 ). This approximation is constructed based on an interesting result that the above minimization is polynomial-time solvable when every probe hybridizes to exactly two viruses.