On the approximability of the Simplified Partial Digest Problem

Citation

Blazewicz J, Burke E, Kasprzak M, Kovalev A & Kovalyov MY (2009) On the approximability of the Simplified Partial Digest Problem. Discrete Applied Mathematics, 157 (17), pp. 3586-3592. https://doi.org/10.1016/j.dam.2009.04.017

Abstract
In this paper, we analyse the computational complexity of an optimization version of the Simplified Partial Digest Problem (SPDP), which is a mathematical model for DNA mapping based on the results of a simplified partial digest experiment. We prove that recognizing 46.16% of the elements of the DNA map in the error-free simplified partial digest experiment is NP-hard in the strong sense. This implies that the problem of maximizing the number of correct elements of the DNA map in the error-free simplified partial digest experiment is pseudopolynomially non-approximable with the approximation ratio ρ=13/6.

Keywords
Genome mapping; Simplified Partial Digest; Computational complexity; Approximation

Journal
Discrete Applied Mathematics: Volume 157, Issue 17