Tech Report CS-99-07

An Experimental Study of SBH with Gapped Probes

Benoit Hudson

April 1999


Sequencing by Hybridization (SBH) has been proposed as a means of automating the task of DNA sequencing. The original SBH proposal was able to sequence DNA of length about $2^k$ nucleotides with a cost $O(4^k)$ (in linear time). Preparata and Upfal have recently proposed a new method, which was predicted to be able to sequence DNA of length $O(4^k)$, still for a cost $O(4^k)$. This work describes a simulation of the method developed to test the theoretical results.

(complete text in pdf or gzipped postscript)