Efficient computation of spaced seeds
Related Experiment Video
Updated: May 24, 2026

Reliable Method for Assessing Seed Germination, Dormancy, and Mortality under Field Conditions
Published on: November 6, 2016
1Department of Mathematics, Ryerson University, Toronto, ON M5B 2K3, Canada. silvana@ryerson.ca
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.
Findings:
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.
Conclusion:
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.
Related Concept Videos
Estimation of the Physical Quantities
Sample Size Calculation
The sample size for the given experiment or sampling effort is fundamental to any study design. Sample size decides the number of...
Area Computation by the Alternative Coordinate Method
Estimating Population Standard Deviation
Random Sampling Method
Calculating Standard Deviation
The standard deviation value is small when all the data is concentrated close to the mean. Here the data exhibits low variation. The standard deviation value is larger when the data values are more spread out from the mean. Here, the data displays high variation.
Let us...
