Complexity of DNA sequencing by hybridization
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. (C) 2002 Elsevier Science B.V. All rights reserved.
dna sequencing computational complexity computational biology