Sequencing-by-hybridization at the information-theory bound: An optimal algorithm

In a recent paper (Preparata et at, 1999) we introduced a novel probing sch eme for DNA sequencing by hybridization (SBH), The new gapped-probe scheme combines natural and universal bases in a well-defined periodic pattern. It has been shown (Preparata et al,, 1999) that the performance of the gapped -probe scheme (in terms of the length of a sequence that can be uniquely re constructed using a given size library of probes) is significantly better t han the standard scheme based on oligomer probes, In this paper we present and analyze a new, more powerful, sequencing algorithm for the gapped-probe scheme. We prove that the new algorithm exploits the full potential of the SBH technology with high-confidence performance that comes within a small constant factor (about 2) of the information-theory bound, Moreover, this p erformance is achieved while maintaining running time linear in the target sequence length.