|
Published Articles >> Table of Contents >> Abstract
May/June 1999 (Vol. 1, No. 3)
pp. 33-43
Whole-Genome DNA Sequencing
Gene Myers
Full Article Text:
   
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/5992.764214
Send link to a friend
| Abstract |
|
Recent advances in DNA sequencing technology portend the determination of the complete DNA sequences of humans, mouse, and several other species of biological importance in the next five years. Sequencing DNA involves computation in an integral and potent way: the sequencing protocol affects the nature of the computation required and what can be computed constrains the nature of potential protocols. This article provides an introduction to the methods of DNA sequencing for the computational scientist, a brief survey of the algorithmic work to date, and current developments in the final push to sequence the human genome.
|
 References
|
[1] R.D. Fleischmann et al. "Whole-Genome Random Sequencing and Assembly of H. Influenzae," Science, Vol. 269, No. 5223, 1995, pp. 496-512.
[2] J. Weber and W. Myers, "Human Whole Genome Shotgun Sequencing," Genome Research, Vol. 7, No. 5, 1997, pp. 401-409.
[3] P. Green, "Against a Whole-Genome Shotgun," Genome Research, Vol. 7, No. 5, 1977, pp. 410-417.
[4] J.C. Venter et al. "Shotgun Sequencing of the Human Genome," Science, Vol. 280, No. 5369, 1998, pp. 1540-1542.
[5] F. Sanger, S. Nicklen, and A.R. Coulson, "DNA Sequencing with Chain-Terminating Inhibitors," Proc. Nat'l Academy of Science, Vol. 74, No. 12, 1974, pp. 5463-5467.
[6] A.M. Maxam and W. Gilbert, "A New Method for Sequencing DNA," Proc. Nat'l Academy of Science, No. 74, No. 2, 1997, pp. 560-564.
[7] F. Sanger et al. "Nucleotide Sequence of BacteriophageλDNA," J. Molecular Biology, Vol. 162, No. 4, 1982, pp. 729-773.
[8] L. Rowen, B.F. Koop, and L. Hood, "The Complete 685-Kilobase DNA Sequence of the Human Beta T cell Receptor Locus," Science, Vol. 272, No. 5269, 1996, pp. 1755-1762.
[9] G.I. Bell, "Roles of Repetitive Sequences," Computers Chemistry, Vol. 16, 1992, pp. 135-143.
[10] F.J.M. Iris, "Optimized Methods for Large-Scale Ssequencing in Alu-Rich Genomic Regions," Automated DNA Sequencing and Analysis, M.D. Adams, C. Fields, and J.C. Venter, eds., Academic Press, London, 1994, pp. 199-210.
[11] A. Edwards and C.T. Caskey, "Closure Strategies for Random DNA Sequencing," Methods: A Companion to Methods Enzymology, Academic Press, New York, 1991, pp. 41-47.
[12] G.G. Sutton et al., "TIGR Assembler: A New Tool for Assembling Large Shotgun Sequencing Projects," Genome Science&Technology, Vol. 1, No. 1, 1995, pp. 9-19.
[13] J.C. Roach et al., "Pairwise end Sequencing: A Unified Approach to Genomic Mapping and Sequencing," Genomics, Vol. 26, No. 26, 1995, p. 345.
[14] F. Collins and D. Galas, "A New Five-Year Plan for the U.S. Human Genome Project," Science, Vol. 262, No. 5130, 1993, pp. 43-46.
[15] M.R. Olson et al. "Random Clone Strategy for Genomic Restriction Mapping in Yeast." Proc. Nat'l Academy of Science, No. 83, No. 20, 1983, pp. 7826-7830.
[16] Y. Kohara, A. Akiyama, and K. Isono, "The Physical Map of the E. Coli Chromosome: Application of a New Strategy for Rapid Analysis and Sorting of a Large Genomic Library," Cell, Vol. 50, No. 3, 1987, pp. 495-508.
[17] A. Coulson et al., "Toward a Physical Map of the Genome of the Nematode, C. Elegans," Proc. Nat'l Academy of Science, Vol. 83, 1986, pp. 7821-7825.
[18] M.R. Olson et al., "A Common Language for Physical Mapping of the Human Genome," Science, Vol. 245, No. 4925, 1989, pp. 1434-1435.
[19] F. Alizadeh et al., "Physical Mapping of Chromosomes: A Combinatorial Problem in Molecular Biology," Algorithmica, Vol. 13, Nos. 1and 2, 1995, pp. 52-76.
[20] M. Jain and E. Myers, "Algorithms for Computing and Integrating Physical Maps Using Unique Probes," J. Computational Biology, Vol. 4, No. 4, 1997, pp. 449-466.
[21] T.J. Hudson et al., "An STS-Based Map of the Human Genome," Science, Vol. 270, No. 5244, 1995, pp. 1945-1954.
[22] J.C. Venter, H.O. Smith, and L. Hood, "A New Strategy for Genome Sequencing," Nature, Vol. 381, No. 6581, 1996, pp. 364-366.
[23] A.G. Clark et al. "Haplotype Structure and Population Genetic Inferences from Nucleotide Sequence Variation in Human Lipoprotein Lipase, American J. Human Genetics, Vol. 63, No. 2, 1998, pp. 595-612.
Additional References
[1] E. Myers, "Toward Simplifying and Accurately Formulating Fragment Assembly," J. Computational Biology, Vol. 2, No. 2, 1995, p. 275-290.
[2] H. Peltola, H. Soderlund, and E. Ukkonen, "SEQAID: a DNA Sequence Assembly Program Based on a Mathematical Model," Nucleic Acids Research, Vol. 12, No. 1, pp. 307-321.
[3] X. Huang, "A Contig Assembly Program Based on Sensitive Detection of Fragment Overlaps," Genomics, Vol. 14, 1992, pp. 18-25.
[4] J. Kececioglu and E. Myers, "Exact and Approximate Algorithms for the Sequence Reconstruction Problem," Algorithmica, Vol. 13, Nos. 1-2, 1995, pp. 7-51.
[5] E. Myers, "A Sublinear Algorithm for Approximate Keyword Matching," Algorithmica, Vol. 12, Nos. 4-5, 1994, pp. 345-374.
[6] J. Turner, "Approximation Algorithms for the Shortest Common Superstring Problem," Information and Computation, Vol. 83, 1989, pp. 1-20.
[7] J. Tarhio and E. Ukkonen, "A Greedy Approximation Algorithm for Constructing Shortest Common Superstrings," Theoretical Computer Science, Vol. 57, 1988, pp. 131-145.
[8] A. Blum et al., "Linear Approximation of Shortest Superstrings," J. ACM, Vol. 41, No. 4, 1994, pp. 630-647.
[9] C. Burks et al., "Stochastic Optimization Tools for Genomic Sequence Assembly," Automated DNA Sequencing and Analysis, M.D. Adams, C. Fields, and J.C. Venter, eds., Academic Press, New York, 1994, pp. 249-259.
[10] R. Parsons, S. Forrest, and C. Burks, "Genetic Algorithms for DNA Sequence Assembly," Proc. First Conf. Intelligent Systems for Molecular Biology, AAAI Press, Menlo Park, Calif., 1993, pp. 310-318.
[11] R. Idury and M.S. Waterman, "A New Algorithm for Shotgun Sequencing," J. Computational Biology, Vol. 2, No. 2, 1995, pp. 291-306.
[12] B. Ewing et al., "Base-Calling of Automated Sequencer Traces Using phred; Accuracy Assessment," Genome Research, Vol. 8, No. 3, 1998, pp. 175-185.
[13] D. Feng and R. Doolittle, "Progressive Sequence Alignment as a Prerequisite to Correct Phylogenetic Trees," J. Molecular Evolution, Vol. 25, No. 4, 1987, pp. 351-360.
[14] A. Krogh et al., "Hidden Markov Models in Computational Biology," J. Molecular Biology, Vol. 235, No. 5, 1994, pp. 1501-1531.
[15] E. Anson and E. Myers, "ReAligner: A Program for Refining DNA Sequence Multialignments," J. Computational Biology, Vol. 4, No. 3, 1997, pp. 369-383.
[16] E.S. Lander and M.S. Waterman, "Genomic Mapping by Fingerprinting Random Clones: A Mathematical Analysis," Genomics, Vol. 2, No. 3, 1988, pp. 231-239.
|
 Additional Information
|
Citation:
Gene Myers,
"Whole-Genome DNA Sequencing,"
Computing in Science and Engineering,
vol. 01,
no. 3,
pp. 33-43,
May/Jun,
1999
|
|
RSS Feed