## DIMACS TR: 2003-14

## Tight Approximability Results for Test Set Problems in Bioinformatics

### Authors: Piotr Berman and Bhaskar DasGupta and Ming-Yang Kao

**
ABSTRACT
**

In this paper, we investigate several versions of a test set problem. In
the simplest version, given a family of tests, viewed as subsets of the
universe, we want to select the smallest subfamily that separates every
two elements of the universe. We show that this problem is exactly as
difficult to approximate as the set cover problem, up to a factor of 1
plus or minus o(1). The same holds for several more elaborate versions of
the problem that have applications in bioinformatics; for example, in one
version the universe consists of strings over a finite alphabet and each
test checks the presence of a specific substring. We also show that if we
allow to form tests as unions of the given tests, the problem has
essentially the same level of computational intractability as graph
coloring.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2003/2003-14.ps.gz

DIMACS Home Page