TY - CHAP
T1 - Tight approximability results for test set problems in bioinformatics
AU - Berman, Piotr
AU - DasGupta, Bhaskar
AU - Kao, Ming Yang
N1 - Funding Information:
A preliminary version of these results appeared in: T. Hagerup, J. Katajainen (Eds.), Nineth Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, vol. 3111, Springer, July 2004, pp. 39–50. ∗Corresponding author. E-mail addresses: [email protected] (P. Berman), [email protected] (B. DasGupta), [email protected] (M.-Y. Kao). 1Supported by NSF Grant CCR-0208821. 2Supported in part by NSF Grants CCR-0296041, CCR-0206795, CCR-0208749 and a CAREER Grant IIS-0346973. 3Supported in part by NSF Grant EIA-0112934.
PY - 2004
Y1 - 2004
N2 - In this paper, we investigate the test set problem and its variations that appear in a variety of applications. In general, we are given a universe of objects to be "distinguished" by a family of "tests", and we want to find the smallest sufficient collection of tests. In the simplest version, a test is a subset of the universe and two objects are distinguished by our collection if one test contains exactly one of them. Variations allow tests to be multi-valued functions or unions of "basic" tests, and different notions of the term distinguished. An important version of this problem that has applications in DNA sequence analysis has the universe consisting of strings over a small alphabet and tests that are detecting presence (or absence) of a substring. For most versions of the problem, including the latter, we establish matching lower and upper bounds on approximation ratio. When tests can be formed as unions of basic tests, we show that the problem is as hard as the graph coloring problem.
AB - In this paper, we investigate the test set problem and its variations that appear in a variety of applications. In general, we are given a universe of objects to be "distinguished" by a family of "tests", and we want to find the smallest sufficient collection of tests. In the simplest version, a test is a subset of the universe and two objects are distinguished by our collection if one test contains exactly one of them. Variations allow tests to be multi-valued functions or unions of "basic" tests, and different notions of the term distinguished. An important version of this problem that has applications in DNA sequence analysis has the universe consisting of strings over a small alphabet and tests that are detecting presence (or absence) of a substring. For most versions of the problem, including the latter, we establish matching lower and upper bounds on approximation ratio. When tests can be formed as unions of basic tests, we show that the problem is as hard as the graph coloring problem.
UR - http://www.scopus.com/inward/record.url?scp=25144496859&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=25144496859&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-27810-8_5
DO - 10.1007/978-3-540-27810-8_5
M3 - Chapter
AN - SCOPUS:25144496859
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 39
EP - 50
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
A2 - Hagerup, Torben
A2 - Katajainen, Jyrki
PB - Springer Verlag
ER -