Distance-preserving vector space embedding for the closest string problem
Andreas Nienkötter, Xiaoyi Jiang · 2016
The closest string problem is a core problem in computational biology with applications in other fields like coding theory. Many algorithms exist to solve this problem, but due to its inherent high computational complexity (typically NP-hard), it can only be solved efficiently by restricting the search space to a specific range of parameters. Often, the run-time of these algorithms is exponential in the maximum distance between strings, restricting these solutions to very small distances. Recently, a prototype embedding method has been proposed to solve the similar generalized median problem for arbitrary objects. In this approach, objects are transformed into vector space using prototype embedding. The problem is solved in vector space and afterwards inversely transformed back into original space. This method has been successfully applied to generalized median computation in several domains where the computational complexity is inherently high. In this work, we apply prototype embedding to the closest string problem. We show that different embedding methods can result in a very good and fast approximation of the closest string, independent of the maximum distance and other parameters.