J. Blazewicz, M. Kasprzak,
"Complexity of DNA sequencing with errors", Poznan Supercomputing
and Networking Center report RA-001/99, 1999.
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 types of errors (positive, negative),
are distinguished. Since decision versions of the subproblems assuming
only one type of errors are trivial, complexities of the search counterparts
are studied. Both search subproblems are proved to be strongly NP-hard,
the result for only positive errors being somewhat surprising, provided
a very good behavior of the exact algorithm in this case.
Back to the List of publications
5 Feb 1999