Computational Aspects of DNA Sequencing by Hybridization : a Survey

• Autorzy: Kwarciak K. , Radom M. , Formanowicz P.

Identyfikatory

DOI

10.12921/cmst.2018.0000055

• Języki publikacji: EN

Abstrakty

EN

Sequencing by hybridization (SBH) is a method of reading DNA sequence from its smaller fragments. Such a method has been proposed in late 1980s and until the emergence of the new generation sequencing it has been widely used and improved. Since the initial, classical approach to SBH, many modifications and enhancements was proposed, aimed at improving the preciseness and the length of sequences which can be unambiguously read. Even now, for some DNA sequences sequencing by hybridization can still be used effectively and at a low cost. In this paper many different approaches to the SBH will be described, mainly from the points of view of algorithms and computational complexity.

Słowa kluczowe

EN

DNA sequencing; hybridization error; algorithm; computational complexity

• Wydawca: Institute of Bioorganic Chemistry Scientific Publishers OWN, Polish Academy of Sciences
• Czasopismo: Computational Methods in Science and Technology
• Rocznik: 2018
• Tom: Vol. 24, No. 4
• Strony: 259--271
• Opis fizyczny: Bibliogr. 51 poz., tab.

Twórcy

autor

Kwarciak K.

• Institute of Computing Science Poznan University of Technology

autor

Radom M.

• Institute of Computing Science Poznan University of Technology
• Institute of Bioorganic Chemistry Polish Academy of Sciences

autor

Formanowicz P.

• Institute of Computing Science Poznan University of Technology
• Institute of Bioorganic Chemistry Polish Academy of Sciences

Bibliografia

• [1] J.T. Bosh and W. Grody, Keeping up with the next generation: massively parallel sequencing in clinical diagnostics, The Journal of Molecular Diagnostics 10(6), 484–492 (2008).
• [2] A. Pihlak, G. Baurén, E. Hersoug, P. Lönnerberg, A. Metsis, S. Linnarsson, Rapid genome sequencing with short universal tiling probes., Nature biotechnology 26, 676–684 (2008).
• [3] J. Hardick, R. Woelfel, W. Gardner, S. Ibrahim, Sequencing ebola and marburg viruses genomes using microarrays, Journal of Medical Virology 88(8), 1303–1308 (2016).
• [4] V. Swaminathan, G. Rajaram, V. Abhishek, B.S. Reddy, K. Kannan, A novel hypergraph-based genetic algorithm (hgga) built on unimodular and anti-homomorphism properties for DNA sequencing by hybridization, Interdisciplinary Sciences: Computational Life Sciences, 2017.
• [5] J. Błażewicz and M. Kasprzak, Complexity of DNA sequencing by hybridization, Theoretical Computer Science 290(3), 1459–1473 (2003).
• [6] P. Pevzner, l-tuple DNA sequencing: a computer analysis, Journal Of Biomolecular Structure & Dynamics 7, 63–73 (1989).
• [7] J. Błażewicz, P. Formanowicz, M. Kasprzak, P. Schuurman, G. Woeginger, A polynomial time equivalence between DNA sequencing and the exact perfect matching problem, Discrete Optimization 7, 154–162 (2007).
• [8] D.MargaritisandS.Skiena,Reconstructingstringsfromsubstrings in rounds, Proceedings 36th Symposium on Foundation of Computer Science 6(2), 237–252 (1995).
• [9] S. Skiena and G. Sundaram, Reconstructing strings from substrings, Journal of Computational Biology 2, 333–353 (1995).
• [10] S.Kruglyak,Multistagesequencingbyhybridization,Journal of Compytational Biology 71, 165–171 (1998).
• [11] A. Frieze and B. Halldorsson, Optimal sequencing by hybridization in rounds, Journal of Computational Biology 9, 355–369 (2002).
• [12] D. Tsur, Sequencing by hybridization in few rounds, Lecture Notes in Computer Science, Algorithms – ESA 2003 2832, 506–516 (2003).
• [13] S. Broude, T. Sano, C. Smith, C. Cantor, Enhanced DNA sequencing by hybridization, Proceedings of National Academy of Science USA 91, 3072–3076 (1994).
• [14] S. Hannenhalli, P. Pevzner, H. Levis, S. Skiena, Positional sequencing by hybridization, Computer Applications in Biosciences 12, 19–24 (1996).
• [15] A. Ben-Dor, I. Pe’er, R. Shamir, R. Sharan, On the complexity of positional sequencing by hybridization, Journal of Computational Biology 8, 361–371 (2001).
• [16] J.-H. Zhang, L.-Y. Wu, Y.-Y. Zhao, X.-S. Zhang, An optimization approach to the reconstruction of positional DNA sequencing by hybridization with errors, European Journal of Operational Research 182(1), 413–427 (2007).
• [17] J. Błażewicz, F. Glover, M. Kasprzak, Evolutionary approaches to DNA sequencing with errors, Annals of Operations Reasearch 138(1), 67–78 (2005).
• [18] J. Błażewicz, M. Kasprzak, W. Kuroczycki, Hybrid genetic algorithm for DNA sequencing with errors, Journal of Heuristics 8(5), 495–502 (2002).
• [19] J. Błażewicz, F. Glover, M. Kasprzak, DNA sequencing – tabu and scatter search combined, INFORMS Journal on Computing 16(3), 232–240 (2004).
• [20] J. Błażewicz, F. Glover, M. Kasprzak, W.T. Markiewicz, C. Oguz, D. Rebholz-Schuhmann, A. Świercz, Dealing with repetitions in sequencing by hybridization, Computational Biology and Chemistry 30(5), 313–320 (2006).
• [21] J. Błażewicz, C. Oguz, A. Świercz, J. We ̨glarz, DNA sequencing by hybridization via genetic search, Operations Research 54(6), 1185–1192 (2006).
• [22] J.-H. Zhang, L.-Y. Wu, X.-S. Zhang, Reconstruction of DNA sequencing by hybridization, Bioinformatics 19(1), 14–21 (2003).
• [23] P. Formanowicz, DNA sequencing by hybridization with additional information available, Computational Methods in Science and Technology 11(1), 21–29 (2005).
• [24] M. Schena, Microarray Analysis. Hoboken, New Jersey: Wiley-Liss, 2003.
• [25] P. Formanowicz, Isothermic sequencing by hybridization problems with information about repetitions, Electrical Review 9, 103–107 (2008).
• [26] K. Kwarciak, M. Radom, P. Formanowicz, DNA sequencing with negative errors and information about repetitions, Zeszyty Naukowe Politechniki Śla ̨skiej: Automatyka 151, 215–222 (2008).
• [27] K.KwarciakandP.Formanowicz,Agreedyalgorithmforthe DNA sequencing by hybridization with positive and negative errors and information about repetitions, Bulletin of the Polish Academy od Sciences, Technical Sciences 51(1), 111– 115 (2011).
• [28] K.KwarciakandP.Formanowicz,Tabusearchalgorithmfor DNA sequencing by hybridization with multiplicity information available, Computers and Operations Research 47, 1–10 (2014).
• [29] K. Kwarciak, M. Radom, P. Formanowicz, A multilevel ant colony optimization algorithm for DNA sequencing by hybridization with multiplicity information available. in press, 2015.
• [30] C.Blum,M.Y.Vallès,M.J.Blesa,Anantcolonyoptimization algorithm for DNA sequencing by hybridization, Computers and Operations Research 35(11), 3620–3635 (2008).
• [31] The Chimpanzee Sequencing and Analysis Consortium, Initial sequence of the chimpanzee genome and comparison with the human genome, Nature 437, 69–97 (2005).
• [32] I. Pe’er and R. Shamir, Spectrum alignment: Efficient resequencing by hybridization, in Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, pp. 260–268, AAAI Press, 2000.
• [33] I. Pe’er, N. Arbili, R. Shamir, A computational method for resequencing long DNA targets by universal oligonucleotide arrays, Proceedings of the National Academy of Sciences, vol. 99, no. 24, pp. 15492–15496, 2002.
• [34] M. Cargill, D. Altshuler, J. Ireland, P. Sklar, K. Ardlie, N. Patil, C.R. Lane, E.P. Lim, N. Kalyanaraman, J. Nemesh, L. Ziaugra, L. Friedland, A. Rolfe, J. Warrington, R. Lipshutz, G.Q. Daley, E.S. Lander, Characterization of singlenucleotide polymorphisms in coding regions of human genes, Nature Genetics 22, 231–238 (1999).
• [35] J.G. Hacia, Resequencing and mutational analysis using oligonucleotide microarrays, Nature Genetics 21, 42–47 (1999).
• [36] K.L. Gunderson, X.C. Huang, M.S. Morris, R.J. Lipshutz, D.J. Lockhart, M.S. Chee, Mutation detection by ligation to complete n-mer DNA arrays., Genome Res 8(11), 1142– 1153 (1998).
• [37] N.J. Haslam, N.E. Whiteford, G. Weber, A. Prugel-Bennet, J.W. Essex, C. Neylon, Optimal probe length varies for targets with high sequence variation: Implications for probe library design for resequencing highly variable genes, PLOS One 3(6), e2500 (2008).
• [38] I. Peer, N. Arbili, Y. Liu, C. Enck, C.A. Gelfand, R. Shamir, Advanced computational techniques for re-sequencing DNA with polymerase signaling assay arrays, Nucleic Acids Research 31(19), 5667–5675 (2003).
• [39] M.T. Boyce-jacino, M.B. Addelston, S.R. Head, Polymerase signaling assay, http://www.freepatentsonline.com/ 6872521.html, March 2005.
• [40] P. Pevzner and R. Lipshutz, Towards DNA sequencing chips, Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 841, 143–158 (1994).
• Symposium on Mathematical Foundations of Computer Science 841, 143–158 (1994).
• [41] M. Radom and P. Formanowicz, Algorithms for sequencing by hybridization problems based on non-classical DNA chips, Przeglad Elektrotechniczny 10, 97–100 (2010).
• [42] M.RadomandP.Formanowicz,Analgorithmforsequencing by hybridization based on an alternating DNA chip, Computational Biology and Chemistry 10(3), 67–78 (2018).
• [43] P. Zhang, M. Egholm, N. Paul, M. Pingle, D. Bergstrom, Peptide nucleic acid-DNA duplexes containing the universal base 3-nitropyrrole, Methods 23, 132–140 (2001).
• [44] K. Too and D. Loakes, Universal Base Analogues and their Applications to Biotechnology. Wiley-VCH Verlag GmbH and Co. KGaA, 2008.
• [45] A. Frieze, F. Preparata, E. Upfal, Optimal reconstruction of a sequence from its probes, Journal of Computational Biology 6, 361–368 (1999).
• [46] F. Preperata and J. Oliver, DNA sequencing by hybridization using semi-degeneratae bases, Journal of Computational Biology 11, 753–765 (2004).
• [47] P. Sachadyn and J. Kur, Reducing the number of microlocations in oligonucleotide microchip matrices by the application of degenerate oligonucleotides, Journal of Computational Biology 197, 393–401 (1999).
• [48] J. Błażewicz, P. Formanowicz, M. Kasprzak, W. Markiewicz,Sequencing by hybridization with isothermic oligonucleotide libraries, Discrete Applied Mathematics 145, 40–51 (2004).
• [49] J. Błażewicz and M. Kasprzak, Computational complexity of isothermic DNA sequencing by hybridization, Discrete Applied Mathematics 154, 718–729 (2006).
• [50] J. Błażewicz, P. Formanowicz, M. Kasprzak, W. Markiewicz,A. Świercz, Tabu search algorithm for DNA sequencing by hybridization with isothermic libraries, Computational Biology and Chemistry 28, 11–19 (2004).
• [51] J. Błażewicz, P. Formanowicz, Multistage isothermic sequencing by hybridization, Computational Biology and Chemistry 29, 69–77 (2005).

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).