Speeding Up the Partial Digest Algorithm

Authors

  • Hazem M. Bahig College of Computer Science and Engineering, Hail University, Hail, Kingdom of Saudi Arabia; Computer Science Division, Department of Mathematics, Faculty of Science, Ain Shams University, Cairo, Egypt
  • Mostafa M. Abbas Qatar Computing Research institute, Hamad Bin Khalifa University, Doha

DOI:

https://doi.org/10.26713/jims.v10i1-2.611

Keywords:

Partial digest problem, Exact algorithms, DNA

Abstract

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.

Downloads

Download data is not yet available.

References

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.

Downloads

Published

2018-08-10
CITATION

How to Cite

Bahig, H. M., & Abbas, M. M. (2018). Speeding Up the Partial Digest Algorithm. Journal of Informatics and Mathematical Sciences, 10(1-2), 217–225. https://doi.org/10.26713/jims.v10i1-2.611

Issue

Vol. 10 No. 1-2 (2018)

Section

Research Articles

License

Authors who publish with this journal agree to the following terms:
  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a CCAL that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.