J. Blazewicz, M. Kasprzak,
"Computational complexity of isothermic DNA sequencing by hybridization",
Discrete Applied Mathematics 154 (2006) 718-729.
Download full text
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.
Back to the List of publications
6 Mar 2006