Fast computation of neighbor seeds.
BACKGROUND
Alignment of biological sequences is one of the most frequently performed computer tasks. The current state of the art involves the use of (multiple) spaced seeds for producing high quality alignments. A particular important class is that of neighbor seeds which combine high sensitivity with reduced space requirements. Current algorithms for computing good neighbor seeds are very slow (exponential).


RESULTS
We give a polynomial-time heuristic algorithm that computes better neighbor seeds than previous ones while being several orders of magnitude faster.
Ilie
Lucian
L
Department of Computer Science, University of Western Ontario, London N6A 5B7, Ontario, Canada. ilie@csd.uwo.ca
Ilie
Silvana
S
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D016415:Sequence Alignment / Q000379:methods*