Sequencing by Hybridization (SBH) is a challenging alternative to the classical DNA sequencing methods. Remarkable growth of interest in SBH has already led to building the first sequencing chip, reading the first 100 bp by SBH and developing a photolithographic technique for building high-capacity sequencing chips. Some unsolved computer science problems seriously slow down the development of biochemical and instrumentation aspects of SBH. In close collaboration with biology and instrumentation SBH groups, the following computer science problems have been identified and are addressed by this project: (a) algorithms for sequence reconstruction by optimized chips, (b) algorithms to optimally choose additional biochemical experiments for SBH, (c) algorithms to eliminate ``blind'' choice of PCR primers by SBH data and reduce the amount of conventional sequencing in molecular evolution studies, and (d) algorithms to combine small-scale SBH and primer walking DNA sequencing and to parallelize ordered sequencing strategies.
