ALeS: adaptive-length spaced-seed design

Abstract

Motivation: Sequence similarity is the most frequently used procedure in biological research, as proved by the widely used BLAST program. The consecutive seed used by BLAST can be dramatically improved by considering multiple spaced seeds. Finding the best seeds is a hard problem and much effort went into developing heuristic algorithms and software for designing highly sensitive spaced seeds.

Results: We introduce a new algorithm and software, ALeS, that produces more sensitive seeds than the current state-of-the-art programs, as shown by extensive testing. We also accurately estimate the sensitivity of a seed, enabling its computation for arbitrary seeds.

Availabilityand implementation: The source code is freely available at github.com/lucian-ilie/ALeS.

Supplementary information: Supplementary data are available at Bioinformatics online.