An algorithm for isothermic DNA sequencing

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

Abstrakty

EN

In the paper, the problem of isothermic DNA sequencing by hybridization, without any errors in its input data, is presented and an exact polynomial-time algorithm solving the problem is described. The correctness of the algorithm is confirmed by an enumerative proof.

Słowa kluczowe

EN

computational molecular biology; DNA sequencing by hybridization

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2004
• Tom: Vol. 52, nr 1
• Strony: 31--35
• Opis fizyczny: Bibliogr. 16 poz.,

Twórcy

autor

Kasprzak M.

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

Bibliografia

• [1] W. Bai ns and G. C. Smith, “A novel method for nuclei cacid sequence determination”, J. Theor. Biol. 135, 303–307 (1988).
• [2] 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”, Dokl. Akad. Nauk SSSR 303, 1508–1511 (1988).
• [3] E. M. Southern, United Kingdom Patent Application GB8810400 (1988).
• [4] 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).
• [5] A. Apostolico and R. Giancarlo, “Sequence alignment in molecular biology”, in: Mathematical Support for Molecular Biology, ed.: M. Farach, F. Roberts, M. Waterman, Am. Math. Soc. DIMACS (1997).
• [6] J. Błażewicz, P. Formanowicz, M. Kasprzak, W. T. Markiewicz and J. Węglarz, “DNA sequencing with positive and negative errors”, J. Comput. Biol. 6, 113–123 (1999).
• [7] A. Guenoche, “Can we recover a sequence, just knowing all its subsequences of given length?”, CABIOS 8, 569–574 (1992).
• [8] J. Setubal and J. Meidanis, Introduction to Computational Molecular Biology, Boston: PWS Publishing Company, (1997).
• [9] M. S. Waterman, Introduction to Computational Biology. Maps, Sequences and Genomes, London: Chapman & Hall, (1995).
• [10] P. A. Pevzner, “l-tuple DNA sequencing: computer analysis”, J. Biomol. Struct. Dyn. 7, 63–73 (1989).
• [11] J. Błażewicz and M. Kasprzak, “Complexity of DNA sequencing by hybridization”, Theor. Comp. Sci. 290, 1459–1473 (2003).
• [12] J. Błażewicz, P. Formanowicz, M. Kasprzak and W. T. Markiewicz, “Sequencing by hybridization with isothermic oligonucleotide libraries”, Disc. Applied Math., to be published.
• [13] R. B. Wallace, M. J. Johnson, T. Hi orse, T. Mi ayke, E. H. Kawashima and K. Itakura, “The use of synthetic oligonucleotides as hybridization probes. Hybridization of oligonucleotides of mixed sequence to rabbit beta-globin DNA”, Nucl. Acids Res. 9, 879–894 (1981).
• [14] J. Błażewicz, A. Hertz, D. Kobler and D. de Werra, “On some properties of DNA graphs”, Disc. Applied Math. 98, 1–19 (1999).
• [15] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Berlin: Springer-Verlag, 2001.
• [16] E. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, New York: Rinehart and Winston, 1976.