Graph reduction and its application to DNA sequence assembly

• Autorzy: Błażewicz J. , Kasprzak M.
• Języki publikacji: EN

Abstrakty

EN

The results presented here are twofold. First, a heuristic algorithm is proposed which, through removing some unnecessary arcs from a digraph, tends to reduce it into an ad joint and thus simplifies the search for a Hamiltonian cycle. Second, a heuristic algorithm for DNA sequence assembly is proposed, which uses a graph model of the problem instance, and incorporates two independent procedures of reducing the set of arcs - one of them being the former algorithm. Finally, results of tests of the assembly algorithm on parts of chromosome arm 2R of Drosophila melanogaster are presented.

Słowa kluczowe

EN

directed graphs; adjoints; Hamiltonian cycle; reduction of arcs; DNA sequence assembly; heuristics

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2008
• Tom: Vol. 56, nr 1
• Strony: 65--70
• Opis fizyczny: bibliogr. 14 poz., rys., tab.

Twórcy

autor

Błażewicz J.

autor

Kasprzak M.

• Institute of Computing Science, Poznan University of Technology, 2 Piotrowo St., 60-965 Poznan, Poland,

Bibliografia

• [1] C. Berge, Graphs and Hypergraphs, North-Holland Publishing Company, London, 1973.
• [2] J. Blazewicz, A. Hertz, D. Kobler, and D. de Werra, "On some properties of DNA graphs", Discrete Applied Mathematics 98, 1-19 (1999).
• [3] G. Chartrand and L. Lesniak, Graphs and Digraphs, Wadsworth & Brooks/Cole, Pacific Grove, 1986.
• [4] M.S. Waterman, Introduction to Computational Biology. Maps, Sequences and Genomes, Chapman & Hall, London, 1995.
• [5] J. Setubal and J. Meidanis, Introduction to Computational Molecular Biology, PWS Publishing Company, Boston, 1997.
• [6] P.A. Pevzner, Computational Molecular Biology: an Algorithmic Approach, MIT Press, Cambridge, 2000.
• [7] W. Bains and G.c. Smith, "A novel method for nucleic acid sequence determination", J. of Theoretical Biology 135,303-307 (1988).
• [8] Yu.P. Lysov, V.L. Florentiev, A.A. Khorlin, K.R. Khrapko, VV 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).
• [9] A.M. Frieze, EP. Preparata, and E. Upfal, "Optimal reconstruction of a sequence from its probes", J. of Computational Biology 6, 361-368 (1999).
• [10] J. Blazewicz, P. Formanowicz, M. Kasprzak, W.T. Markiewicz, and J. Weglarz, "DNA sequencing with positive and negative errors", J. of Computational Biology 6, 113-123 (1999).
• [11] J. Blazewicz, P. Formanowicz, E Guinand, and M. Kasprzak, "A heuristic managing errors for DNA sequencing", Bioinformatics 18, 652-660 (2002).
• [12] M.R. Garey and D.S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, San Francisco, 1979.
• [13] J. Blazewicz, M. Figlerowicz, P. Formanowicz, M. Kasprzak, B. Nowierski, R. Styszynski, L. Szajkowski, P. Widera, and M. Wiktorczyk, "Assembling the SARS-CoV genome - new method based on graph theoretical approach", Acta Biochimica Polonica 51, 983-993 (2004).
• [14] S.B. Needleman and C.D. Wunsch, "A general method applicable to the search for similarities in the amino acid sequence of two proteins",J. Molecular Biology 48, 443--453 (1970).