|
|||||
|
|
On the approximability of the Simplified Partial Digest Problem |
|
| Authors: | Jacek Blazewicz Edmund K Burke Marta Kasprzak Alexandr Kovalev Mikhail Y Kovalyov |
| Institution: | a Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland b Institute of Bioorganic Chemistry, Polish Academy of Sciences, Z. Noskowskiego 12/14, 61-704 Poznan, Poland c School of Computer Science, University of Nottingham, Jubilee Campus, Nottingham NG8 1BB, UK d Belarusian State University, Nezavisimosti 4, 220030 Minsk, Belarus e United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova 6, 220012 Minsk, Belarus |
| 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 |
| Keywords: | Genome mapping Simplified Partial Digest Computational complexity Approximation |
| 本文献已被 ScienceDirect 等数据库收录！ | |