Sequencing by Hybridization
Sequencing by hybridization is a novel DNA sequencing technique in which an array (SBH chip) of short sequences of nucleotides (probes) is brought in contact with a solution of (replicas of) the target DNA sequence. A biochemical method determines the subset of probes that bind to the target sequence (the spectrum of the sequence), and a combinatorial method is used to reconstruct the DNA sequence from the 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 show in this work that the use of universal bases (bases that bind to any nucleotide) can drastically improve the performance of the SBH process. We present a novel probe design with performance that asymptotically approaches the information-theoretical bound up to a constant factor, and, for any number of probes, is significantly better than previously analyzed probe patterns. Furthermore, the sequencing algorithm we use is substantially simpler than the Eulerian path method used in previous work.
Project status: Complete
Research Areas
| Design and Analysis of Algorithms |
| Computational Biology |
Research Themes
| Applications to Medicine |
People
| Franco P. Preparata |
| Eli Upfal |
Publications
Preparata, F., Upfal, E., and Heath, S. Sequence reconstruction from nucleic acid micro-array data. In Analytical Techniques for DNA Sequencing, B. Nunnally, Ed. M. Dekker, 2005, pp. 177-193.
Sheffler, W., Upfal, E., Sedivy, J., and Noble, W. S. A learned comparative expression measure for Affymetrix GeneChip DNA microarrays. In Proceedings of the Computational Systems Bioinformatics Conference (Aug 2005), pp. 144-154.
Preparata, F., and Oliver, J. DNA sequencing-by-Hybridization using semidegenerate bases. Journal of Computational Biology 11, 4 (2004), 753-765. [ pdf ]
Preparata, F. Sequencing by Hybridization revisited: The analog-spectrum proposal. IEEE-ACM Transactions on Computational Biology and Bioinformatics 1, 1 (2004), 46-52. [ pdf ]
Preparata, F., and Upfal, E. Sequencing-by-hybridization at the information-theory bound: an optimal algorithm. In Proceedings of the Fourth Annual International Conference on Computational Molecular Biology (Tokyo, Apr 2000), pp. 245-253. [ pdf ]
Frieze, A. M., Preparata, F. P., and Upfal, E. Optimal reconstruction of a sequence from its probes. Journal of Computational Biology 6 (1999), 361-368. [ pdf ]
Preparata, F., Frieze, A., and Upfal, E. On the power of universal bases in sequencing by hybridization. In Proceedings of the Third Annual International Conference on Computational Molecular Biology (Lyon, France, Apr 1999), pp. 295-301. [ pdf ]
| Page Owner: Webmaster | Last Modified: Mon Oct 23 14:57:09 2006 |