Complexity of DNA sequencing by hybridization |
| |
| Authors: | Jacek B
a
ewicz Marta Kasprzak |
| |
| Affiliation: | 1. Institute of Computing Science, Poznań University of Technology, ul. Piotrowo 3A, 60-965 Poznań, Poland;2. Institute of Bioorganic Chemistry, Polish Academy of Sciences, Noskowskiego 12/14, 61-704 Poznań, Poland |
| |
| Abstract: | In the paper, the question of the complexity of the combinatorial part of the DNA sequencing by hybridization, is analyzed. Subproblems of the general problem, depending on the type of error (positive, negative), are distinguished. Since decision versions of the subproblems assuming only one type of error are trivial, complexities of the search counterparts are studied. Both search subproblems are proved to be strongly NP-hard, as well as their uniquely promised versions. |
| |
| Keywords: | DNA sequencing Computational complexity Computational biology |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
