ON THE LINK BETWEEN DNA SEQUENCING AND GRAPH THEORY
Kasprzak Marta 1,2
1 Institute of Computing Science, Poznań University of Technology,
Piotrowo 3A, 60-965 Poznań, Poland
2Institute of Bioorganic Chemistry, Polish Academy of Sciences,
Noskowskiego 12, 61-704Poznań, Poland
marta@cs.put.poznan.pl
Received:
Rec. 20 November 2003
DOI: 10.12921/cmst.2004.10.01.39-46
OAI: oai:lib.psnc.pl:558
Abstract:
The methods cited in this paper solve the combinatorial part of DNA sequencing by
hybridization, basing on known approaches from graph theory. It is assumed here, that the length of oligonucleotides used in the hybridization experiment is constant within a library.
References:
[1] R. Arratia, D. Martin, G. Reinert, and M. S. Waterman, Poisson process approximation for
sequence repeats and sequencing by hybridization, Journal of Computational Biology 3, 425-463 (1996).
[2] W. Bains and G. C. Smith, A novel method for nucleic acid sequence determination, Journal of Theoretical Biology 135, 303-307 (1988).
[3] J. Błażewicz, P. Formanowicz, M. Kasprzak, W. T. Markiewicz, and J. Węglarz, DNA sequencing with positive and negative errors, Journal of Computational Biology 6, 113-123 (1999).
[4] J. Błażewicz, Ł. Gwóźdź, M. Kasprzak, and M. Przysucha, A comparison of two DNA sequencing methods, Computational Methods in Science and Technology 2, 17-32 (1996).
[5] J. Błażewicz, A. Hertz, D. Kobler, and D. de Werra, On some properties of DNA graphs, Discrete Applied Mathematics 98, 1-19 (1999).
[6] J. Błażewicz and M. Kasprzak, Complexity of DNA sequencing by hybridization, Theoretical
Computer Science 290, 1459-1473 (2003).
[7] R. Drmanac, I. Labat, I. Brukner, and R. Crkvenjakov, Sequencing of megabase plus DNA by
hybridization: theory of the method, Genomics 4, 114-128 (1989).
[8] M. Dyer, A. Frieze, and S. Suen, The probability of unique solution of sequencing by
hybridization, Journal of Computational Biology 1, 105-110 (1994).
[9] A. M. Frieze and B. V. Halldorsson, Optimal sequencing by hybridization in rounds, Journal of Computational Biology 9, 355-369 (2002).
[10] J. N. Hagstrom, R. Hagstrom, R. Overbeek, M. Price, and L. Schrage, Maximum likelihoodgenetic sequence reconstructionfrom oligo content, Networks 24, 297-302 (1994).
[11] R. J. Lipshutz, Likelihood DNA sequencing by hybridization, Journal of Biomolecular Structure and Dynamics 11, 637-653 (1993).
[12] Yu. P. Lysov, V. L. Florentiev, A. A. Khorlin, K. R. Khrapko, V. V. Shik, and A. D. Mirzabekov,
Determination of the nucleotide sequence of DNA using hybridization with oligonucleotides.
A new method, Doklady Akademii Nauk SSSR 303, 1508-1511 (1988).
[13] P. A. Pevzner, l-tuple DNA sequencing: computer analysis, Journal of Biomolecular, Structure and Dynamics 7, 63-73 (1989).
[14] P. A. Pevzner, Computational Molecular Biology: an Algorithmic Approach, MIT Press, Cambridge (2000).
[15] P. A. Pevzner and R. J. Lipshutz, Towards DNA sequencing chips, Lecture Notes in Computer Science 841, 143-158 (1994).
[16] V. T. Phan and S. Skiena, Dealing with errors in interactive sequencing by hybridization, Bioinformatics 17, 862-870 (2001).
[17] F. P. Preparata and E. Upfal, System and methods for sequencing by hybridization, United States Patent ApplicationUS 2001/0004728A1 (2001).
[18] J. Setubal and J. Meidanis, Introduction to Computational Molecular Biology, PWS Publishing Company, Boston (1997).
[19] R. Shamir and D. Tsur, Large scale sequencing by hybridization, Journal of Computational
Biology 9, 413-428 (2002).
[20] E. M. Southern, U. Maskos, and J. K. Elder, Analyzing and comparing nucleic acid sequences by hybridization to arrays of oligonucleotides: Evaluation using experimental models, Genomics 13, 1008-1017 (1992).
[21] M. S. Waterman, Introduction to Computational Biology. Maps, Sequences and Genomes,
Chapman & Hall, London (1995).
The methods cited in this paper solve the combinatorial part of DNA sequencing by
hybridization, basing on known approaches from graph theory. It is assumed here, that the length of oligonucleotides used in the hybridization experiment is constant within a library.
[1] R. Arratia, D. Martin, G. Reinert, and M. S. Waterman, Poisson process approximation for
sequence repeats and sequencing by hybridization, Journal of Computational Biology 3, 425-463 (1996).
[2] W. Bains and G. C. Smith, A novel method for nucleic acid sequence determination, Journal of Theoretical Biology 135, 303-307 (1988).
[3] J. Błażewicz, P. Formanowicz, M. Kasprzak, W. T. Markiewicz, and J. Węglarz, DNA sequencing with positive and negative errors, Journal of Computational Biology 6, 113-123 (1999).
[4] J. Błażewicz, Ł. Gwóźdź, M. Kasprzak, and M. Przysucha, A comparison of two DNA sequencing methods, Computational Methods in Science and Technology 2, 17-32 (1996).
[5] J. Błażewicz, A. Hertz, D. Kobler, and D. de Werra, On some properties of DNA graphs, Discrete Applied Mathematics 98, 1-19 (1999).
[6] J. Błażewicz and M. Kasprzak, Complexity of DNA sequencing by hybridization, Theoretical
Computer Science 290, 1459-1473 (2003).
[7] R. Drmanac, I. Labat, I. Brukner, and R. Crkvenjakov, Sequencing of megabase plus DNA by
hybridization: theory of the method, Genomics 4, 114-128 (1989).
[8] M. Dyer, A. Frieze, and S. Suen, The probability of unique solution of sequencing by
hybridization, Journal of Computational Biology 1, 105-110 (1994).
[9] A. M. Frieze and B. V. Halldorsson, Optimal sequencing by hybridization in rounds, Journal of Computational Biology 9, 355-369 (2002).
[10] J. N. Hagstrom, R. Hagstrom, R. Overbeek, M. Price, and L. Schrage, Maximum likelihoodgenetic sequence reconstructionfrom oligo content, Networks 24, 297-302 (1994).
[11] R. J. Lipshutz, Likelihood DNA sequencing by hybridization, Journal of Biomolecular Structure and Dynamics 11, 637-653 (1993).
[12] Yu. P. Lysov, V. L. Florentiev, A. A. Khorlin, K. R. Khrapko, V. V. Shik, and A. D. Mirzabekov,
Determination of the nucleotide sequence of DNA using hybridization with oligonucleotides.
A new method, Doklady Akademii Nauk SSSR 303, 1508-1511 (1988).
[13] P. A. Pevzner, l-tuple DNA sequencing: computer analysis, Journal of Biomolecular, Structure and Dynamics 7, 63-73 (1989).
[14] P. A. Pevzner, Computational Molecular Biology: an Algorithmic Approach, MIT Press, Cambridge (2000).
[15] P. A. Pevzner and R. J. Lipshutz, Towards DNA sequencing chips, Lecture Notes in Computer Science 841, 143-158 (1994).
[16] V. T. Phan and S. Skiena, Dealing with errors in interactive sequencing by hybridization, Bioinformatics 17, 862-870 (2001).
[17] F. P. Preparata and E. Upfal, System and methods for sequencing by hybridization, United States Patent ApplicationUS 2001/0004728A1 (2001).
[18] J. Setubal and J. Meidanis, Introduction to Computational Molecular Biology, PWS Publishing Company, Boston (1997).
[19] R. Shamir and D. Tsur, Large scale sequencing by hybridization, Journal of Computational
Biology 9, 413-428 (2002).
[20] E. M. Southern, U. Maskos, and J. K. Elder, Analyzing and comparing nucleic acid sequences by hybridization to arrays of oligonucleotides: Evaluation using experimental models, Genomics 13, 1008-1017 (1992).
[21] M. S. Waterman, Introduction to Computational Biology. Maps, Sequences and Genomes,
Chapman & Hall, London (1995).
