An Exponential Example for a Partial Digest Mapping Algorithm

Abstract

ABSTRACT

The partial digest problem for small-scale DNA physical mapping is known in computer science as the turnpike reconstruction problem. Although no polynomial algorithm for this problem is known, a simple backtracking algorithm of Skiena et al. works well in practice. Weiss raises the question whether an exponential example exists for this algorithm. This paper presents such an exponential example for this backtracking algorithm.