Non-unique probe selection and group testing

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

4 Scopus Citations
View graph of relations

Author(s)

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

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)29-32
Journal / PublicationTheoretical Computer Science
Volume381
Issue number1-3
Publication statusPublished - 22 Aug 2007

Abstract

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. © 2007 Elsevier Ltd. All rights reserved.

Research Area(s)

  • d-disjoint matrix, Group testing, over(d, ̄)-separable matrix, Vertex cover

Citation Format(s)

Non-unique probe selection and group testing. / Wang, Feng; David Du, Hongwei; Jia, Xiaohua et al.
In: Theoretical Computer Science, Vol. 381, No. 1-3, 22.08.2007, p. 29-32.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review