Sequencing by Hybridization with Positive Faults

Jacek Blazewicz[1] (blazewic@sol.put.poznan.pl)
Piotr Formanowicz[1] (piotr@cs.put.poznan.pl)
Marta Kasprzak[1] (marta@cs.put.poznan.pl)
Wojciech T. Markiewicz[2] (markwt@ibch.poznan.pl)
Jan Weglarz[2] (weglarz@sol.put.poznan.pl)

[1] Institute of Computing Science, Poznan University of Technology, Piotrowo 3A, 60-965 Poznan, Poland
[2] Institute of Bioorganic Chemistry, Polish Academy of Sciences, Noskowskiego 12/14, 61-704 Poznan, Poland


Abstract

The paper is concerned with a computational phase of the sequencing DNA chains by hybridization. It is assumed that positive faults can occur in the hybridization experiment. An approach based on a reduction of the problem to a variant of a Selective Traveling Salesman Problem and an algorithm for solving the latter, have been proposed. The algorithm behaves extremely well, even for a fault rate exceeding 50%.

[ Full-text PDF | Table of Contents ]


Japanese Society for Bioinformatics