title: On the parameterized complexity of pooling design.
abstract: Pooling design is a very helpful tool for reducing the number of tests in DNA library screening, which is a key process to obtain high-quality DNA libraries for studying gene functions. Three basic problems in pooling design are, given an m x n binary matrix and a positive integer d, to decide whether the matrix is d-separable (d-separable, or d-disjunct). The three problems are all known to be coNP-complete. Since in most applications, d is a small integer compared to n, it is interesting to investigate whether there are efficient algorithms solving the above problems when the value of d is small. In this article, we give a negative answer to the above question by studying the parameterized complexity of these three problems, with d as the parameter. We show that the parameterized versions of all the three problems are co-W[2]-complete. An immediate implication of our results is that, given an m x n binary matrix and a positive integer d, a deterministic algorithm with running time f(d) x (mn)(O(1)) (where f is an arbitrary computable function) to decide whether the matrix is d-separable (d-separable, or d-disjunct) should not be expected.
authors.affiliation: Department of Computing Science, University of Alberta, Edmonton, Alberta, Canada. chengyx@gmail.com
authors.forename: Yongxi
authors.initials: Y
authors.lastname: Cheng
authors.forename: Ding-Zhu
authors.initials: DZ
authors.lastname: Du
authors.forename: Ker-I
authors.initials: KI
authors.lastname: Ko
authors.forename: Guohui
authors.initials: G
authors.lastname: Lin
mesh_terms: D019295:Computational Biology / Q000379:methods*; D015723:Gene Library; D006801:Humans