Speeding Up the Partial Digest Algorithm

Hazem M. Bahig, Mostafa M. Abbas


We consider the partial digest problem, which aims to find the set \(X=\{x_0, x_1,\ldots,x_n\}\) such that \(\Delta X=\{ | x_j – x_i |,\, 0\leq  i < j \leq  n\}\) is equal to the input  of the problem which is a multiset \(D=\{d_1, d_2,\ldots, d_m\}\). In bioinformatics, the lengths of DNA fragments represents the multiset \(D\), while the set of restriction site locations represents  the set \(X=\{x_0, x_1,\ldots, x_n\}\). In this paper, we study experimentally the effect of increasing and decreasing the number of levels on the breadth-breadth algorithm which is the best practical algorithm for the partial digest problem. The experimental study shows that the running time of breadth-breadth method is not the minimum time. Also, we obtained the number of levels that is used in the breadth-breadth algorithm to reduce the running time.


Partial digest problem; Exact algorithms; DNA

Full Text:



M.M. Abbas and H.M. Bahig, A fast exact sequential algorithm for the partial digest problem, BMC Bioinformatics 17 (2016), 1365.

H. Ahrabian, M. Ganjtabesh, A. Nowzari-Dalini and Z. Razaghi-Moghadam-Kashani, Genetic algorithm solution for partial digest problem, International Journal of Bioinformatics Research and Applications 9 (6) (2013), 584–594.

M. Baker, Gene-editing nucleases, Nature Methods 9 (1) (2012), 23–26.

J. Blazewicz, E.K. Burke, M. Kasprzak, A. Kovalev and M.Y. Kovalyov, Simplified partial digest problem: enumerative and dynamic programming algorithms, IEEE/ACM Transactions on Computational Biology and Bioinformatics 4 (4) (2007), 668–680.

J. Błazewicz, P. Formanowicz, M. Kasprzak, M. Jaroszewski and W.T. Markiewicz, Construction of DNA restriction maps based on a simplified experiment, Bioinformatics 17 (5) (2001), 398–404.

M. Cieliebak, S. Eidenbenz, P. Penna, Noisy Data Make the Partial Digest Problem NP-Hard, Springer, Berlin—Heidelberg (2003).

A. Daurat, Y. G´rard and M. Nivat, Some necessary clarifications about the chords’ problem and the partial digest problem, Theoretical Computer Science 347 (1-2) (2005), 432–436.

P.H. Dear, Genome Mapping, eLS (2001).

E. Fomin, A simple approach to the reconstruction of a set of points from the multiset of n2 pairwise distances in n2 steps for the sequencing problem: II Algorithm, Journal of Computational Biology 23 (2016), 1–7.

N.C. Jones and P. Pevzner, An Introduction to Bioinformatics Algorithms, MIT Press (2004).

R.M. Karp and L.A. Newberg, An algorithm for analysing probed partial digestion experiments, Computer Applications in the Biosciences 11 (3) (1995), 229–235.

P. Lemke and M. Werman, On the complexity of inverting the autocorrelation function of a finite integer sequence, and the problem of locating n points on a line, given the (nC2) unlabelled distances between them, Preprint 453 (1988).

R. Nadimi, H.S. Fathabadi and M. Ganjtabesh, A fast algorithm for the partial digest problem, Japan Journal of Industrial and Applied Mathematics 28 (2) (2011), 315–325.

P. Narayanan, Bioinformatics: A Primer, New Age International (2005).

G. Pandurangan and H. Ramesh, The restriction mapping problem revisited, Journal of Computer and System Sciences 65 (3) (2002), 526–544.

P. Pevzner, DNA physical mapping and alternating Eulerian cycles in colored graphs, Algorithmica 13 (1-2) (1995), 77–105.

J. Sambrook, E.F. Fritsch and T. Maniatis, Molecular Cloning: A Laboratory Manual, 2nd edition, Cold Spring Harbor Laboratory Press, Cold Spring Harbor, NY (1989), 1.63–1.70.

S.S. Skiena, W.D. Smith and P. Lemke, Reconstructing sets from interpoint distances, in Proceedings of the Sixth Annual Symposium on Computational Geometry, ACM (1990), 332–339.

Z. Zhang, An exponential example for a partial digest mapping algorithm, Journal of Computational Biology 1 (3) (1994), 235–239.

DOI: http://dx.doi.org/10.26713%2Fjims.v10i1-2.611

eISSN 0975-5748; pISSN 0974-875X