Journal article
AMASS: A Structured Pattern Matching Approach to Shotgun Sequence Assembly
Journal of computational biology, Vol.6(2), pp.163-186
01/1999
DOI: 10.1089/cmb.1999.6.163
PMID: 10421521
Abstract
In this paper, we propose an efficient, reliable shotgun sequence assembly algorithm based on a fingerprinting scheme that is robust to both noise and repetitive sequences in the data, two primary roadblocks to effective whole-genome shotgun sequencing. Our algorithm uses exact matches of short patterns randomly selected from fragment data to identify fragment overlaps, construct an overlap map, and deliver a consensus sequence. We show how statistical clues made explicit in our approach can easily be exploited to correctly assemble results even in the presence of extensive repetitive sequences. Our approach is both accurate and exceptionally fast in practice: e.g., we have correctly assembled the whole Mycoplasma genitalium genome (approximately 580 kbp) is roughly 8 minutes of 64MB 200MHz Pentium Pro CPU time from real shotgun data, where most existing algorithms can be expected to run for several hours to a day on the same data. Moreover, experiments with artificially-shotgunned data prepared from real DNA sequences from a wide range of organisms (including human DNA) and containing complex repeating regions demonstrate our algorithm's robustness to input noise and the presence of repetitive sequences. For example, we have correctly assembled a 238-kbp human DNA sequence in less than 3 min of 64-MB 200-MHz Pentium Pro CPU time.
Details
- Title: Subtitle
- AMASS: A Structured Pattern Matching Approach to Shotgun Sequence Assembly
- Creators
- SUN Kim - University of Illinois Urbana-ChampaignALBERTO MARIA Segre
- Resource Type
- Journal article
- Publication Details
- Journal of computational biology, Vol.6(2), pp.163-186
- DOI
- 10.1089/cmb.1999.6.163
- PMID
- 10421521
- ISSN
- 1066-5277
- eISSN
- 1557-8666
- Language
- English
- Date published
- 01/1999
- Academic Unit
- Nursing; Fraternal Order of Eagles Diabetes Research Center; Computer Science
- Record Identifier
- 9984259403902771
Metrics
27 Record Views