Non-unique probe selection and group testing

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.

Authors

• Feng Wang
• Hongwei David Du
• Xiaohua Jia
• Ping Deng
• Weili Wu
• David MacCallum

Keywords

• Group testing
• d -disjoint matrix
• d ̄ -separable matrix
• Vertex cover