PerFSeeB: Designing Long High-weight Single Spaced Seeds for Full Sensitivity Alignment with a Given Number of Mismatches

Background: Technical progress in computational hardware allows researchers to use new approaches for sequence alignment problems. A standard procedure is usually based on pre-aligning of short subsequences followed by proper comparison of neighbouring parts. For this purpose index ﬁles are created that store all subsequences (or numbers associated with them) and their positions within a reference sequence. Index ﬁles designed on subsequences of 32–64 symbols for a human reference genome can now be easily stored without any compression even on a budget computer. The main goal now is to choose a combination of symbols (a spaced seed) that will tolerate various mismatches between reference and given sequences. An ideal spaced seed should allow us to ﬁnd all such positions (full sensitivity). By increasing the seed’s weight by one we usually reduce the number of candidate positions fourfold. At the same time longer seeds also reduce the number of signatures to be checked. Results: Several algorithms to assist seed generation are presented. The ﬁrst one allows us to ﬁnd all permitted spaced seeds iteratively. The results obtained with the algorithm show speciﬁc patterns of the seeds of the highest weight. Among the best seeds, there are periodic seeds with a simple relation between the period of a seed, its length and the length of a read. The second algorithm generates blocks for periodic seeds. A list of blocks is found for blocks of up to 50 symbols and up to 9 mismatches. The third algorithm uses those lists to ﬁnd spaced seeds for reads of an arbitrary length. Conclusions: Lists of long high-weight spaced seeds are found and available in Supplementary Materials. The seeds are best in terms of weights compared to seeds from other papers and can usually be applied to shorter reads. Codes for all algorithms are available at https://github.com/vtman/PerFSeeB.


Background
Sequence analysis is used to understand the features, structure, function of organisms. By comparing sequences obtained for well-known and unexplored organisms we may understand the biology of the unexplored ones. Currently, experimental techniques cannot provide us with whole sequences but only with many subsequences that need to be concatenated/merged in some way to form a long sequence. Thus, researchers have to solve a general sequence alignment problem before they can produce any meaningful conclusions related to the biological properties of an organism.
Suppose two long sequences are similar in some way. One sequence (a reference sequence) is known, the other sequence is to be found. For example, as a reference sequence, we may use a human genome sequence (an "averaged" sequence based on data obtained from several persons). We want to know a genome sequence for another person, i.e. a patient with a specific disease. The current hardware for genome sequence allows us to find only chunks of the unknown genome of the "patient". Those chunks (called reads) are usually relatively short (hundreds of base pairs) and may contain errors. We assume that the reference and "patient" sequences are similar, so we may use the reference sequence to align a set of reads accounting for possible mismatches.
The standard procedure is to consider each read and find its possible positions within the reference sequence such that the distance between a given read and a part of the reference sequence is minimal. The distance between two strings x and y was introduced in [1] and can be determined in several ways. We may define a list of elementary operations which convert a source string x into a target string y. Each operation may have a different cost, the distance is then a sum of all costs. If we cannot transform x into y, then the cost is ∞. According to [2], depending on permissible elementary operations the most common distances are: Levenshtein (or edit) distance (insertions, deletions, substitutions are allowed at equal cost of 1; symmetric, i.e. d(x, y) = d(y, x)) [3], Hamming distance (only substitutions, symmetric) [4], episode distance (only insertions, is not symmetric) [5], longest common subsequence distance (insertions and deletions, all costing 1, symmetric) [6].
The similarity between two strings was originally measured using dynamic programming algorithms, see [7,8,9]. However, due to time complexity, the use of these algorithms became impractical for the increased size of data available. While it is natural to position a read in a way to achieve the smallest distance, the found location may not always be the best one. With progress related to sequencing hardware and the amount of data provided the original problem can be simplified as many reads may overlap, so for each position within a reference sequence, there are tens/hundreds of reads that have regions similar to a chosen reference chunk. So, ideally, we need to align reads in such a way that there are fewer discrepancies between each other when aligned. In any case, the initial problem is to find possible candidate positions for each read.
In the late 90s several new algorithms, e.g. BLAST [10,11], appeared based on ideas of filtration and indexing. Short sequence fragments were used. To align a read we require fragments from the read to be also found in a reference sequence. The search is sped up using various indexing, e.g. hash-tables, which may provide a researcher with "false-matching" positions. The fragments were considered as contiguous segments. Once candidate positions based on full matching of contiguous regions are found, algorithms extend regions around the common parts to calculate a similarity score (seed-and-extend approach).
Originally only contiguous fragments were considered, however, in [12] and [13] spaced seeds were introduced. By a seed we mean a vector with all elements from a binary alphabet. We may use a bit-wise representation (1 when a symbol at a given position is taken into account and 0 when it is ignored). We position three sequences with respect to each other (a reference sequence, a read and a seed). To find the distance we consider only those elements of the reference sequence and the read that have 1-element of the seed at the same position. When there is 0-element of the seed, the distance between the corresponding elements of the reference sequence and the read does not contribute to the total distance.
The number of 1s within a seed is called its weight, while the number of all symbols (0s or 1s) gives its length/span. In [12] the most sensitive seed was 111010010100110111. Some spaced seeds for different weights can be found in [14]. The idea of spaced seeds was extended for other problems: vector [15], indel [16], neighbour [17] seeds. In ZOOM software [18] spaced seeds are generated to perform alignment with at most 2 mismatches. In PerM software [19] so-called periodic spaced seeds are used to improve the efficiency of mapping. Fast alignment-free string comparison based on spaced seeds (spaced-words) is discussed in [20].
Later approaches based on multiple seeds were used, e.g. [21,22] (a good review can be found in [23]). Seeds in a multiple seed environment are designed to have less overlap between each other and thus are increasing chances to hit common regions.
Seed design may also deal with a non-binary alphabet. For example, in YASS [24] a three-letter alphabet (#, @, −) is used, where # stands for a nucleotide match, @ is for a match or transition (A ↔ G or C ↔ T mutations) and − is used when we ignore corresponding symbols.
The sensitivity of seeds is usually measured using probabilistic approaches. In this paper, we consider an extreme case of full sensitivity seeds under the assumption that a read has at most n m mismatches. This means that these seeds should allow us to find all candidate positions. Full sensitivity seeds are also known as lossless seeds [25] and were applied to filtration problems. A lossless filtration means that all fragments will be found (in case of lossy filtration we may miss some of them).
For a given length of reads, there are a lot of seeds that can be used for our task. In the general case, a seed of higher weight should provide us with less candidate positions for alignment. As there are 4 symbols for genome alignment problems, then by increasing the weight of seed by one we reduce the number of candidate positions by 4 times. This factor 4 is valid only in the perfect case of discrete uniform distribution when all four symbols A, C, G, T have the same chance to appear at a given position in a sequence and all such events for any two positions are independent. In practice, the factor is smaller, however, this does not change the fact that seeds of higher weight are preferable for alignment problems.
There may be several seeds of the maximum weight. Longer seeds require us to generate and check fewer index/hash values. We observed that most long highweight seeds have a periodic structure. However, this structure is not a perfect one like discussed in [25] where a seed is made of several repetitions of structure A separated by structure B. We have an integer number of repetitions of structure A and a "remainder" of this structure (which is a number of first elements of structure A). The size of a periodic block has a simple relation with lengths of reads and the seed. It is possible to generate those periodic blocks within a reasonable time frame (from a fraction of a second for blocks less than 30 symbols to several hours for cases of 50 symbols).

Problem setup
Suppose there is a reference sequence of length L and we are given a set of shorter sequences (reads) of length n r . For human genome problems L ≈ 3.2 · 10 9 and n r ≈ 100-300. Let there be a seed s of length n s and weight w. Each symbol of sequences is usually either a letter A, C, G, T or a symbol N when the symbol is unknown or specific masking has been applied. For simplicity, we assume that only 4 letters are present. Therefore each symbol can be coded with 2 bits. When a seed is positioned at given elements of the reference sequence or a read, corresponding 1elements select w elements within the sequences. Thus we may form 2w-bit numbers. For a read we get (n r − n s + 1) numbers, for the reference sequence there are (L − n s + 1) ≈ L numbers. Therefore we get a list of pairs ("position", "signature"). We may sort the list by "signature" values. In this way for each 2w-bit "signature" value found of a read, we may obtain a set of positions within the reference sequence having the same "signatures" values.
For human genome problems all positions can be coded with a 32-bit number. Therefore storing the whole list in memory requires L(32 + 2w) bits. If w = 32, then the memory required is 39 GB; for w = 64 we need 64 GB. After the list is sorted by "signature" values we may split it on shorter vectors having the same number of identical bits which can be ignored for the whole vector. For example, a spaced seed of weight 24 provides us with a 24-vector of letters A, C, G, T for a given position within the reference sequence. We may combine all pairs ("position", "signature") in groups having the same 8 letters for "signature", e.g. the first 8 letters. Therefore we may omit those 8 letters in a chosen group and store only the other 24 − 8 = 16 letters. Of course, by varying the number of the same letters in groups, we may increase or decrease the number of such groups. However, it is safe to assume that 8 letters are used, so we reduce storage requirements: L(16 + 2w), i.e. 32 GB for w = 32 and 58 GB for w = 64. This means that index files created for a chosen seed can be easily stored even on a budget computer. In principle, we may create index files for multiple seeds of different weight, however in this paper we focus only on a single seed case.
In many other approaches based on probabilistic ideas quality of seeds generated is based on sensitivity, i.e. the chance that seed will allow us to find all candidate positions within a reference sequence. Here we consider the extreme case and require that a seed allows us to find all positions. On the other hand, we also restrict the matching of two sequences to a specific case. We set a number n m of mismatches and consider full matching when two strings are of the same length and have not more than n m mismatches. Cases of insertions/deletions, transitions/transversions are not considered in this paper and will be discussed in future papers. This approach seems to be a limited one. However, insertions/deletions are very small (but important) fractions among all other cases, thus we may successfully align almost all reads. So, for reads that are not aligned we may 1) use other approaches, e.g. those based on dynamic programming (see X-drop approach to improve performance [26]) or seeds designed to account for other mutations, 2) align the second sequence for paired-end data, 3) align with respect to already pre-aligned other reads not containing insertions/deletions. Thus in this paper, we deal with full sensitivity seeds that allowed us to have not more than n m mismatches.
By increasing the seed's weight we reduce the number of positions within the reference sequence that have identical "signature" values. So, we aim to find seeds of the highest weight possible for reads of given lengths. Several seeds may exist. To choose the best one we pick up seeds of maximum length. In this way, we are reducing the number (n r − n s + 1) of "signatures" generated for each read. Of course, each seed may provide us with a different number of candidate positions within a reference sequence. Therefore we cannot guarantee that a smaller number of "signature" values will provide us with an also smaller number of total candidate positions to be processed compared to a larger number of different "signatures" obtained with a different seed. However, in a general case of pure random sequences, this should be true, i.e. the total number of candidate positions should be proportional to (n r − n s + 1).
The procedure to choose the best seeds is described below. We set a positive integer number w and for a given number of mismatches n m and length n r of reads we check if there are any seeds that have weight w. It is clear that by increasing lengths n r we may increase maximum possible weight of seeds we can generate. However, the maximum weight of seeds may stay constant for a range of n r values. If we have two lengths n r1 and n r2 of reads (n r1 < n r2 ), then all seeds found for (n m , w, n r1 ) triple are also valid seeds for (n m , w, n r2 ). There may be seeds for (n m , w, n r2 ) that are not valid seeds for (n m , w, n r1 ). Therefore there is a higher chance that the longest seeds found for (n m , w, n r1 ) are shorter than the longest seeds found for (n m , w, n r2 ). While it may be good to choose the longest seeds valid for (n m , w, n r2 ), they may not be valid seeds for (n m , w, n r1 ). Therefore, once we have found seeds valid for (n m , w) by increasing value n r iteratively, we stop and choose the longest seeds among them.

Seed validation
Let there be a seed s of length n s . We want to check if the seed meets the full sensitivity requirement for any read of length n r and a given maximum number n m of mismatches. Suppose n m and n r are set. Then we create n m -vector of indices i k , k = 1, 2, . . . , n m such that 1 ≤ i k ≤ n r . By definition, the length of a seed is not greater than the length of a read, n s ≤ n r . We may shift the first element of a seed by δ with respect to the first element of the read. As the last element of the seed should be within the read's elements, then δ can vary from 0 to (n r − n s ). For each value of δ we check that none of 1-elements of the seed shifted by δ has indices i k , k = 1, 2, . . . , n m . If for any possible combination of indices i k , there is at least one value of δ (depending on i k , k = 1, . . . , n m ) the requirement is met, then the seed is a valid seed for given n m and n r . See Figure 1.
Parameter δ has (n r − n s + 1) values. By padding the seed vector with 0-elements from left and right we can form (n r − n s + 1) vectors of length n r . We pad from left and right and the total number of 0-elements to be used for each vector is (n r − n s ). Padding can be performed in any way, however it may be more convenient to have the first element of the seed aligned with the first element of the read for the first vector, the next vectors are just the previous vectors padded by one 0-element from left (see Figure 1). Or we may align the last elements of a seed and read and pad by 0-element from right (see Figure 4).
In any case for a given seed we form (n r −n s +1) vectors of length n r . We generate all possible combinations of i k indices. There are n m indices and we want them all to be different. There are such combinations. If for any of these combinations all (n r − n m + 1) vectors/rows contain at least one 1-element for chosen indices i k , then the seed cannot be used, otherwise, the seed meets the requirements. We want seed validation to be performed as quickly as possible on a modern computer. Therefore we may store each n r -vector as an n r -bit number. It may often be reasonable to pad each vector with 1-elements to a 128-bit number (or several 128-bit numbers). Then SIMD instructions (single instruction, multiple data) can be used to perform comparison or various logical operations. For a given set of indices i k , k = 1, . . . , n m we may create a 128-bit vector V such that all its elements are 1 except i k -th ones which are 0. Then for each row R p , p = 1, . . . , (n r − n m + 1) we check if R p |V equals V (by "|" we mean bitwise logical OR operation). If it is true, then the seed can be used for the given combination of n m indices. In Figure 2 we use examples for Figure 1. For convenience we pad all vectors to 24-vectors (by merging with four 1-elements). For example 1 (i 1 = 7, i 2 = 12) only one row (R 3 ) has met the requirement R p |V = V , therefore for this combination of indices the seed can be used. However, for example 3 (i 1 = 4, i 2 = 13) no row meets the requirement. Therefore, the seed cannot be used for the given combination of indices and, as the result, it cannot provide us with full sensitivity. Only when the procedure is successful for all C nm nr combinations, then the seed is valid. There is an alternative approach to validate seeds. We create n r binary vectors/columns U t , t = 1, . . . , n r , of length (n r − n m + 1), see Figure 3. As before we may also pad them with 1-elements to form numbers of a given length, e.g. 32-, 64or 128-bit numbers. The task is to consider all C nm nr combinations of columns U t and perform logical OR operation, i.e.
and check if the resultant column has all 1-elements (let us call it the saturated vector). Now we try to reduce the number of columns. We may identify the same columns and leave only different ones (10 out of 36 columns are removed in the example in Figure 4). So, as n m = 4 and n r = 36, then instead of C 4 36 = 58905 combinations, we should check only C 4 26 = 14950. The next step is to identify those columns that are subsets of other columns. We denote U k ⊂ U m if U k |U m is U m . This means that all 1-elements of column U k are also 1-elements of U m (however, there may be positions q such that element q of U m is 1-element but element q of U k is 0element). Removing columns that are subsets of other columns allows us to further decrease the number of combinations. For the example in Figure 4 we excluded extra 16 columns, so the total number of combinations is C 4 36−10−16 = C 4 10 = 210, i.e. the number of combinations we need to check is 280 times fewer compared to the original case. Note that similar approaches can be used when we form resultant columns. For instance, we may generate i k indices iteratively. We consider i 1 from 1 to (n r − n m + 1) (as other (n m − 1) indices are to be generated, they all should be different, so i 1 can never be equal to n r ). Then i 2 is from (i 1 + 1) to n r − n m + 2, similarly i 3 is from (i 2 + 1) to (n r − n m + 3), and so on. If U i3 ⊂ (U i1 |U i2 ), then U i3 can be skipped.

Seed expansion
It is agreed that a seed should start and end with 1-element. So, there is only 1 seed of length 1 (1), there is also only 1 seed of length 2 (11), 2 seeds of length 3 (101, 111), 4 seeds of length 4 (1001, 1011, 1101, 1111). Therefore for a read of length n r there are seeds in total. As validation of each seed is also quite time-consuming, we should identify ways to reduce the number of candidate seeds. For example, seed 10001110100100011101 is a valid seed for n r = 30 and n m = 3. Any subset of this seed is also a valid seed (of lower weight). So, 1110100100011101, 100011101001000111, 10001010100100010101 are also valid seeds. Therefore, we can implement the following procedure. Assume we have already found all valid seeds of length less or equal to k. We pad all these seeds with 0-elements from their right ends, so we get vectors of length k. Then we concatenate them with 1-element (also at the right ends of the padded seeds). Before applying the validation procedure we form a seed by removing the first 1-element and all 0-elements from the left end and check that the seed is in the list of valid seeds. For example, an original valid seed was 100111011 (of length 9) and we aim to find valid seeds of length 13, then the extended seed is 1001110110001 and we need to check if 1110110001 is already in the list of valid seeds. Clear that seed is valid if and only if the reverse seed (the order of elements is reversed) is valid. So, seeds 1001110110001 and 1000110111001 are valid (or are not valid) at the same time.

Periodic seeds
The above procedure allows reducing the number of candidate seeds. However, there are still a lot of seeds to be validated, so finding all possible seeds for a read's length of more than 45 is very slow. However, we can observe a very important property. There are almost always periodic seeds such that where T is the size of the periodic block. Such seeds have a whole number n b of these periodic blocks and the "remainder" (the first n d > 0 elements of the block), so n s = n b · T + n d . There may be seeds of different period T for the same length n r of a read. For example, in Figure 5 there are seeds found for n r = 43, n m = 4. The maximum weight is w = 12. We get two pairs of seeds for T = 19, three pairs for T = 17 and one for T = 13.
Note that when such seeds can be found there are often other (shorter) seeds available. There are also several exceptions from the observation. For some values of n r and n m we may have seeds such that (4) is valid for smaller values of n r , e.g. n r − 1, n r − 2. However, there may be cases when the formula is not true for the best seeds. See Table 1. For 80% of read lengths formula (4) is valid for a given value of n r , for 87% is true when smaller n r can be used.
Suppose there is a periodic seed such that n s = n b T + n d and formula (4) is true. We want to check if a seed is a valid one for a given n m , see Figure 6. We need to generate indices j k , k = 1, . . . , n r such that 1 ≤ j k ≤ n r and check if the resultant column U j1 |U j2 | . . . |U nm is the saturated vector. If the seed is valid, then its periodic block should also meet the same requirements. For this purpose, we just choose j k such that (1 + T ) ≤ j k ≤ 2T . Now we assume that the resultant column for the periodic block is not the saturated one for all possible combinations of indices. For any index j k , 1 ≤ j k ≤ n r , we may write down j k = j * k + m · T , where (1 + T ) ≤ j * k ≤ 2T and m is an integer number. Therefore U j k ⊂ U j * k and instead of U j k we may consider U j * k .

Periodic blocks
Validation of a periodic block is done in the way of validation of the whole seed. We just need to generate all possible combinations of indices j k , k = 1, . . . , n m such that 1 ≤ j k ≤ T and check if the resultant column is not the saturated one.
A periodic block is valid if and only if its reverse is valid. We may also perform a cyclic rotation of elements of the block, those new blocks are valid at the same time. As the result, we have groups of 2T periodic blocks of length T (some of them may be identical) that are valid/not valid at the same time. We call them equivalent blocks. Therefore it is enough to consider the validity of only one block. To reduce the number of blocks to be considered we require that the first element is always 0element and the last element is always 1-element. See examples of equivalent blocks generated for a given periodic block in Figure 7. We need a procedure to choose only one block instead of 2T blocks. Of course, for some blocks (e.g. 00101101) there may be cases of identical blocks obtained via reversion/cyclic rotation. By varying indices j k we create patterns of 0-elements. Those patterns should be within the periodic block (or one of the equivalent blocks obtained by cyclic rotation) since there should be a row such the corresponding elements of the chosen columns are all 0-elements. Therefore each periodic block must have a contiguous chunk of n m 0-elements. Therefore when we generate various periodic blocks we may always assume that the first n m elements are 0-elements. To choose one block we pick up the one with the highest number of 0-elements at the beginning. As among blocks obtained for the reverse block, there will also be a block with the maximum number of 0-elements, we need to perform a further comparison. We may count the number of 1-elements in contiguous blocks from the left/right side of the zero-block and choose the block with fewer 1-elements. If the contiguous are the same, then consider neighbouring blocks of 0-elements (and choose the smallest one). We repeat the procedure if it is needed.
As we want to find seeds of maximum weight, it is reasonable to also find periodic blocks of maximum weight. Suppose there are blocks found for weight w. By replacing 1-elements with 0-elements we form periodic blocks of weight (w − 1). However, there may also be blocks of weight (w − 1) that cannot be formed by replacing 1-elements in blocks of weight w. For example, there are 5 blocks for T = 11, n m = 2 and weight w = 7: 00011011111, 00101011111, 00101110111, 00101111011, 00110101111. Block 00010110111 of weight w = 6 cannot be formed from those blocks. Seeds are formed of an integer number of periodic blocks and a "remainder". There is a possibility that the best seeds are formed of blocks of non-maximum weight. However, when we generated seeds of non-maximum weight, they never formed seeds of weight larger than seeds formed from maximum-weight blocks.
All ideas mentioned above allow us to reduce the number of blocks to be validated. It is also possible to parallelise processing, so each CPU thread validates only specific seeds from a pre-generated list. Together with SIMD instructions for validation steps generation of periodic blocks is sped up. It may take less than a second for n r < 35, however, finding periodic blocks for n r ≈ 50 may still take hours as trillions of blocks should be validated.

Forming periodic spaced seeds
The final step of PerFSeeB approach (periodic full sensitivity blocks) is to form spaced seeds of maximum weight. For this purpose, we consider all periodic blocks formed for a given number n m of mismatches. As n s = n b T +n d , n b ≥ 1, 1 ≤ n d < T , and n r = n s + T − 1, then n r = n b T + n d + T − 1 = (n b + 1)T + (n d − 1) ≥ 2T or T ≤ n r /2. For each periodic block we form all equivalent blocks and check if 1) the first symbol of the block is 1-element, 2) n d -th element is also 1-element. In principle, there is no need to consider blocks obtained from the reverse periodic block as the final seed will be a reverse of seeds formed from the original block. Once the seed is formed we count its weight. By processing all periodic blocks we find seeds of maximum weight.

Results
We have written a code to generate the best periodic blocks of size T for a given number n m of mismatches. A user can specify an initial number n 1 of 1-elements in those blocks. If no valid blocks are found for a given n 1 , then the value of n 1 is incremented by one and the procedure restarts until at least one valid block is found. The code was applied for n m values from 2 to 9, and for T values from 10 to 50 (and from 10 to 70 for n m = 2). Maximum weight n 1 and density of best blocks (defined as n 1 /T ) are shown in Table 2.
Note that while values n 1 and ρ tend to increase with the block size, they are not monotonic in general. See examples for n m = 5 and n m = 8 in Figure 8  When all maximum-weight blocks are found for a given range of T , we may find periodic spaced seeds of the maximum weight for any given value of n r . Of course, there may be cases of seeds composed of periodic blocks of different sizes. For example, if the length of reads is n r = 35, the maximum weight of possible seeds is w = 17 and there are seeds formed for blocks of sizes 7, 10, 11, 13, e.g.
• T = 7, n b = 4, n d = 1, b = 1011100, s = 10111001011100101110010111001; • T = 10, n b = 2, n d = 6, b = 1101111000, s = 11011110001101111000110111; • T = 11, n b = 2, n d = 3, b = 11111000110, s = 1111100011011111000110111; • T = 13, n b = 1, n d = 10, b = 1011111011100, s = 10111110111001011111011. For a given length n r of reads, we plot sizes of corresponding periodic blocks, see Figure 9. We see that sizes of best blocks tend to work in a specific range of n r values. Best blocks are often those having peak density values. For example, if n m = 8, the most frequent block sizes are T = 18, 21, 33, 36, 39 (Figure 9), we see peak density values for them in Figure 8. Note that values of T also increase with the length of reads. So, while we can find seeds for any n r , they may not be the densest as there we have not generated periodic blocks for large values of T .
The final goal is to set the weight w of seeds, then find the minimum length of reads that have valid seeds of this weight and choose the longest seeds when several seeds are available. In Table 3 we present examples of these seeds for weights w (multiples of 8). As seeds may be very long we present only periodic blocks, number n b of these blocks and values of "remainders" n d , see Tables 4 and 5. The full list of spaced seeds found for various values of n r and w (n r ≤ 400, w ≤ 320) is in Supplementary Materials. Users can generate their seeds using codes (https://github.com/vtman/PerFSeeB).
We plot weights of the best seeds as a function of reads' length in Figure 10. Based on lemmas in [27], it is possible to show that for a contiguous seed of weight/length q the minimum length of reads when the seeds are valid is K = q(n m + 1), so the ratio is r = q/K → r ∞ = 1 nm+1 when q → ∞. The corresponding values of r ∞ are also shown in Figure 10 (dashed lines). Depending on values of n m and n r the spaced seeds are more dense (per read's length) compared to contiguous seeds by 20-68% (n r = 50), 40-95% (n r = 100), 60-113% (n r = 150), 70-128% (n r = 200).

Discussion
To compare quality of spaced seed generated with PerFSeeB approach we present a list of most popular seeds in Table 6. These seeds are generated for given sensitivity levels. When there were several seeds presented in a paper, we choose a seed obtained for highest sensitivity levels. We may see that the seeds are usually relatively short and of a smaller weight. Unlike PerfSeeB approach, the other algorithms did not usually put any restrictions on the number of mismatches. Several seeds were generated for a multiple-seed approach.
Our goal is to have full sensitivity seeds. Therefore we aim to check how the other seeds work under such requirements. For a given seed and a number of mismatches n m we vary lengths' n r of reads in order to check when the seed is valid. These numbers are provided in Table 7. We may see that seeds generated directly with the extension procedure (usually n r < 45) and seeds generated with PerFSeeB approach (they all called "best" seeds in Table 7) are valid for shorter reads: by approximately 15% for w ≤ 12, by 20% for w = 20, 22 and by 32% for w = 39-46. We have also provided weights of PerFSeeB seeds for lengths n r found for each seed. These weights are usually 30-40% higher compared to the given ones.

Conclusions
PerFSeeB approach proposed in this paper is based on the designing of periodic blocks. Resultant spaced seeds are guaranteed to find all positions within a reference sequence when a given number of mismatches is set. Each periodic seed is an integer number of periodic blocks and a "remainder" (a number of the first symbols of the block). The size of a periodic block is the difference between read's and seed's lengths plus one. This relation is empirical and was observed for seeds generated by iterative extension procedure for reads of length less than 45.
Periodic blocks are found for the number mismatches n m from 2 to 9 and block's length T up to 50 (or 70 for n m = 2). Those blocks can be used to generate spaced seeds required for any given length of reads. The seeds found with PerFSeeB approach might not be of the highest weight for long reads (>200) as longer periodic blocks are needed to be found, however, they definitely meet the requirements. Codes used to generate periodic blocks and final seeds are designed to account for SIMD instructions, can work in a multithreading environment and are publicly available at (https://github.com/vtman/PerFSeeB). While the authors did their best to minimise the number of candidate blocks to be validated, there may be trillions of them to be checked for periods T around 50.

Declarations
Abbreviations Not applicable.
Ethics approval and consent to participate Not applicable.

Consent for publication
Not applicable.

Availability of data and materials
The codes to generate periodic blocks and seeds are publicly available at https://github.com/vtman/PerFSeeB. Figure 1 Checking if a seed is a full sensitivity one for a given length of a read and number of mismatches. Figure 2 Seed validation based on padded rows. When the requirement is met, the row is in green colour, otherwise, in red colour.           Table 7 Minimum lengths of reads required to achieve full sensitivity for a given number nm of mismatches. Minimum lengths found with PerFSeeB approach are in bold. For the found lengths the corresponding weights of seeds generated with the proposed approach are in parentheses.  Figure 1 Checking if a seed is a full sensitivity one for a given length of a read and number of mismatches.

Figure 2
Seed validation based on padded rows. When the requirement is met, the row is in green colour, otherwise, in red colour.

Figure 3
Seed validation based on columns. When the requirement is met, the row is in green colour, otherwise, in red colour. Reducing the number of combinations when checking seed's validity.

Figure 5
All seeds of maximum weight (12) found for reads of length 43, number of mismatches is 4. Flipped seeds are not shown.

Figure 6
A seed is valid only when its periodic block is valid.   Maximum numbers of 1-elements per length of periodic blocks, nm = 5 and nm = 8.

Figure 10
Weights of the best spaced seeds per reads' lengths (solid lines). Maximum ratios for contiguous seeds (dashed lines).

Supplementary Files
This is a list of supplementary les associated with this preprint. Click to download.