Sequencing by Hybridization with Positive Faults

Jacek Blazewicz[1] (
Piotr Formanowicz[1] (
Marta Kasprzak[1] (
Wojciech T. Markiewicz[2] (
Jan Weglarz[2] (

[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


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