  Motivation: Optimizing seed selection is an important problem in read
mapping. The number of non-overlapping seeds a mapper selects determines the
sensitivity of the mapper while the total frequency of all selected seeds
determines the speed of the mapper. Modern seed-and-extend mappers usually
select seeds with either an equal and fixed-length scheme or with an inflexible
placement scheme, both of which limit the potential of the mapper to select
less frequent seeds to speed up the mapping process. Therefore, it is crucial
to develop a new algorithm that can adjust both the individual seed length and
the seed placement, as well as derive less frequent seeds.
  Results: We present the Optimal Seed Solver (OSS), a dynamic programming
algorithm that discovers the least frequently-occurring set of x seeds in an
L-bp read in $O(x \times L)$ operations on average and in $O(x \times L^{2})$
operations in the worst case. We compared OSS against four state-of-the-art
seed selection schemes and observed that OSS provides a 3-fold reduction of
average seed frequency over the best previous seed selection optimizations.
