title: Optimal seed solver: optimizing seed selection in read mapping.
abstract: 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 ability of the mapper in selecting 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.
  
  
  
  We present the Optimal Seed Solver (OSS), a dynamic programming algorithm that discovers the least frequently-occurring set of x seeds in an L-base-pair read in [Formula: see text] operations on average and in [Formula: see text] operations in the worst case, while generating a maximum of [Formula: see text] seed frequency database lookups. We compare OSS against four state-of-the-art seed selection schemes and observe that OSS provides a 3-fold reduction in average seed frequency over the best previous seed selection optimizations.
  
  
  
  We provide an implementation of the Optimal Seed Solver in C++ at: https://github.com/CMU-SAFARI/Optimal-Seed-Solver
  
  
  
  hxin@cmu.edu, calkan@cs.bilkent.edu.tr or onur@cmu.edu
  
  
  
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Computer Science Department.
authors.forename: Hongyi
authors.initials: H
authors.lastname: Xin
authors.affiliation: Computer Science Department.
authors.forename: Sunny
authors.initials: S
authors.lastname: Nahar
authors.affiliation: Computer Science Department.
authors.forename: Richard
authors.initials: R
authors.lastname: Zhu
authors.affiliation: Department of Computer Science and Engineering, Washington University, St. Louis, MO 63130, USA.
authors.forename: John
authors.initials: J
authors.lastname: Emmons
authors.affiliation: Computer Science Department.
authors.forename: Gennady
authors.initials: G
authors.lastname: Pekhimenko
authors.affiliation: Computational Biology Department, Carnegie Mellon University, Pittsburgh, PA 15213, USA.
authors.forename: Carl
authors.initials: C
authors.lastname: Kingsford
authors.affiliation: Department of Computer Engineering, Bilkent University, Bilkent, Ankara 06800, Turkey and.
authors.forename: Can
authors.initials: C
authors.lastname: Alkan
authors.affiliation: Computer Science Department, Department of Electrical and Computer Engineering.
authors.forename: Onur
authors.initials: O
authors.lastname: Mutlu
mesh_terms: D000465:Algorithms