Zhang Z
Department of Computer Science and Engineering, Pennsylvania State University, University Park 16802, USA.
J Comput Biol. 1994 Fall;1(3):235-9. doi: 10.1089/cmb.1994.1.235.
The partial digest problem for small-scale DNA physical mapping is known 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.
小规模DNA物理图谱的部分酶切问题在计算机科学领域被称为高速公路重建问题。虽然目前尚未发现针对该问题的多项式算法，但Skiena等人提出的一种简单回溯算法在实际应用中效果良好。Weiss提出了一个问题，即对于该算法是否存在指数级的示例。本文给出了针对此回溯算法的一个指数级示例。
