Optimal reconstruction of a sequence from its probes.
An important combinatorial problem, motivated by DNA sequencing in molecular biology, is the reconstruction of a sequence over a small finite alphabet from the collection of its probes (the sequence spectrum), obtained by sliding a fixed sampling pattern over the sequence. Such construction is required for Sequencing-by-Hybridization (SBH), a novel DNA sequencing technique based on an array (SBH chip) of short nucleotide sequences (probes). Once the sequence spectrum is biochemically obtained, a combinatorial method is used to reconstruct the DNA sequence from its spectrum. Since technology limits the number of probes on the SBH chip, a challenging combinatorial question is the design of a smallest set of probes that can sequence an arbitrary DNA string of a given length. We present in this work a novel probe design, crucially based on the use of universal bases [bases that bind to any nucleotide (Loakes and Brown, 1994)] that drastically improves the performance of the SBH process and asymptotically approaches the information-theoretic bound up to a constant factor. Furthermore, the sequencing algorithm we propose is substantially simpler than the Eulerian path method used in previous solutions of this problem.
Frieze
A M
AM
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA. af1p@andrew.cmu.edu
Preparata
F P
FP
Upfal
E
E
D000465:Algorithms; D015195:Drug Design; D005069:Evaluation Studies as Topic; D015233:Models, Statistical; D015335:Molecular Probes; D020411:Oligonucleotide Array Sequence Analysis / Q000379:methods* / Q000706:statistics & numerical data; D017422:Sequence Analysis, DNA / Q000379:methods* / Q000706:statistics & numerical data
D015335:Molecular Probes