On the Control of Hybridization Noise in DNA Sequencing-by-Hybridization


F.P Preparata  Hon-Wai, Leong  Wing-Kin, Sung  Hugo Willy



DNA sequencing-by-hybridization (SBH) is a powerful potential alternative to current sequencing by electrophoresis. Different SBH methods have been compared under the hypothesis of error-free hybridization. However both false negatives and false positive are likely to occur in practice. Under the assumption of random independent hybridization errors, Doi and Imai recently concluded that the previously reported algorithms which are asymptotically optimal in the error-free case, cannot be successfully adapted to noisy conditions. In this paper we prove that the reported dramatic drop in performance is attributable to algorithmic artifacts, and present instead an algorithm for sequence reconstruction under hybridization noise, which exhibits graceful degradation of performance as the error-rate increases. As a downside, the computational cost of sequence reconstruction rises noticeably under noisy conditions.



H.W. Leong, F.P. Preparata, W.K. Sung and H. Willy. On the control of hybridization noise in DNA Sequencing-by-Hybridization, WABI (2002).


The Simulation program implemented in JAVA is available here.