Title of article :
On the approximability of the Simplified Partial Digest Problem Original Research Article
Author/Authors :
Jacek Blazewicz، نويسنده , , Edmund K. Burke، نويسنده , , Marta Kasprzak، نويسنده , , Alexandr Kovalev، نويسنده , , Mikhail Y. Kovalyov، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2009
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
Keywords :
Simplified Partial Digest , approximation , Genome mapping , Computational complexity
Journal title :
Discrete Applied Mathematics
Journal title :
Discrete Applied Mathematics
