On the parameterized complexity of pooling design

Area of Science:

• Computational Biology
• Bioinformatics
• Algorithm Analysis

Background:

• DNA library screening is crucial for gene function studies.
• Pooling designs reduce the number of tests required.
• Key problems involve determining d-separability (or d-disjunctness) of binary matrices.

Purpose of the Study:

• To investigate the existence of efficient algorithms for d-separability problems when d is small.
• To analyze the parameterized complexity of these pooling design problems with d as the parameter.

Main Methods:

• Parameterized complexity analysis.
• Investigating coNP-complete problems with a focus on the parameter d.
• Proving co-W[2]-completeness for the parameterized versions of the three pooling design problems.

Main Results:

• The parameterized versions of the three d-separability problems are co-W[2]-complete.
• This implies that efficient (f(d) x (mn)^O(1)) deterministic algorithms are not expected for small d.

Conclusions:

• No efficient deterministic algorithms can be expected for solving d-separability problems in DNA library screening when d is small.
• The co-W[2]-completeness result provides a theoretical barrier to developing such algorithms.