Sequential algorithms for DNA sequencing
Błażewicz Jacek, Kaczmarek Janusz, Kasprzak Marta, Węglarz Jan, Markiewicz Wojciech T.
Institute of Computing Science, Poznań University of Technology
ul. Piotrowo 3a, 60-965 Poznań, Poland
{blazewic | janusz | marta | węglarz}@cs.put.poznan.plInstitute of Bioorganic Chemistry, Polish Academy of Sciences
ul. Noskowskiego 12/14, 61-704 Poznań, Poland
markwt@ibch.poznan.pl
DOI: 10.12921/cmst.1996.01.01.31-42
OAI: oai:lib.psnc.pl:467
Abstract:
Reconstruction of the original DNA sequence in sequencing by hybridization approach (SBH) due to a large number of possible combinations requires a computational support. In the paper, a new method of sequencing has been proposed. Two algorithms based on its idea have been implemented and tested: for the case of an ideal hybridization experiment (complete data) and for more general case, when some data are missing, like in the real experiment. Authentic DNA sequences have been used for testing. A parallel version of the second algorithm has been also implemented and tested. The quality of the reconstruction is satisfactory for the library of oligunucleotides of length 9, and 100, 200 and 300-bp long sequences. A way to a further decrease of the computation time is also suggested,
Key words:
DNA sequencing, oligonucleotide hybridization, parallel computing, sequencing by hybridization
Reconstruction of the original DNA sequence in sequencing by hybridization approach (SBH) due to a large number of possible combinations requires a computational support. In the paper, a new method of sequencing has been proposed. Two algorithms based on its idea have been implemented and tested: for the case of an ideal hybridization experiment (complete data) and for more general case, when some data are missing, like in the real experiment. Authentic DNA sequences have been used for testing. A parallel version of the second algorithm has been also implemented and tested. The quality of the reconstruction is satisfactory for the library of oligunucleotides of length 9, and 100, 200 and 300-bp long sequences. A way to a further decrease of the computation time is also suggested,
Key words:
DNA sequencing, oligonucleotide hybridization, parallel computing, sequencing by hybridization
