J. Blazewicz, M. Kasprzak,
"Complexity of DNA sequencing by hybridization",
Theoretical Computer Science 290, 2003, pp. 1459-1473.
Download full text
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.
Back to the List of publications
22 Jan 2003