title: Reducing storage requirements for biological sequence comparison.
abstract: BACKGROUND
  Comparison of nucleic acid and protein sequences is a fundamental tool of modern bioinformatics. A dominant method of such string matching is the 'seed-and-extend' approach, in which occurrences of short subsequences called 'seeds' are used to search for potentially longer matches in a large database of sequences. Each such potential match is then checked to see if it extends beyond the seed. To be effective, the seed-and-extend approach needs to catalogue seeds from virtually every substring in the database of search strings. Projects such as mammalian genome assemblies and large-scale protein matching, however, have such large sequence databases that the resulting list of seeds cannot be stored in RAM on a single computer. This significantly slows the matching process.
  
  
  RESULTS
  We present a simple and elegant method in which only a small fraction of seeds, called 'minimizers', needs to be stored. Using minimizers can speed up string-matching computations by a large factor while missing only a small fraction of the matches found using all seeds.
authors.affiliation: Institute for Physical Science and Technology, University of Maryland, College Park, MD 20742-2431, USA.
authors.forename: Michael
authors.initials: M
authors.lastname: Roberts
authors.forename: Wayne
authors.initials: W
authors.lastname: Hayes
authors.forename: Brian R
authors.initials: BR
authors.lastname: Hunt
authors.forename: Stephen M
authors.initials: SM
authors.lastname: Mount
authors.forename: James A
authors.initials: JA
authors.lastname: Yorke
mesh_terms: D000465:Algorithms; D030541:Databases, Genetic; D016247:Information Storage and Retrieval / Q000379:methods*; D009716:Numerical Analysis, Computer-Assisted; D016415:Sequence Alignment / Q000379:methods*; D017421:Sequence Analysis / Q000379:methods*