Computational complexity of isothermic DNA sequencing by hybridization |
| |
Authors: | Jacek Blazewicz Marta Kasprzak |
| |
Institution: | a Institute of Computing Science, Poznan University of Technology, Poznan, Poland b Institute of Bioorganic Chemistry, Polish Academy of Sciences, Poznan, Poland |
| |
Abstract: | In the paper, the computational complexity of several variants of the problem of isothermic DNA sequencing by hybridization, is analyzed. The isothermic sequencing is a recent method, in which isothermic oligonucleotide libraries are used during the hybridization with an unknown DNA fragment. The variants of the isothermic DNA sequencing problem with errors in the hybridization data, negative ones or positive ones, are proved to be strongly NP-hard. On the other hand, the polynomial time algorithm for the ideal case with no errors is proposed. |
| |
Keywords: | DNA sequencing Computational complexity Eulerian path |
本文献已被 ScienceDirect 等数据库收录! |
|