title: Sequencing by hybridization in the presence of hybridization errors.
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.
authors.affiliation: Department of Information Science, Graduate School of Science, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033, Japan. doi@is.s.u-tokyo.ac.jp
authors.forename: K
authors.initials: K
authors.lastname: Doi
authors.forename: H
authors.initials: H
authors.lastname: Imai
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D015336:Molecular Probe Techniques; D009693:Nucleic Acid Hybridization; D020411:Oligonucleotide Array Sequence Analysis / Q000706:statistics & numerical data*; D015345:Oligonucleotide Probes; D017422:Sequence Analysis, DNA / Q000379:methods* / Q000706:statistics & numerical data
chemical_list: D015345:Oligonucleotide Probes