On the hardness of counting and sampling center strings

Area of Science:

• Computational complexity theory
• Bioinformatics algorithms
• Stringology

Background:

• The Closest String problem seeks a central string within a defined Hamming distance 'd' from all strings in a set 'S'.
• Efficiently solving this problem is crucial for various applications, including DNA sequence alignment and data compression.

Purpose of the Study:

• To analyze the computational complexity of the #CLOSEST STRING problem, which counts the number of such center strings.
• To investigate the feasibility of exact and approximate solutions, as well as uniform random sampling of center strings.

Main Methods:

• The study employs theoretical computer science techniques, including reductions and complexity analysis.
• It explores parameterized complexity by fixing one of the input parameters (n, l, or d).

Main Results:

• The #CLOSEST STRING problem is proven to be intractable for exact or polynomial-time approximate solutions.
• Fixing any single parameter (n, l, or d) allows for a fully polynomial-time randomized approximation scheme (FPRAS).
• Equivalent complexity results are established for uniformly at random sampling of center strings.

Conclusions:

• The #CLOSEST STRING problem presents significant computational challenges.
• Parameterized complexity offers a viable approach for developing approximation algorithms and efficient random sampling methods.
• These findings have implications for the practical application of closest string algorithms in fields like bioinformatics.