Swiftly computing center strings

Abstract. The center string (or closest string) problem is a classical computer science problem with important applications in computational biology. Given k input strings and a distance threshold d, we search for a string within Hamming distance d to each input string. This problem is NP-complete. In this paper, we focus on exact methods for the prob-lem that are also fast in application. First, we introduce data reduction techniques that allow us to infer that certain instances have no solution, or that a center string must satisfy certain conditions. Then, we describe a novel search tree strategy that is very efficient in practice. Finally, we present results of an evaluation study for instances from a biological ap-plication. We find that data reduction is mandatory for the notoriously difficult case d = dopt − 1.