title: Dealing with errors in interactive sequencing by hybridization.
abstract: 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.
authors.affiliation: Department of Computer Science, State University of New York, Stony Brook, NY 11794-4400, USA.
authors.forename: V T
authors.initials: VT
authors.lastname: Phan
authors.forename: S S
authors.initials: SS
authors.lastname: Skiena
mesh_terms: 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*
chemical_list: D015345:Oligonucleotide Probes