摘要
The simplified partial digest problem (SPDP) models an effective and robust method for building physical maps using restriction site analysis. Blazewicz and Kasprzak proved that SPDP is NP-hard. The best-known solution for SPDP is an O(n1.52n/2)-time backtracking algorithm, where n is the number of sites. Blazewicz et al. had an O(n2q)-time dynamic programming algorithm, where q≤n+1 is the number of distinct intersite distances. When q is small, their algorithm solves SPDP efficiently. We give a new dynamic programming algorithm that requires O(qn(n/q+1)q−1) time. This time complexity is O(nq) for any q and is better than O(n1.52n/2) when q≤n/6. For example, for q=n/7, the running time is O(n223n/7). We also give an O(nlgn)-time algorithm for q=2. This result improves the previous upper bound of O(n4) and solves an open problem by Blazewicz and Kasprzak.
