Enhanced Sequence Reconstruction with DNA Microarray Application

Abstract

DNA sequencing by hybridization is potentially a powerful alternative to standard gel electrophoresis techniques.An important aspect of the approach is the design of the probing scheme and of the associated sequence reconstruction algorithm.Recen tly a novel probing scheme, whose performance is within a constant factor of the information theory bound, has settled the issue of asymptotic optimality.Thus, the research focus has shifted to the ?ne tuning of actual performance, with enormous potential for the life sciences.In this paper we discuss a new algorithmic device, called voting upon failure, which, exploiting the knowledge acquired in the course of the sequence reconstruction process, achieves typically a 20% performance improvement over the previous best technique, and comes at 90%-con?dence within a factor 0.5 of the information-theory bound.

This work was partially supported by the National Science Foundation under Grant