Abstract
The partial digest problem, PDP, is one of the methods used in restriction mapping to characterize a fragment of DNA. The main challenge of PDP is the exponential time for the best exact sequential algorithm in the worst case. In this paper, we reduce the running time for generating the solution of PDP by designing an efficient parallel algorithm. The algorithm is based on parallelizing the fastest sequential algorithm for PDP. The experimental study on a multicore system shows that the running time of the proposed algorithm decreases with the number of processors increases. Also, the speedup achieved good scales with increase in the number of processors.