title: Best hits of 11110110111: model-free selection and parameter-free sensitivity calculation of spaced seeds.
abstract: BACKGROUND
  Spaced seeds, also namedgapped q-grams, gapped k-mers, spaced q-grams, have been proven to be more sensitive than contiguous seeds (contiguous q-grams, contiguous k-mers) in nucleic and amino-acid sequences analysis. Initially proposed to detect sequence similarities and to anchor sequence alignments, spaced seeds have more recently been applied in severalalignment-freerelated methods. Unfortunately, spaced seeds need to be initially designed. This task is known to be time-consuming due to the number of spaced seed candidates. Moreover, it can be altered by a set ofarbitrary chosenparameters from the probabilistic alignment models used. In this general context,Dominant seedshave been introduced by Mak and Benson (Bioinformatics 25:302-308, 2009) on the Bernoulli model, in order to reduce the number of spaced seed candidates that are further processed in aparameter-freecalculation of the sensitivity.
  
  
  RESULTS
  We expand the scope of work of Mak and Benson on single and multiple seeds by considering the Hit Integration model of Chung and Park (BMC Bioinform 11:31, 2010), demonstrate that the same dominance definition can be applied, and that a parameter-free study can be performed without any significant additional cost. We also consider two new discrete models, namely the Heaviside and the Dirac models, where lossless seeds can be integrated. From a theoretical standpoint, we establish a generic framework on all the proposed models, by applying acounting semi-ringto quickly compute large polynomial coefficients needed by thedominancefilter. From a practical standpoint, we confirm thatdominant seedsreduce the set of, either single seeds to thoroughly analyse, or multiple seeds to store. Moreover, in http://bioinfo.cristal.univ-lille.fr/yass/iedera_dominance, we provide a full list of spaced seeds computed on the four aforementioned models, with one (continuous) parameter left free for each model, and with several (discrete) alignment lengths.
authors.affiliation: CRIStAL (UMR 9189 Lille University/CNRS)-Inria Lille, Bat M3 ext, Université Lille 1, 59655 Villeneuve d'Ascq, France.
authors.forename: Laurent
authors.identifier: 0000-0002-1170-8376
authors.initials: L
authors.lastname: Noé
keywords: Bernoulli; Counting semi-ring; DFA; Dirac; Dominant seeds; Heaviside; Hit Integration; Polynomial form; Spaced seeds