Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420479 | Discrete Applied Mathematics | 2009 | 7 Pages |
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 ρ=136.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jacek Blazewicz, Edmund K. Burke, Marta Kasprzak, Alexandr Kovalev, Mikhail Y. Kovalyov,