title: Efficient computation of spaced seeds.
abstract: BACKGROUND
  The most frequently used tools in bioinformatics are those searching for similarities, or local alignments, between biological sequences. Since the exact dynamic programming algorithm is quadratic, linear-time heuristics such as BLAST are used. Spaced seeds are much more sensitive than the consecutive seed of BLAST and using several seeds represents the current state of the art in approximate search for biological sequences. The most important aspect is computing highly sensitive seeds. Since the problem seems hard, heuristic algorithms are used. The leading software in the common Bernoulli model is the SpEED program.
  
  
  RESULTS
  SpEED uses a hill climbing method based on the overlap complexity heuristic. We propose a new algorithm for this heuristic that improves its speed by over one order of magnitude. We use the new implementation to compute improved seeds for several software programs. We compute as well multiple seeds of the same weight as MegaBLAST, that greatly improve its sensitivity.
  
  
  CONCLUSIONS
  Multiple spaced seeds are being successfully used in bioinformatics software programs. Enabling researchers to compute very fast high quality seeds will help expanding the range of their applications.
authors.affiliation: Department of Mathematics, Ryerson University, Toronto, ON M5B 2K3, Canada. silvana@ryerson.ca
authors.forename: Silvana
authors.initials: S
authors.lastname: Ilie
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D015203:Reproducibility of Results; D016415:Sequence Alignment / Q000379:methods*; D012984:Software; D013997:Time Factors