Dealing with errors in interactive sequencing by hybridization.
BACKGROUND
A realistic approach to sequencing by hybridization must deal with realistic sequencing errors. The results of such a method can surely be applied to similar sequencing tasks.


RESULTS
We provide the first algorithms for interactive sequencing by hybridization which are robust in the presence of hybridization errors. Under a strong error model allowing both positive and negative hybridization errors without repeated queries, we demonstrate accurate and efficient reconstruction with error rates up to 7%. Under the weaker traditional error model of Shamir and Tsur (Proceedings of the Fifth International Conference on Computational Molecular Biology (RECOMB-01), pp 269-277, 2000), we obtain accurate reconstructions with up to 20% false negative hybridization errors. Finally, we establish theoretical bounds on the performance of the sequential probing algorithm of Skiena and Sundaram (J. Comput. Biol., 2, 333-353, 1995) under the strong error model.


BACKGROUND
Freely available upon request.


BACKGROUND
skiena@cs.sunysb.edu.
Phan
V T
VT
Department of Computer Science, State University of New York, Stony Brook, NY 11794-4400, USA.
Skiena
S S
SS
D000465:Algorithms; D019295:Computational Biology; D005188:False Negative Reactions; D005189:False Positive Reactions; D015233:Models, Statistical; D009693:Nucleic Acid Hybridization; D015345:Oligonucleotide Probes; D017422:Sequence Analysis, DNA / Q000379:methods / Q000706:statistics & numerical data*
D015345:Oligonucleotide Probes