Best hits of 11110110111: model-free selection and parameter-free sensitivity calculation of spaced seeds

Optimized spaced seeds, or best gapped q-grams, have independently been proposed in PatternHunter [3] and by Burkhardt and Karkkainen [4]. The primary objective was either to improve the sensitivity of the heuristic but efficient hit and extend BLAST-like strategy (without using the neighborhood word principle
¹), or to increase the selectivity for lossless filters on alignments of size (ell) under a given Hamming distance of k.

Several extensions of the spaced seed model have then been proposed on the two aforementioned problems: vector seeds [5], one gapped q-grams [6] or indel seeds [7, 8], neighbor seeds [9, 10], transition seeds  [11–15], multiple seeds [16–19], adaptive seeds [20] and related work on the associated indexes  [21–26], just to mention a few.

Unfortunately, spaced seeds are known to produce hard problems, both on the seed sensitivity computation [27] or the lossless computation [28], and moreover on the seed design [29]. But the choice of the right seed pattern has a significant impact on genomic sequence comparison [3, 12, 16, 20, 30–38], on oligonucleotide design [39–44], as well as on amino acid sequence comparison [45–53]; this has led to several effective methods to (possibly greedily) select spaced seeds [54–61] with elaborated alignment models and their associated algorithms [62–70].

Another less frequently mentioned problem is that the seed design is mostly performed on a fixed and already fully parameterized alignment model (for example, a Bernoulli model where the probability of a match
p is set to 0.7). There is not so much choice for the optimal seed, when, for example, the scoring system is changed, and thus the expected distribution of alignments.

We note that several recent works mention the use of spaced seeds in alignment-free methods [71–73] with applications in phylogenetic distance estimation [74], metagenomic classification [75, 76], just to cite a few.

Finally, we also noticed that several recent studies use the overlap complexity [54, 56, 57, 77–79] which is closely linked to the variance of the number of spaced-word matches [80] and is known to provide an upper/lower bound for the expectation of the length preceding the first seed hit [27, 66, 81]. We mention here that a similar parameter-free approach could also be applied for the variance induced selection of seeds, but an interesting question remains in that case: to find a dominance equivalent criterion associated with the selection of candidate seeds.

The paper is organized as follows. We start with an introduction to the spaced seed model and its associated sensitivity or lossless aspect, and show how semi-rings on DFA can help determining such features. Section “Semi-rings and number of alignments” restricts the description to counting semi-rings that are applied on a specific DFA to perform an efficient dynamic programming algorithm on a set of counters. This is a prerequisite for the two next sections that present respectively continuous models and discrete models. Section “Continuous models” is divided into two parts : the first one outlines the polynomial form of the sensitivity proposed by [1] to compute the sensitivity on the Bernoulli model together with the associated dominance principle, whereas the second one extends this polynomial form to the Hit Integration model of [2], and explains why the dominance principle remains valid. Section “Discrete models” describes two new Dirac and Heaviside models, and shows how lossless seeds can be integrated into them. Then, we report our experimental analysis on all the aforementioned models, display and explain several optimal seed Pareto plots for the restricted case of one single seed, and links to a wide range of compiled results for multiple seeds. The last section brings the discussion to the asymptotic problem, and to several finite extensions.