Sequencing by hybridization in the presence of hybridization errors

DNA sequencing is a very important problem in genomics. Several different sequencing methods are currently utilized. One promising method uses a sequencing chip to obtain information about the presence of subsequences in DNA. This paper deals with sequencing of hybridization data from a sequencing chip, called Sequencing by Hybridization (SBH). Preparata et al. proposed a new sequencing chip using universal bases, together with a new sequencing algorithm, and showed that its performance is significantly better than the standard scheme based on oligomer probes. However, the presence of errors in the sequencing chip was not considered, and the method of Preparata et al. cannot be used directly in practice. This paper proposes sequencing algorithms in the presence of hybridization errors for their sequencing chip and applies these algorithms to random data in the presence of random errors. Computational results show that false negative errors have larger effects on the rates of correct reconstruction than do false positive errors. Our extended sequencing algorithms are useful when there are a few hybridization errors.