A greedy algorithm for the DNA sequencing by hybridization with positive and negative errors and information about repetitions

• Autorzy: Kwarciak K. , Formanowicz P.
• Języki publikacji: EN

Abstrakty

EN

In this paper a greedy algorithm for some variants of the sequencing by hybridization method is presented. In the standard version of the method information about repetitions is not available. In the paper it is assumed that a partial information of this type is a part of the problem instance. Here two simple but realistic models of this information are taken into consideration. The first one assumes it is known if a given element of a spectrum appears in the target sequence once or more than once. The second model uses the knowledge is a given element of a spectrum occurs in the analyzed sequence once, twice or at least three times. The proposed greedy algorithm solves the variant of the problem with positive and negative errors. Results of a computational experiment are reported which, among others, confirm that the additional information leads to the improvement of the obtained solutions. They also show that the more precise model of information increases the quality of reconstructed sequences.

Słowa kluczowe

EN

DNA sequencing; l-mer multiplicity; greedy algorithm; combinatorial problems

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2011
• Tom: Vol. 59, nr 1
• Strony: 111--115
• Opis fizyczny: Bibliogr. 10 poz., rys., tab.

Twórcy

autor

Kwarciak K.

autor

Formanowicz P.

• Poznan University of Technology, Institute of Computing Science, Piotrowo 2, 60-965 Poznań, Poland,

Bibliografia

• [1] W. Bains and G.C. Smith, “A novel method for nucleic acid sequence determination”, J. Theoretical Biology 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”, Doklady Akademii Nauk SSSR 303, 1508–1511 (1988).
• [3] A.C. Pease, D. Solas, E.J. Sullivan, M.T. Cronin, C.P. Holmes, and S.P. Fodor, “Light-generated oligonucleotide arrays for rapid DNA sequence analysis” Proc. National Academy of Science USA 91, 5022–5026 (1994).
• [4] P.A. Pevzner, Computational Molecular Biology. An Algorithmic Approach, The MIT Press, Cambridge, 2000.
• [5] P. Formanowicz, “DNA sequencing by hybridization with additional information available”, Computational Methods in Science and Technology 11, 21–29 (2005).
• [6] P. Formanowicz, Selected Combinatorial Aspects of Biological Sequence Analysis, Poznań University of Technology Publishing House, Poznań, 2005.
• [7] J. Błażewicz and M. Kasprzak, “Complexity of DNA sequencing by hybridization”, Theoretical Computer Science 290, 1459–1473 (2003).
• [8] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, Scientific-Technical Publishing House, Warszawa, 2005.
• [9] J. Błażewicz, P. Formanowicz, M. Kasprzak, W.T. Markiewicz, and J. Węglarz, “DNA sequencing with positive and negative errors”, J. Computational Biology 6, 113–123 (1999).
• [10] T.F. Smith and M.S. Waterman, “Identification of common molecular subsequences”, J. Molecular Biology 147, 195-–197 (1981).