Sequencing by Hybridization in the Presence of Hybridization Errors
Koichiro Doi(doi@is.s.u-tokyo.ac.jp)
Hiroshi Imai(imai@is.s.u-tokyo.ac.jp)
[1]Department of Information Science, Graduate School of Science,
The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033, Japan
Abstract
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.
Japanese Society for Bioinformatics