On the link between DNA sequencing and graph theory

• Autorzy: Kasprzak M.
• Języki publikacji: EN

Abstrakty

EN

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.  

• Wydawca: Institute of Bioorganic Chemistry Scientific Publishers OWN, Polish Academy of Sciences
• Czasopismo: Computational Methods in Science and Technology
• Rocznik: 2004
• Tom: Vol. 10, nr 1
• Strony: 39--47
• Opis fizyczny: Bibliogr. 21 poz., rys.

Twórcy

autor

Kasprzak M.

• Institute of Computing Science, Poznań University of Technology, Piotrowo 3A, 60-965 Poznań, Poland,

Bibliografia

• [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).