Bioinformatics Vol. 17 no. 10 2001
Pages 862-870
© 2001 Oxford University Press
Dealing with errors in interactive sequencing by hybridization
Department of Computer Science, State University of New York, Stony Brook, NY 11794-4400, USA
Received on April 20, 2001
; revised on July 2, 2001
; accepted on July 2, 2001
Motivation: 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.
Availability: Freely available upon request.
Contact: skiena{at}cs.sunysb.edu
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  J. Blazewicz, C. Oguz, A. Swiercz, and J. Weglarz DNA Sequencing by Hybridization via Genetic Search Operations Research, November 1, 2006; 54(6): 1185 - 1192. [Abstract] [PDF]
|
|