Asymptotically optimal minimizers schemes
Identifieur interne : 000B22 ( Pmc/Corpus ); précédent : 000B21; suivant : 000B23Asymptotically optimal minimizers schemes
Auteurs : Guillaume Marçais ; Dan Deblasio ; Carl KingsfordSource :
- Bioinformatics [ 1367-4803 ] ; 2018.
Abstract
The minimizers technique is a method to sample
From the analysis of the asymptotic behavior of minimizers, forward and local schemes, we show that the previously believed lower bound on minimizers schemes does not hold, and that schemes with density lower than thought possible actually exist. The proof is constructive and leads to an efficient algorithm to compare
Url:
DOI: 10.1093/bioinformatics/bty258
PubMed: 29949995
PubMed Central: 6037127
Links to Exploration step
PMC:6037127Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Asymptotically optimal minimizers schemes</title><author><name sortKey="Marcais, Guillaume" sort="Marcais, Guillaume" uniqKey="Marcais G" first="Guillaume" last="Marçais">Guillaume Marçais</name><affiliation><nlm:aff id="bty258-aff1">Department of Computational Biology, Carnegie Mellon University, Pittsburgh, PA, USA</nlm:aff></affiliation></author><author><name sortKey="Deblasio, Dan" sort="Deblasio, Dan" uniqKey="Deblasio D" first="Dan" last="Deblasio">Dan Deblasio</name><affiliation><nlm:aff id="bty258-aff1">Department of Computational Biology, Carnegie Mellon University, Pittsburgh, PA, USA</nlm:aff></affiliation></author><author><name sortKey="Kingsford, Carl" sort="Kingsford, Carl" uniqKey="Kingsford C" first="Carl" last="Kingsford">Carl Kingsford</name><affiliation><nlm:aff id="bty258-aff1">Department of Computational Biology, Carnegie Mellon University, Pittsburgh, PA, USA</nlm:aff></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">PMC</idno><idno type="pmid">29949995</idno><idno type="pmc">6037127</idno><idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC6037127</idno><idno type="RBID">PMC:6037127</idno><idno type="doi">10.1093/bioinformatics/bty258</idno><date when="2018">2018</date><idno type="wicri:Area/Pmc/Corpus">000B22</idno><idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000B22</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Asymptotically optimal minimizers schemes</title><author><name sortKey="Marcais, Guillaume" sort="Marcais, Guillaume" uniqKey="Marcais G" first="Guillaume" last="Marçais">Guillaume Marçais</name><affiliation><nlm:aff id="bty258-aff1">Department of Computational Biology, Carnegie Mellon University, Pittsburgh, PA, USA</nlm:aff></affiliation></author><author><name sortKey="Deblasio, Dan" sort="Deblasio, Dan" uniqKey="Deblasio D" first="Dan" last="Deblasio">Dan Deblasio</name><affiliation><nlm:aff id="bty258-aff1">Department of Computational Biology, Carnegie Mellon University, Pittsburgh, PA, USA</nlm:aff></affiliation></author><author><name sortKey="Kingsford, Carl" sort="Kingsford, Carl" uniqKey="Kingsford C" first="Carl" last="Kingsford">Carl Kingsford</name><affiliation><nlm:aff id="bty258-aff1">Department of Computational Biology, Carnegie Mellon University, Pittsburgh, PA, USA</nlm:aff></affiliation></author></analytic><series><title level="j">Bioinformatics</title><idno type="ISSN">1367-4803</idno><idno type="eISSN">1367-4811</idno><imprint><date when="2018">2018</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en"><title>Abstract</title><sec id="s1"><title>Motivation</title><p>The minimizers technique is a method to sample <italic>k</italic>-mers that is used in many bioinformatics software to reduce computation, memory usage and run time. The number of applications using minimizers keeps on growing steadily. Despite its many uses, the theoretical understanding of minimizers is still very limited. In many applications, selecting as few <italic>k</italic>-mers as possible (i.e. having a low <italic>density</italic>) is beneficial. The density is highly dependent on the choice of the order on the <italic>k</italic>-mers. Different applications use different orders, but none of these orders are optimal. A better understanding of minimizers schemes, and the related local and forward schemes, will allow designing schemes with lower density and thereby making existing and future bioinformatics tools even more efficient.</p></sec><sec id="s2"><title>Results</title><p>From the analysis of the asymptotic behavior of minimizers, forward and local schemes, we show that the previously believed lower bound on minimizers schemes does not hold, and that schemes with density lower than thought possible actually exist. The proof is constructive and leads to an efficient algorithm to compare <italic>k</italic>-mers. These orders are the first known orders that are asymptotically optimal. Additionally, we give improved bounds on the density achievable by the three type of schemes.</p></sec></div></front><back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="De Bruijn, N G" uniqKey="De Bruijn N">N.G. de Bruijn</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Deorowicz, S" uniqKey="Deorowicz S">S. Deorowicz</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Grabowski, S" uniqKey="Grabowski S">S. Grabowski</name></author><author><name sortKey="Raniszewski, M" uniqKey="Raniszewski M">M. Raniszewski</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Kawulok, J" uniqKey="Kawulok J">J. Kawulok</name></author><author><name sortKey="Deorowicz, S" uniqKey="Deorowicz S">S. Deorowicz</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Lempel, A" uniqKey="Lempel A">A. Lempel</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Li, H" uniqKey="Li H">H. Li</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Li, Y" uniqKey="Li Y">Y. Li</name></author><author><name sortKey="Xifengyan, X" uniqKey="Xifengyan X">X. XifengYan</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Li, Y" uniqKey="Li Y">Y. Li</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Lichiardopol, N" uniqKey="Lichiardopol N">N. Lichiardopol</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Marcais, G" uniqKey="Marcais G">G. Marçais</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Maurer, U M" uniqKey="Maurer U">U.M. Maurer</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Mykkeltveit, J" uniqKey="Mykkeltveit J">J. Mykkeltveit</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Ondov, B D" uniqKey="Ondov B">B.D. Ondov</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Orenstein, Y" uniqKey="Orenstein Y">Y. Orenstein</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Paindavoine, M" uniqKey="Paindavoine M">M. Paindavoine</name></author><author><name sortKey="Vialla, B" uniqKey="Vialla B">B. Vialla</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Roberts, M" uniqKey="Roberts M">M. Roberts</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Roberts, M" uniqKey="Roberts M">M. Roberts</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Schleimer, S" uniqKey="Schleimer S">S. Schleimer</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Wood, D E" uniqKey="Wood D">D.E. Wood</name></author><author><name sortKey="Salzberg, S L" uniqKey="Salzberg S">S.L. Salzberg</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Ye, C" uniqKey="Ye C">C. Ye</name></author></analytic></biblStruct></listBibl></div1></back></TEI><pmc article-type="research-article"><pmc-dir>properties open_access</pmc-dir>
<front><journal-meta><journal-id journal-id-type="nlm-ta">Bioinformatics</journal-id><journal-id journal-id-type="iso-abbrev">Bioinformatics</journal-id><journal-id journal-id-type="publisher-id">bioinformatics</journal-id><journal-title-group><journal-title>Bioinformatics</journal-title></journal-title-group><issn pub-type="ppub">1367-4803</issn><issn pub-type="epub">1367-4811</issn><publisher><publisher-name>Oxford University Press</publisher-name></publisher></journal-meta><article-meta><article-id pub-id-type="pmid">29949995</article-id><article-id pub-id-type="pmc">6037127</article-id><article-id pub-id-type="doi">10.1093/bioinformatics/bty258</article-id><article-id pub-id-type="publisher-id">bty258</article-id><article-categories><subj-group subj-group-type="heading"><subject>Ismb 2018–Intelligent Systems for Molecular Biology Proceedings</subject><subj-group subj-group-type="category-toc-heading"><subject>Bioinformatics of Microbes and Microbiomes</subject></subj-group></subj-group></article-categories><title-group><article-title>Asymptotically optimal minimizers schemes</article-title></title-group><contrib-group><contrib contrib-type="author"><name><surname>Marçais</surname><given-names>Guillaume</given-names></name><xref ref-type="aff" rid="bty258-aff1"></xref><xref ref-type="corresp" rid="bty258-cor1"></xref><pmc-comment>gmarcais@cs.cmu.edu </pmc-comment>
</contrib><contrib contrib-type="author"><name><surname>DeBlasio</surname><given-names>Dan</given-names></name><xref ref-type="aff" rid="bty258-aff1"></xref></contrib><contrib contrib-type="author"><name><surname>Kingsford</surname><given-names>Carl</given-names></name><xref ref-type="aff" rid="bty258-aff1"></xref><xref ref-type="corresp" rid="bty258-cor1"></xref><pmc-comment>ckingsf@cs.cmu.edu </pmc-comment>
</contrib></contrib-group><aff id="bty258-aff1">Department of Computational Biology, Carnegie Mellon University, Pittsburgh, PA, USA</aff><author-notes><corresp id="bty258-cor1">To whom correspondence should be addressed. <email>gmarcais@cs.cmu.edu</email> or <email>ckingsf@cs.cmu.edu</email></corresp></author-notes><pub-date pub-type="ppub"><day>01</day><month>7</month><year>2018</year></pub-date><pub-date pub-type="epub" iso-8601-date="2018-06-27"><day>27</day><month>6</month><year>2018</year></pub-date><pub-date pub-type="pmc-release"><day>27</day><month>6</month><year>2018</year></pub-date><pmc-comment> PMC Release delay is 0 months and 0 days and was based on the
<volume>34</volume><issue>13</issue><issue-title>ISMB 2018 Proceedings July 6 to July 10, 2018, Chicago, IL, United States</issue-title><fpage>i13</fpage><lpage>i22</lpage><permissions><copyright-statement>© The Author(s) 2018. Published by Oxford University Press.</copyright-statement><copyright-year>2018</copyright-year><license license-type="cc-by-nc" xlink:href="http://creativecommons.org/licenses/by-nc/4.0/"><license-p>This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (<ext-link ext-link-type="uri" xlink:href="http://creativecommons.org/licenses/by-nc/4.0/">http://creativecommons.org/licenses/by-nc/4.0/</ext-link>), which permits non-commercial re-use, distribution, and reproduction in any medium, provided the original work is properly cited. For commercial re-use, please contact journals.permissions@oup.com</license-p></license></permissions><self-uri xlink:href="bty258.pdf"></self-uri><abstract><title>Abstract</title><sec id="s1"><title>Motivation</title><p>The minimizers technique is a method to sample <italic>k</italic>-mers that is used in many bioinformatics software to reduce computation, memory usage and run time. The number of applications using minimizers keeps on growing steadily. Despite its many uses, the theoretical understanding of minimizers is still very limited. In many applications, selecting as few <italic>k</italic>-mers as possible (i.e. having a low <italic>density</italic>) is beneficial. The density is highly dependent on the choice of the order on the <italic>k</italic>-mers. Different applications use different orders, but none of these orders are optimal. A better understanding of minimizers schemes, and the related local and forward schemes, will allow designing schemes with lower density and thereby making existing and future bioinformatics tools even more efficient.</p></sec><sec id="s2"><title>Results</title><p>From the analysis of the asymptotic behavior of minimizers, forward and local schemes, we show that the previously believed lower bound on minimizers schemes does not hold, and that schemes with density lower than thought possible actually exist. The proof is constructive and leads to an efficient algorithm to compare <italic>k</italic>-mers. These orders are the first known orders that are asymptotically optimal. Additionally, we give improved bounds on the density achievable by the three type of schemes.</p></sec></abstract><funding-group><award-group award-type="grant"><funding-source><named-content content-type="funder-name">Gordon and Betty Moore Foundation’s Data-Driven Discovery Initiative</named-content></funding-source><award-id>GBMF4554</award-id></award-group><award-group award-type="grant"><funding-source><named-content content-type="funder-name">US National Science Foundation</named-content></funding-source><award-id>CCF-1256087</award-id><award-id>CCF-1319998</award-id></award-group><award-group award-type="grant"><funding-source><named-content content-type="funder-name">US National Institutes of Health</named-content></funding-source><award-id>R01HG007104</award-id><award-id>R01GM122935</award-id></award-group></funding-group><counts><page-count count="10"></page-count></counts></article-meta></front><body><sec><title>1 Introduction</title><p>The <italic>minimizers</italic> technique is a method (Roberts <italic>et al.</italic>, <xref rid="bty258-B16" ref-type="bibr">2004a</xref>, <xref rid="bty258-B17" ref-type="bibr">b</xref>; <xref rid="bty258-B18" ref-type="bibr">Schleimer <italic>et al.</italic>, 2003</xref>) to sample <italic>k</italic>-mers from a sequence. It has two important properties: (i) there is no large gap in the sampling and (ii) from similar sequences similar <italic>k</italic>-mers are sampled. Minimizers help design algorithms that are more efficient both in memory usage and run time by reducing the amount of information to process, while not losing information.</p><p>The minimizers method is very flexible and has been used in a surprising large number of settings, from the original computation of read overlaps (Roberts <italic>et al.</italic>, <xref rid="bty258-B16" ref-type="bibr">2004a</xref>, <xref rid="bty258-B17" ref-type="bibr">b</xref>), to counting <italic>k</italic>-mers (<xref rid="bty258-B2" ref-type="bibr">Deorowicz <italic>et al.</italic>, 2015</xref>; <xref rid="bty258-B7" ref-type="bibr">Li and XifengYan, 2015</xref>), reducing the genome assembly de Bruijn graph (<xref rid="bty258-B8" ref-type="bibr">Li <italic>et al.</italic>, 2013</xref>; <xref rid="bty258-B20" ref-type="bibr">Ye <italic>et al.</italic>, 2012</xref>), making sequence alignment faster (<xref rid="bty258-B6" ref-type="bibr">Li, 2016</xref>; <xref rid="bty258-B13" ref-type="bibr">Ondov <italic>et al.</italic>, 2016</xref>), to metagenomics (<xref rid="bty258-B4" ref-type="bibr">Kawulok and Deorowicz, 2015</xref>; <xref rid="bty258-B19" ref-type="bibr">Wood and Salzberg, 2014</xref>) and sparse data structures (<xref rid="bty258-B3" ref-type="bibr">Grabowski and Raniszewski, 2015</xref>).</p><p>The minimizers method has two parameters, <italic>k</italic> the length of the <italic>k</italic>-mers and <italic>w</italic> the maximum distance between two sampled <italic>k</italic>-mers in the input sequence (called the window size). Additionally, the minimizers scheme is parameterized by the choice of a complete order on the <italic>k</italic>-mers, for example the lexicographic order. The minimizers scheme then selects in the input sequence the smallest <italic>k</italic>-mer, according to the predefined order, in each window of <italic>w</italic> consecutive <italic>k</italic>-mers.</p><p>Any choice of an order on the <italic>k</italic>-mers is valid in the sense that properties (i) and (ii) above are satisfied. The <italic>density</italic>, i.e. the expected number of selected <italic>k</italic>-mers over the length of the input sequence, is affected by the choice of the order on the <italic>k</italic>-mers. For many applications, a lower density is preferable as it reduces the amount of data to process. The density of any minimizers scheme is at least <inline-formula id="IE1"><mml:math id="IM1"><mml:mrow><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula>, as at least 1 <italic>k</italic>-mer is selected in each window, and at most 1, when every <italic>k</italic>-mer in the sequence is selected. These are the trivial bounds.</p><p>Although bioinformatics tool developers chose many different orders for their applications, in most cases, these orders are not an integral part of their algorithm. That is, if one were to change the order in a given application, the results returned by the application would be unchanged or equivalent, although the run time or memory usage may be different. Therefore, the development of <italic>k</italic>-mer orders giving lower density would benefit new and existing applications.</p><p>In addition to minimizers schemes, we consider two generalizations: local schemes and forward schemes. Local schemes are the most general schemes as they use any function defined on a set of <italic>w k</italic>-mers. The forward schemes are local schemes with the additional requirement that the <italic>k</italic>-mers are selected in an increasing manner from the input sequence (minimizers schemes are an example of forward schemes). From the more specific to the more general schemes, we have
<disp-formula id="E1"><mml:math id="M1"><mml:mrow><mml:mtext>minimizers</mml:mtext><mml:mo>⊂</mml:mo><mml:mtext>forward</mml:mtext><mml:mo>⊂</mml:mo><mml:mtext>local</mml:mtext><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula>Similarly, from the point of view of a bioinformatics application, these other two types of schemes can be used as a drop-in replacement of a minimizers scheme: they have the same parameters <italic>k</italic> and <italic>w</italic>, the same input and output, and they satisfy properties (i) and (ii).</p><p><xref rid="bty258-B18" ref-type="bibr">Schleimer <italic>et al.</italic> (2003)</xref> showed an expected density of <inline-formula id="IE2"><mml:math id="IM2"><mml:mrow><mml:mn>2</mml:mn><mml:mo>/</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> for some class of minimizers schemes and showed a lower-bound of <inline-formula id="IE3"><mml:math id="IM3"><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mn>1.5</mml:mn><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mn>2</mml:mn><mml:mi>w</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>/</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>. This later bound only applies to randomized and not all local schemes as previously believed. <xref rid="bty258-B10" ref-type="bibr">Marçais <italic>et al.</italic> (2017)</xref> used a heuristic method to create minimizers schemes with density below <inline-formula id="IE4"><mml:math id="IM4"><mml:mrow><mml:mn>2</mml:mn><mml:mo>/</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>, but still above the <inline-formula id="IE5"><mml:math id="IM5"><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mn>1.5</mml:mn><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mn>2</mml:mn><mml:mi>w</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>/</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> bound.</p><p>We study the asymptotic behavior in <italic>k</italic> and <italic>w</italic> of local, forward and minimizers schemes. This study leads to the realization that the previously believed lower-bound on the achievable density of local schemes does not apply. We give concrete examples of minimizers schemes with density below that former lower-bound. This opens up the field for much greater improvements in density from minimizers, forward and local schemes. Also, the results of this study give directions for further potential improvements.</p><p>We present three main results in this paper.
<list list-type="roman-lower"><list-item><p>For fixed <italic>w</italic> and asymptotically in <italic>k</italic>, we show that there exist minimizers schemes that achieve optimal density. This is the first example of schemes that achieve optimal density. Because minimizers schemes are the most specific schemes, optimality is also achieved by local and forward schemes and this completely characterizes the behavior for fixed <italic>w</italic> and asymptotic in <italic>k</italic>.</p></list-item><list-item><p>For fixed <italic>k</italic> and asymptotically in <italic>w</italic>, we derive new lower-bounds for minimizers and forward schemes, which show that neither of these schemes can be optimal when <italic>w</italic> is much larger than <italic>k</italic>. Furthermore, we show that the local schemes are strictly more powerful than forward schemes by finding optimal local schemes for some parameters <italic>k</italic> and <italic>w</italic> with density not achievable by forward schemes.</p></list-item><list-item><p>We prove a lower-bound on the density of forward schemes that is valid for all parameters <italic>k</italic> and <italic>w</italic>. This lower-bound is a refinement of the bound proposed by <xref rid="bty258-B18" ref-type="bibr">Schleimer <italic>et al.</italic> (2003)</xref>.</p></list-item></list></p><p>Additionally, these results give two practical algorithms. The first one computes a set of <italic>k</italic>-mers that covers every path of length <italic>w</italic> in the de Bruijn graph (an extension of the set cover problem). This problem was studied in <xref rid="bty258-B14" ref-type="bibr">Orenstein <italic>et al.</italic> (2017)</xref> and <xref rid="bty258-B10" ref-type="bibr">Marçais <italic>et al.</italic> (2017)</xref>, and this new algorithm gives an asymptotically optimal solution. The second algorithm gives the order between <italic>k</italic>-mers for the minimizers schemes in (i). This algorithm is efficient as it only takes <italic>O</italic>(<italic>k</italic>) time to compare two <italic>k</italic>-mers.</p><p>In the next section, we give precise definitions of the various concepts and a statement of the main theorems. Section 3 gives detailed proofs of the theorems, followed by a discussion of remaining open problems (Section 4).</p></sec><sec><title>2 Approach</title><sec><title>2.1 Definitions</title><sec><title><italic>2.1.1</italic> Basic definitions</title><p>Let Σ be an alphabet of size <inline-formula id="IE6"><mml:math id="IM6"><mml:mrow><mml:mo>σ</mml:mo><mml:mo>=</mml:mo><mml:mo>|</mml:mo><mml:mo>Σ</mml:mo><mml:mo>|</mml:mo></mml:mrow></mml:math></inline-formula>. If <inline-formula id="IE7"><mml:math id="IM7"><mml:mrow><mml:mi>S</mml:mi><mml:mo>∈</mml:mo><mml:msup><mml:mo>Σ</mml:mo><mml:mo>*</mml:mo></mml:msup></mml:mrow></mml:math></inline-formula> is a string on alphabet Σ, <inline-formula id="IE8"><mml:math id="IM8"><mml:mrow><mml:mi>S</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo>,</mml:mo><mml:mo>ℓ</mml:mo><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula> is the substring of <italic>S</italic> starting at position <italic>i</italic> and of length <italic>ℓ</italic>. In many cases in the following the strings are circular: offsets in the string are understood modulo the length of the string and a substring extending beyond the end of the string wraps around to the beginning of the string. The substring <inline-formula id="IE9"><mml:math id="IM9"><mml:mrow><mml:mo>ω</mml:mo><mml:mo>=</mml:mo><mml:mi>S</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula> represents the sequence of a window <italic>ω</italic> of <italic>w</italic> consecutive <italic>k</italic>-mers starting at offset <italic>i</italic> in <italic>S</italic>.</p></sec><sec><title><italic>2.1.2</italic> Schemes</title><p>A <italic>local scheme</italic> is a function that selects a <italic>k</italic>-mer in a window of <italic>w</italic> consecutive <italic>k</italic>-mers, i.e. <inline-formula id="IE10"><mml:math id="IM10"><mml:mrow><mml:mi>f</mml:mi><mml:mo>:</mml:mo><mml:msup><mml:mo>Σ</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo>→</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mn>0</mml:mn><mml:mo>:</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>.</p><p>A <italic>forward scheme</italic> is a particular local scheme where the sequence of the starting positions of the selected <italic>k</italic>-mers is an increasing sequence. Equivalently, a local scheme <inline-formula id="IE11"><mml:math id="IM11"><mml:mrow><mml:mi>f</mml:mi><mml:mo>:</mml:mo><mml:msup><mml:mo>Σ</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo>→</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mn>0</mml:mn><mml:mo>:</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula> is a forward scheme if
<disp-formula id="E2"><mml:math id="M2"><mml:mrow><mml:mo>∀</mml:mo><mml:mo>ω</mml:mo><mml:mo>∈</mml:mo><mml:msup><mml:mo>Σ</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo>,</mml:mo><mml:mo>∀</mml:mo><mml:mi>x</mml:mi><mml:mo>∈</mml:mo><mml:mo>Σ</mml:mo><mml:mo>,</mml:mo><mml:mi>f</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mo>ω</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="true">]</mml:mo><mml:mo>·</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>≥</mml:mo><mml:mi>f</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mo>ω</mml:mo><mml:mo stretchy="true">)</mml:mo><mml:mo>−</mml:mo><mml:mn>1.</mml:mn></mml:mrow></mml:math></disp-formula>The dot is the concatenation operator and <inline-formula id="IE12"><mml:math id="IM12"><mml:mrow><mml:mo>ω</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="true">]</mml:mo><mml:mo>·</mml:mo><mml:mi>x</mml:mi><mml:mo>,</mml:mo></mml:mrow></mml:math></inline-formula><inline-formula id="IE601"><mml:math id="IM13"><mml:mrow><mml:mo>∀</mml:mo><mml:mi>x</mml:mi><mml:mo>∈</mml:mo><mml:mo>Σ</mml:mo></mml:mrow></mml:math></inline-formula> represents all the possible windows following <italic>ω</italic>.</p><p>A <italic>minimizers scheme</italic> is a particular local scheme where the function returns the left-most position of the smallest <italic>k</italic>-mer in the window. All minimizers schemes are forward schemes, and forward schemes are local schemes, but those sets are not equal to each other.</p></sec><sec><title><italic>2.1.3</italic> Density</title><p>The set of <italic>selected indices</italic> of a scheme <italic>f</italic> on string <italic>S</italic> is
<disp-formula id="E3"><mml:math id="M3"><mml:mrow><mml:msub><mml:mi mathvariant="script">S</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>S</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mo>{</mml:mo><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mi>f</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi>S</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo><mml:mo stretchy="true">)</mml:mo><mml:mo> </mml:mo><mml:mo>|</mml:mo><mml:mo> </mml:mo><mml:mi>i</mml:mi><mml:mo>∈</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mo>|</mml:mo><mml:mi>S</mml:mi><mml:mo>|</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo><mml:mo>}</mml:mo><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula>Because the scheme may select in adjacent windows the same position in <italic>S</italic>, <inline-formula id="IE13"><mml:math id="IM14"><mml:mrow><mml:mo>|</mml:mo><mml:msub><mml:mi mathvariant="script">S</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>S</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>|</mml:mo><mml:mo>≤</mml:mo><mml:mo>|</mml:mo><mml:mi>S</mml:mi><mml:mo>|</mml:mo></mml:mrow></mml:math></inline-formula>. The <italic>particular density</italic> of a scheme <italic>f</italic> on the circular string <italic>S</italic> is the proportion of <italic>k</italic>-mers selected: <inline-formula id="IE14"><mml:math id="IM15"><mml:mrow><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>S</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mo>|</mml:mo><mml:msub><mml:mi mathvariant="script">S</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>S</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>|</mml:mo><mml:mo>/</mml:mo><mml:mo>|</mml:mo><mml:mi>S</mml:mi><mml:mo>|</mml:mo></mml:mrow></mml:math></inline-formula>.</p><p>The <italic>density</italic> of a scheme <inline-formula id="IE15"><mml:math id="IM16"><mml:mrow><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> is defined at the limit as the expected density on an infinitely long sequence with the characters selected Independent Identical Distribution (IID). The trivial bounds for the density are <inline-formula id="IE16"><mml:math id="IM17"><mml:mrow><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mi>w</mml:mi><mml:mo>≤</mml:mo><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo>≤</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula>. Following <xref rid="bty258-B10" ref-type="bibr">Marçais <italic>et al.</italic> (2017)</xref>, we define the <italic>density factor</italic><inline-formula id="IE17"><mml:math id="IM18"><mml:mrow><mml:mtext>df</mml:mtext><mml:mo>=</mml:mo><mml:mi>d</mml:mi><mml:mo>·</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>, which represents the average number of <italic>k</italic>-mers selected in every window of length <italic>w</italic> + 1. The trivial bounds for the density factors are <inline-formula id="IE18"><mml:math id="IM19"><mml:mrow><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mi>w</mml:mi><mml:mo>≤</mml:mo><mml:msub><mml:mrow><mml:mtext>df</mml:mtext></mml:mrow><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo>≤</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula>.</p></sec><sec><title><italic>2.1.4</italic> Computing density</title><p>A <italic>de Bruijn sequence</italic> of order <italic>ℓ</italic> is any circular sequence of length <inline-formula id="IE19"><mml:math id="IM20"><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mo>ℓ</mml:mo></mml:msup></mml:mrow></mml:math></inline-formula> such that every possible substring of length <italic>ℓ</italic> occurs once and only once in the string (<xref rid="bty258-B1" ref-type="bibr">de Bruijn, 1946</xref>). In the following, <inline-formula id="IE20"><mml:math id="IM21"><mml:mrow><mml:msub><mml:mi>D</mml:mi><mml:mo>ℓ</mml:mo></mml:msub></mml:mrow></mml:math></inline-formula> represents the de Bruijn graph of order <italic>ℓ</italic>. A de Bruijn sequence is obtained by reading the first base of every vertex traversed by a Hamiltonian tour of a de Bruijn graph <inline-formula id="IE21"><mml:math id="IM22"><mml:mrow><mml:msub><mml:mi>D</mml:mi><mml:mo>ℓ</mml:mo></mml:msub></mml:mrow></mml:math></inline-formula> of order <italic>ℓ</italic>.</p><p>Even though the density is defined as the limit of an expected value on an infinite string, it can be computed exactly (and not just estimated) as the particular density computed on a de Bruijn sequence of large enough order (<xref rid="bty258-B10" ref-type="bibr">Marçais <italic>et al.</italic>, 2017</xref>). For any de Bruijn sequence <inline-formula id="IE22"><mml:math id="IM23"><mml:mrow><mml:msub><mml:mi>S</mml:mi><mml:mo>ℓ</mml:mo></mml:msub></mml:mrow></mml:math></inline-formula> of order <inline-formula id="IE23"><mml:math id="IM24"><mml:mrow><mml:mo>ℓ</mml:mo><mml:mo>≥</mml:mo><mml:mn>2</mml:mn><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math></inline-formula>, the particular density of <italic>f</italic> on <inline-formula id="IE24"><mml:math id="IM25"><mml:mrow><mml:msub><mml:mi>S</mml:mi><mml:mo>ℓ</mml:mo></mml:msub></mml:mrow></mml:math></inline-formula> is equal to the density of <italic>f</italic>: <inline-formula id="IE25"><mml:math id="IM26"><mml:mrow><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi>S</mml:mi><mml:mo>ℓ</mml:mo></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>. For a forward scheme, the minimum order of the de Bruijn sequence is only <italic>w </italic>+<italic> k</italic>.</p></sec><sec><title><italic>2.1.5</italic> Universal set</title><p>A <italic>universal set</italic> is an unavoidable set of <italic>k</italic>-mers: it is a set <inline-formula id="IE26"><mml:math id="IM27"><mml:mrow><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> such that every path of <italic>w</italic> nodes in the de Bruijn graph of order <italic>k</italic> contains a <italic>k</italic>-mer from <inline-formula id="IE27"><mml:math id="IM28"><mml:mrow><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula>. In other words, a universal set is a set of nodes of <italic>D<sub>k</sub></italic> that covers every path of <italic>w</italic> nodes. Equivalently, every string of length <inline-formula id="IE28"><mml:math id="IM29"><mml:mrow><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula> must contain a substring of length <italic>k</italic> from <inline-formula id="IE29"><mml:math id="IM30"><mml:mrow><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula>.</p><p>There is a strong link between universal sets and minimizers schemes. A minimizers scheme is <italic>compatible</italic> with a universal set <inline-formula id="IE30"><mml:math id="IM31"><mml:mrow><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> if every <italic>k</italic>-mer of <inline-formula id="IE31"><mml:math id="IM32"><mml:mrow><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> compares less than any <italic>k</italic>-mer not in <inline-formula id="IE32"><mml:math id="IM33"><mml:mrow><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula>. There is more than one order which is compatible with a universal set, as the relative order of the <italic>k</italic>-mers within <inline-formula id="IE33"><mml:math id="IM34"><mml:mrow><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> is not constrained by the definition. Although this relative order may change the density of the scheme, it is not relevant in our asymptotic analysis.</p></sec></sec><sec><title>2.2 Main results</title><sec><title><italic>2.2.1</italic> Behavior asymptotically in <italic>k</italic></title><p>We show that for any fixed value of <italic>w</italic>, there exists a sequence of minimizers schemes that asymptotically achieve optimal density, i.e. one <italic>k</italic>-mer per window or <inline-formula id="IE34"><mml:math id="IM35"><mml:mrow><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula>. These are the first proposed orders that achieve close to optimal density. It is also the first orders to have density factors below <inline-formula id="IE35"><mml:math id="IM36"><mml:mrow><mml:mn>1.5</mml:mn><mml:mo>+</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mn>2</mml:mn><mml:mi>w</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>, which was formerly considered the lowest possible density factor. Surprisingly, this optimal density is attained with minimizers schemes, the weakest type of schemes.</p><p>The sequence of minimizers schemes is created from universal sets. The following Lemma shows an important link between universal sets and minimizers scheme: the size of a universal set upper-bounds the density of any compatible minimizers scheme.</p><statement id="mthst1"><p><italic>Lemma 1</italic>. Given a minimizers scheme <italic>f<sub>U</sub></italic> compatible with a universal set <italic>U</italic>, the density satisfies
<disp-formula id="E4"><mml:math id="M4"><mml:mrow><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:msub><mml:mi>f</mml:mi><mml:mi>U</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo>≤</mml:mo><mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:mi>U</mml:mi><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>The strategy is then to construct a sequence of universal sets whose sizes get close to <inline-formula id="IE36"><mml:math id="IM37"><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula>. This gives us our first main result, that optimal minimizers schemes exist asymptotically in <italic>k</italic> for alphabet of even sizes.</p></statement><statement id="mthst2"><p><italic>Theorem 1</italic>. On an even alphabet, for any fixed <italic>w</italic>, there exists a sequence of universal sets <italic>U<sub>k</sub></italic> asymptotically of optimal size and a sequence of minimizers schemes <italic>f<sub>k</sub></italic> asymptotically of optimal density.</p><p>The proof of this theorem relies on a geometric argument. The de Bruijn graph is embedded in a <italic>w</italic>-dimensional space, a hypercube with <italic>w</italic> dimensions, such that the <italic>k</italic>-mers mapping into a particular volume of the cube is a universal set. Then, we show that asymptotically the number of <italic>k</italic>-mers mapping into that volume represents a proportion <inline-formula id="IE37"><mml:math id="IM38"><mml:mrow><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula> of the total number of <italic>k</italic>-mers. This line of proof is a generalization of the construction of asymptotically minimum vertex cover by <xref rid="bty258-B9" ref-type="bibr">Lichiardopol (2006)</xref>.</p></statement></sec><sec><title><italic>2.2.2</italic> Behavior asymptotically in <italic>w</italic></title><p>The previously mentioned bounds on density of <inline-formula id="IE38"><mml:math id="IM39"><mml:mrow><mml:mn>2</mml:mn><mml:mo>/</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> might give the impression that, as <italic>w</italic> gets large, arbitrarily small density can be achieved. It is not the case for minimizers schemes which have a lower limit on the density greater than 0.</p><statement id="mthst3"><p><italic>Theorem 2</italic>. For any minimizers scheme <italic>f</italic>, the density <inline-formula id="IE39"><mml:math id="IM40"><mml:mrow><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> converges asymptotically in <italic>w</italic> to <inline-formula id="IE40"><mml:math id="IM41"><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:mo>−</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:math></inline-formula>:
<disp-formula id="E5"><mml:math id="M5"><mml:mrow><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:munder><mml:mo stretchy="true">→</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>→</mml:mo><mml:mo>∞</mml:mo></mml:mrow></mml:munder><mml:mfrac><mml:mn>1</mml:mn><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>Forward schemes and local schemes do not have such a lower-bound on their density, and we will construct a forward scheme with a density going to 0 asymptotically in <italic>w</italic>. In such cases, it is more meaningful to speak of the density factor. The lowest density factor for minimizers is <inline-formula id="IE41"><mml:math id="IM42"><mml:mrow><mml:mo>Ω</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>w</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>, while the lowest density factor for forward schemes is <inline-formula id="IE42"><mml:math id="IM43"><mml:mrow><mml:mi>O</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:msqrt><mml:mi>w</mml:mi></mml:msqrt><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>.</p></statement></sec><sec><title><italic>2.2.3</italic> Forward schemes bound</title><p>Finally, we prove a lower-bound on the density for forward schemes, which holds for any parameters <italic>k</italic> and <italic>w</italic>.</p><statement id="mthst4"><p><italic>Theorem 3</italic>. The density of any forward scheme satisfies
<disp-formula id="E6"><mml:math id="M6"><mml:mrow><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo>≥</mml:mo><mml:mfrac><mml:mrow><mml:mn>1.5</mml:mn><mml:mo>+</mml:mo><mml:mi>max</mml:mi><mml:mo></mml:mo><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mrow><mml:mo stretchy="true">⌊</mml:mo><mml:mrow><mml:mfrac><mml:mrow><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mi>w</mml:mi></mml:mrow><mml:mi>w</mml:mi></mml:mfrac></mml:mrow><mml:mo stretchy="true">⌋</mml:mo></mml:mrow></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mo>+</mml:mo><mml:mfrac><mml:mn>1</mml:mn><mml:mrow><mml:mn>2</mml:mn><mml:mi>w</mml:mi></mml:mrow></mml:mfrac></mml:mrow><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:mfrac><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>Asymptotically in <italic>w</italic>, this bound implies that the best density factor for forward schemes is <inline-formula id="IE43"><mml:math id="IM44"><mml:mrow><mml:mo>≥</mml:mo><mml:mn>1.5</mml:mn></mml:mrow></mml:math></inline-formula>. This is much lower than the lower-bound for minimizers schemes, although it is not known yet how to construct a forward scheme approaching that lower-bound for large values of <italic>w</italic>.</p></statement></sec></sec></sec><sec><title>3 Proofs of main theorems</title><sec><title>3.1 Minimizers asymptotic behavior in <italic>k</italic></title><p>We consider in this section the behavior of minimizers schemes when the length of the window <italic>w</italic> is fixed while the length of the <italic>k</italic>-mer goes to infinity. In particular, we will construct asymptotically optimal minimizers schemes. Given that a local scheme must select at least one <italic>k</italic>-mer in each window, the minimum density is <inline-formula id="IE44"><mml:math id="IM45"><mml:mrow><mml:mo>≥</mml:mo><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula>. So, more precisely, we construct a minimizers scheme <italic>f</italic> such that <inline-formula id="IE45"><mml:math id="IM46"><mml:mrow><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mstyle displaystyle="true"><mml:munder><mml:mo stretchy="true">→</mml:mo><mml:mrow><mml:mi>k</mml:mi><mml:mo>→</mml:mo><mml:mo>∞</mml:mo></mml:mrow></mml:munder></mml:mstyle><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula>. To do so, we use the link between universal sets and orderings.</p><p>Recall that given a universal set <italic>U</italic>, a set that intersects every <italic>w</italic>-long path in the de Bruijn graph <inline-formula id="IE46"><mml:math id="IM47"><mml:mrow><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula>, the minimizers scheme <italic>f</italic> is compatible with <italic>U</italic> if every <italic>k</italic>-mer of <italic>U</italic> compares less than any <italic>k</italic>-mer not in <italic>U</italic>. The following Lemma explains the fundamental link between universal sets and orderings.</p><statement id="mthst5"><p><italic>Lemma 1</italic>. Given a minimizers scheme <italic>f<sub>U</sub></italic> compatible with a universal set <italic>U</italic>, the density satisfies
<disp-formula id="E7"><mml:math id="M7"><mml:mrow><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:msub><mml:mi>f</mml:mi><mml:mi>U</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo>≤</mml:mo><mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:mi>U</mml:mi><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p><italic>P<sc>roof</sc></italic>. Let <inline-formula id="IE47"><mml:math id="IM48"><mml:mrow><mml:msub><mml:mi>S</mml:mi><mml:mo>ℓ</mml:mo></mml:msub></mml:mrow></mml:math></inline-formula> be a de Bruijn sequence of order <inline-formula id="IE48"><mml:math id="IM49"><mml:mrow><mml:mo>ℓ</mml:mo><mml:mo>≥</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:math></inline-formula>. Because <italic>U</italic> is a universal set, every window of <italic>w</italic> consecutive <italic>k</italic>-mers contains at least one element of <italic>U</italic>, hence all the selected <italic>k</italic>-mers are from the set <italic>U</italic>. Therefore, <inline-formula id="IE49"><mml:math id="IM50"><mml:mrow><mml:msub><mml:mi mathvariant="script">S</mml:mi><mml:mrow><mml:msub><mml:mi>f</mml:mi><mml:mi>U</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> contains, at most, all the positions in <inline-formula id="IE501"><mml:math id="IM51"><mml:mrow><mml:msub><mml:mi>S</mml:mi><mml:mo>ℓ</mml:mo></mml:msub></mml:mrow></mml:math></inline-formula> of the <italic>k</italic>-mers of <italic>U</italic>. Moreover, every <italic>k</italic>-mer occurs exactly <inline-formula id="IE50"><mml:math id="IM52"><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:mo>ℓ</mml:mo><mml:mo>−</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:math></inline-formula> times in <inline-formula id="IE51"><mml:math id="IM53"><mml:mrow><mml:msub><mml:mi>S</mml:mi><mml:mo>ℓ</mml:mo></mml:msub></mml:mrow></mml:math></inline-formula>. Hence
<disp-formula id="E8"><label>(1)</label><mml:math id="M8"><mml:mrow><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:msub><mml:mi>f</mml:mi><mml:mi>U</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:msub><mml:mi mathvariant="script">S</mml:mi><mml:mrow><mml:msub><mml:mi>f</mml:mi><mml:mi>U</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi>S</mml:mi><mml:mo>ℓ</mml:mo></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mo>ℓ</mml:mo></mml:msup></mml:mrow></mml:mfrac><mml:mo>≤</mml:mo><mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:mi>U</mml:mi><mml:mo>|</mml:mo><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:mo>ℓ</mml:mo><mml:mo>−</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msup></mml:mrow><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mo>ℓ</mml:mo></mml:msup></mml:mrow></mml:mfrac><mml:mo>=</mml:mo><mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:mi>U</mml:mi><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p> □</p><p>This Lemma gives a simple lower-bound on the size of a universal set for a de Bruijn graph. Define <inline-formula id="IE52"><mml:math id="IM54"><mml:mrow><mml:msub><mml:mo>β</mml:mo><mml:mi>w</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>G</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> to be the minimum size of a universal set for a graph <italic>G</italic> that hits every path of <italic>w</italic> vertices. This notation is an extension of the definition of the size of the minimum vertex cover: <inline-formula id="IE53"><mml:math id="IM55"><mml:mrow><mml:msub><mml:mo>β</mml:mo><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>G</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mo>β</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>G</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>.</p></statement><statement id="mthst6"><p><italic>Proposition 1</italic>. The minimum size of a universal set satisfies:
<disp-formula id="E9"><mml:math id="M9"><mml:mrow><mml:msub><mml:mo>β</mml:mo><mml:mi>w</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>≥</mml:mo><mml:mfrac><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow><mml:mi>w</mml:mi></mml:mfrac><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p><italic>P<sc>roof</sc></italic>. Let <italic>U</italic> be a universal set of minimum size, <inline-formula id="IE54"><mml:math id="IM56"><mml:mrow><mml:mo>|</mml:mo><mml:mi>U</mml:mi><mml:mo>|</mml:mo><mml:mo>=</mml:mo><mml:msub><mml:mo>β</mml:mo><mml:mi>w</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> and <italic>f<sub>U</sub></italic> a minimizers scheme compatible with <italic>U</italic>. By Lemma 1
<disp-formula id="E10"><label>(2)</label><mml:math id="M10"><mml:mrow><mml:mfrac><mml:mn>1</mml:mn><mml:mi>w</mml:mi></mml:mfrac><mml:mo>≤</mml:mo><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:msub><mml:mi>f</mml:mi><mml:mi>U</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo>≤</mml:mo><mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:mi>U</mml:mi><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac><mml:mo>⇒</mml:mo><mml:msub><mml:mo>β</mml:mo><mml:mi>w</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>≥</mml:mo><mml:mfrac><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow><mml:mi>w</mml:mi></mml:mfrac><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p> □</p><p>A second consequence of Lemma 1 is that a sequence of universal set <italic>U<sub>k</sub></italic> that is asymptotically optimal, i.e. such that <inline-formula id="IE55"><mml:math id="IM57"><mml:mrow><mml:mo>|</mml:mo><mml:msub><mml:mi>U</mml:mi><mml:mi>k</mml:mi></mml:msub><mml:mo>|</mml:mo><mml:mo>/</mml:mo><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup><mml:mstyle displaystyle="true"><mml:munder><mml:mo stretchy="true">→</mml:mo><mml:mrow><mml:mi>k</mml:mi><mml:mo>→</mml:mo><mml:mo>∞</mml:mo></mml:mrow></mml:munder></mml:mstyle><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula>, gives a sequence of minimizers schemes <inline-formula id="IE56"><mml:math id="IM58"><mml:mrow><mml:msub><mml:mi>f</mml:mi><mml:mrow><mml:msub><mml:mi>U</mml:mi><mml:mi>k</mml:mi></mml:msub></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> which is also asymptotically optimal, i.e. <inline-formula id="IE57"><mml:math id="IM59"><mml:mrow><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:msub><mml:mi>f</mml:mi><mml:mrow><mml:msub><mml:mi>U</mml:mi><mml:mi>k</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:msub><mml:mstyle displaystyle="true"><mml:munder><mml:mo stretchy="true">→</mml:mo><mml:mrow><mml:mi>k</mml:mi><mml:mo>→</mml:mo><mml:mo>∞</mml:mo></mml:mrow></mml:munder></mml:mstyle><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula>. The remainder of this section describes how to construct such a sequence of universal sets. This construction is similar to the construction of an optimal vertex cover (<xref rid="bty258-B9" ref-type="bibr">Lichiardopol, 2006</xref>) and of an optimal decycling set (<xref rid="bty258-B12" ref-type="bibr">Mykkeltveit, 1972</xref>).</p></statement><sec><title><italic>3.1.1</italic> Naive extension</title><p>Given a universal set <italic>U</italic> that hits every <italic>w</italic>-long path in <inline-formula id="IE58"><mml:math id="IM60"><mml:mrow><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula>, we can easily construct a universal set that hits every <italic>w</italic>-long path in <inline-formula id="IE59"><mml:math id="IM61"><mml:mrow><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula>. The set <inline-formula id="IE60"><mml:math id="IM62"><mml:mrow><mml:mi>U</mml:mi><mml:mo>·</mml:mo><mml:mo>Σ</mml:mo></mml:mrow></mml:math></inline-formula> obtained by concatenating every letter of the alphabet Σ to every element of <italic>U</italic> is called the <italic>naive extension</italic>. The naive extension of a universal set <italic>U</italic> in <inline-formula id="IE61"><mml:math id="IM63"><mml:mrow><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> is a universal set in <inline-formula id="IE62"><mml:math id="IM64"><mml:mrow><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> for <italic>w</italic>-long paths, but the naive extension may not be of optimal size, even if <italic>U</italic> is of optimal size.</p><p>The naive extension shows that the minimum size of a universal set, in proportion, is a non-increasing function as the length of the <italic>k</italic>-mers increases.</p><statement id="mthst7"><p><italic>Proposition 2</italic>. <italic>The function</italic><inline-formula id="IE63"><mml:math id="IM65"><mml:mrow><mml:mi>k</mml:mi><mml:mo>→</mml:mo><mml:msub><mml:mo>β</mml:mo><mml:mi>w</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>/</mml:mo><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:math></inline-formula><italic>is non-increasing.</italic></p><p><italic>P<sc>roof</sc></italic>. Let <inline-formula id="IE64"><mml:math id="IM66"><mml:mrow><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> be a universal set of minimum size, i.e. <inline-formula id="IE65"><mml:math id="IM67"><mml:mrow><mml:mo>|</mml:mo><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo>|</mml:mo><mml:mo>=</mml:mo><mml:msub><mml:mo>β</mml:mo><mml:mi>w</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>. Consider now the naive extension <inline-formula id="IE66"><mml:math id="IM68"><mml:mrow><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo>·</mml:mo><mml:mo>Σ</mml:mo></mml:mrow></mml:math></inline-formula>. The size of the naive extension is <inline-formula id="IE67"><mml:math id="IM69"><mml:mrow><mml:mo>|</mml:mo><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo>·</mml:mo><mml:mo>Σ</mml:mo><mml:mo>|</mml:mo><mml:mo>=</mml:mo><mml:mo>σ</mml:mo><mml:mo>|</mml:mo><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo>|</mml:mo></mml:mrow></mml:math></inline-formula>. Then,
<disp-formula id="E11"><label>(3)</label><mml:math id="M11"><mml:mrow><mml:mfrac><mml:mrow><mml:msub><mml:mo>β</mml:mo><mml:mi>w</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup></mml:mrow></mml:mfrac><mml:mo>≤</mml:mo><mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo>·</mml:mo><mml:mo>Σ</mml:mo><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup></mml:mrow></mml:mfrac><mml:mo>=</mml:mo><mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac><mml:mo>=</mml:mo><mml:mfrac><mml:mrow><mml:msub><mml:mo>β</mml:mo><mml:mi>w</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p> □</p><p>In the following construction, we only consider a subsequence of universal sets, where <italic>k</italic> is a multiple of <italic>w</italic>. Nevertheless, using the naive extension, the subsequence can be extended to a non-increasing complete sequence of universal sets that is asymptotically optimal.</p></statement></sec><sec><title><italic>3.1.2</italic> Embedding of the de Bruijn graph</title><p>The universal set is created by embedding the de Bruijn graph in a <italic>w</italic>-dimensional space and picking a region of the space that intersects every path of length <italic>w</italic>. Using a mapping (called <italic>ψ<sub>w</sub></italic>), we embed the de Bruijn graph <italic>D<sub>k</sub></italic> in a <italic>w</italic>-dimensional hypercube <inline-formula id="IE68"><mml:math id="IM70"><mml:mrow><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mi>w</mml:mi></mml:msub></mml:mrow></mml:math></inline-formula>, where edges in <italic>D<sub>k</sub></italic> correspond approximately to a rotation around a diagonal of the hypercube (a rotation plus a small translation). The hypercube is then split into <italic>w</italic> volumes, or wedges called <inline-formula id="IE69"><mml:math id="IM71"><mml:mrow><mml:msub><mml:mi>W</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:mi>i</mml:mi><mml:mo>∈</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>, of equal size, and one of them is selected, say <italic>W</italic><sub>0</sub>. Because the edges do not correspond perfectly to a rotation, the <italic>k</italic>-mers mapping to the wedge <italic>W</italic><sub>0</sub> do not constitute a universal set. Therefore, we enlarge the wedge <italic>W</italic><sub>0</sub> to get a universal set: <inline-formula id="IE70"><mml:math id="IM72"><mml:mrow><mml:mover accent="true"><mml:mrow><mml:msub><mml:mi>W</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:mrow><mml:mo stretchy="true">¯</mml:mo></mml:mover></mml:mrow></mml:math></inline-formula> is the wedge <italic>W</italic><sub>0</sub> augmented with thin ‘slabs’ at the frontier between <italic>W</italic><sub>0</sub> and the other wedges. The set <inline-formula id="IE71"><mml:math id="IM73"><mml:mrow><mml:mover accent="true"><mml:mrow><mml:msub><mml:mi>W</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:mrow><mml:mo stretchy="true">¯</mml:mo></mml:mover></mml:mrow></mml:math></inline-formula> is such that any path of <italic>w</italic> vertices in <italic>D<sub>k</sub></italic> contains at least one vertex that maps to <inline-formula id="IE72"><mml:math id="IM74"><mml:mrow><mml:mover accent="true"><mml:mrow><mml:msub><mml:mi>W</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:mrow><mml:mo stretchy="true">¯</mml:mo></mml:mover></mml:mrow></mml:math></inline-formula>. Finally, the universal set is any <italic>k</italic>-mer that maps into the wedge <inline-formula id="IE73"><mml:math id="IM75"><mml:mrow><mml:mover accent="true"><mml:mrow><mml:msub><mml:mi>W</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:mrow><mml:mo stretchy="true">¯</mml:mo></mml:mover></mml:mrow></mml:math></inline-formula>, that is the set <inline-formula id="IE74"><mml:math id="IM76"><mml:mrow><mml:msubsup><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mover accent="true"><mml:mrow><mml:msub><mml:mi>W</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:mrow><mml:mo stretchy="true">¯</mml:mo></mml:mover></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>.</p><p>By construction, the same number of <italic>k</italic>-mers maps to any of the <italic>w</italic> wedges. The technical part of the proof below is to show that the number of <italic>k</italic>-mers mapping into the extra slabs is negligible as <inline-formula id="IE75"><mml:math id="IM77"><mml:mrow><mml:mi>k</mml:mi><mml:mo>→</mml:mo><mml:mo>∞</mml:mo></mml:mrow></mml:math></inline-formula>.</p><p>In the following, we assume that <italic>w</italic> divides <italic>k</italic> and set <inline-formula id="IE76"><mml:math id="IM78"><mml:mrow><mml:mi>n</mml:mi><mml:mo>=</mml:mo><mml:mi>k</mml:mi><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula>. Also, the alphabet is mapped to the integers <inline-formula id="IE77"><mml:math id="IM79"><mml:mrow><mml:mo>{</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:mo>σ</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo>}</mml:mo></mml:mrow></mml:math></inline-formula>. For a <italic>k</italic>-mer <italic>m</italic>, define the functions
<disp-formula id="E13"><label>(4)</label><mml:math id="M12"><mml:mrow><mml:msub><mml:mo>ψ</mml:mo><mml:mrow><mml:mi>i</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:munderover><mml:mo>∑</mml:mo><mml:mrow><mml:mi>j</mml:mi><mml:mo>=</mml:mo><mml:mn>0</mml:mn></mml:mrow><mml:mrow><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:munderover><mml:mi>m</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mi>j</mml:mi><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>i</mml:mi><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></disp-formula><disp-formula id="E14"><label>(5)</label><mml:math id="M13"><mml:mrow><mml:msub><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mo>ψ</mml:mo><mml:mrow><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mo>ψ</mml:mo><mml:mrow><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mo>ψ</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">)</mml:mo><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula><inline-formula id="IE78"><mml:math id="IM80"><mml:mrow><mml:msub><mml:mo>ψ</mml:mo><mml:mrow><mml:mi>i</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> sums every <italic>w</italic>th bases of <italic>m</italic>, starting at base <italic>i</italic>. <inline-formula id="IE79"><mml:math id="IM81"><mml:mrow><mml:msub><mml:mo>ψ</mml:mo><mml:mrow><mml:mi>i</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> is an integer in the range <inline-formula id="IE80"><mml:math id="IM82"><mml:mrow><mml:mo stretchy="true">[</mml:mo><mml:mn>0</mml:mn><mml:mo>:</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mo>σ</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>. Then <inline-formula id="IE81"><mml:math id="IM83"><mml:mrow><mml:msub><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> is a <italic>w</italic>-dimensional vector that maps a <italic>k</italic>-mer to a point with integer coordinates inside a <italic>w</italic>-dimensional hypercube of side length <inline-formula id="IE82"><mml:math id="IM84"><mml:mrow><mml:mi>n</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mo>σ</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula> (<xref ref-type="fig" rid="bty258-F1">Fig. 1</xref>).
</p><fig id="bty258-F1" orientation="portrait" position="float"><label>Fig. 1.</label><caption><p>The cube <inline-formula id="IE83"><mml:math id="IM85"><mml:mrow><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mi>w</mml:mi></mml:msub></mml:mrow></mml:math></inline-formula> for <italic>w</italic> = 3. The vertices <italic>V<sub>i</sub></italic> have their <italic>i</italic>th coordinate equal to <inline-formula id="IE84"><mml:math id="IM86"><mml:mrow><mml:mi>n</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mo>σ</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></inline-formula>, where <inline-formula id="IE85"><mml:math id="IM87"><mml:mrow><mml:mi>n</mml:mi><mml:mo>=</mml:mo><mml:mi>k</mml:mi><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula> and all other coordinates equal to 0. The wedge <italic>W<sub>i</sub></italic> is the part of the cube of the points whose <italic>i</italic>th coordinate is greater than the others, which includes vertex <italic>V<sub>i</sub></italic>. The hyperplanes separating wedge <italic>W<sub>i</sub></italic> and <italic>W<sub>j</sub></italic> is orthogonal to the vector <inline-formula id="IE86"><mml:math id="IM88"><mml:mrow><mml:mstyle displaystyle="true"><mml:mrow><mml:mover><mml:mrow><mml:msub><mml:mi>V</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:msub><mml:mi>V</mml:mi><mml:mi>j</mml:mi></mml:msub></mml:mrow><mml:mo stretchy="true">→</mml:mo></mml:mover></mml:mrow></mml:mstyle></mml:mrow></mml:math></inline-formula>. An edge in the de Bruijn graph corresponds to a rotation of <inline-formula id="IE87"><mml:math id="IM89"><mml:mrow><mml:mn>2</mml:mn><mml:mo>π</mml:mo><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula> around the line <inline-formula id="IE88"><mml:math id="IM90"><mml:mrow><mml:mi>O</mml:mi><mml:msub><mml:mi>O</mml:mi><mml:mrow><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mi>w</mml:mi></mml:msub></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula>, followed by a translation along the <inline-formula id="IE89"><mml:math id="IM91"><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></inline-formula>th coordinate of at most <italic>σ</italic></p></caption><graphic xlink:href="bty258f1"></graphic></fig><p>The mapping <italic>ψ<sub>w</sub></italic> has an important property: an edge in the de Bruijn graph corresponds to a rotation in the space, plus a translation along the last coordinate of length at most <inline-formula id="IE90"><mml:math id="IM92"><mml:mrow><mml:mo>σ</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula>. More precisely, given an edge <inline-formula id="IE91"><mml:math id="IM93"><mml:mrow><mml:mi>m</mml:mi><mml:mo>→</mml:mo><mml:mi>m</mml:mi><mml:mo>′</mml:mo></mml:mrow></mml:math></inline-formula> in <italic>D<sub>k</sub></italic>, the suffix of <italic>m</italic> is equal to the prefix of <inline-formula id="IE92"><mml:math id="IM94"><mml:mrow><mml:mi>m</mml:mi><mml:mo>′</mml:mo></mml:mrow></mml:math></inline-formula>: <inline-formula id="IE93"><mml:math id="IM95"><mml:mrow><mml:mi>m</mml:mi><mml:mo>′</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo stretchy="true">]</mml:mo><mml:mo>=</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo><mml:mo>,</mml:mo><mml:mi>i</mml:mi><mml:mo>∈</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>. Hence, there is a shift in most of the coordinates in the mapping: <inline-formula id="IE94"><mml:math id="IM96"><mml:mrow><mml:msub><mml:mo>ψ</mml:mo><mml:mrow><mml:mi>i</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo>′</mml:mo><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:msub><mml:mo>ψ</mml:mo><mml:mrow><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>,</mml:mo><mml:mi>i</mml:mi><mml:mo>∈</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>. Only the last coordinate of <inline-formula id="IE95"><mml:math id="IM97"><mml:mrow><mml:msub><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo>′</mml:mo><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> is not directly equal to a coordinate of <inline-formula id="IE96"><mml:math id="IM98"><mml:mrow><mml:msub><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>, but rather <inline-formula id="IE97"><mml:math id="IM99"><mml:mrow><mml:msub><mml:mo>ψ</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo>′</mml:mo><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:msub><mml:mo>ψ</mml:mo><mml:mrow><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>−</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mn>0</mml:mn><mml:mo stretchy="true">]</mml:mo><mml:mo>+</mml:mo><mml:mi>m</mml:mi><mml:mo>′</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>. In other words, <inline-formula id="IE98"><mml:math id="IM100"><mml:mrow><mml:msub><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo>′</mml:mo><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> is obtained from <inline-formula id="IE99"><mml:math id="IM101"><mml:mrow><mml:msub><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> by rotating all the coordinates and adding a vector <italic>δ</italic> which has only one non-zero coordinate <inline-formula id="IE100"><mml:math id="IM102"><mml:mrow><mml:mo>δ</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo><mml:mo>∈</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mo>−</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mo>σ</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo><mml:mo>:</mml:mo><mml:mo>σ</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>:
<disp-formula id="E15"><mml:math id="M14"><mml:mrow><mml:msub><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo>′</mml:mo><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mo>ψ</mml:mo><mml:mrow><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mo>ψ</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mo>ψ</mml:mo><mml:mrow><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>+</mml:mo><mml:mo>δ</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo><mml:mo stretchy="true">)</mml:mo><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>We define the wedge <italic>W<sub>i</sub></italic> as the points in the hypercube whose <italic>i</italic>th coordinate is greater than all the other coordinates. Let <italic>V<sub>i</sub></italic> be a vertex of the hypercube whose only non-zero coordinate is the <italic>i</italic>th coordinate. If <inline-formula id="IE101"><mml:math id="IM103"><mml:mrow><mml:mi>x</mml:mi><mml:mo>∈</mml:mo><mml:msub><mml:mi>W</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:mrow></mml:math></inline-formula>, then its 0th coordinate is greater than its <italic>i</italic>th coordinate: <inline-formula id="IE102"><mml:math id="IM104"><mml:mrow><mml:mi>x</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo stretchy="true">]</mml:mo><mml:mo>−</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mn>0</mml:mn><mml:mo stretchy="true">]</mml:mo><mml:mo>=</mml:mo><mml:mover><mml:mrow><mml:msub><mml:mi>V</mml:mi><mml:mi>0</mml:mi></mml:msub><mml:msub><mml:mi>V</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:mrow><mml:mo stretchy="true">→</mml:mo></mml:mover><mml:mo>·</mml:mo><mml:mrow><mml:mover accent="true"><mml:mi>x</mml:mi><mml:mo>⃗</mml:mo></mml:mover></mml:mrow><mml:mo>/</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mo>σ</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">)</mml:mo><mml:mo><</mml:mo><mml:mn>0</mml:mn></mml:mrow></mml:math></inline-formula>. The wedge <italic>W</italic><sub>0</sub> is then equivalently defined as the volume bounded by the <italic>w</italic> – 1 hyperplanes orthogonal to the vectors <inline-formula id="IE103"><mml:math id="IM105"><mml:mrow><mml:mrow><mml:mover><mml:mrow><mml:msub><mml:mi>V</mml:mi><mml:mi>0</mml:mi></mml:msub><mml:msub><mml:mi>V</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:mrow><mml:mo stretchy="true">→</mml:mo></mml:mover></mml:mrow><mml:mo>,</mml:mo><mml:mi>i</mml:mi><mml:mo>∈</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>:
<disp-formula id="E16"><mml:math id="M15"><mml:mrow><mml:msub><mml:mi>W</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mrow><mml:mo stretchy="true">{</mml:mo><mml:mrow><mml:mi>x</mml:mi><mml:mo>∈</mml:mo><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mi>w</mml:mi></mml:msub><mml:mo>|</mml:mo><mml:mfrac><mml:mrow><mml:mstyle displaystyle="true"><mml:mrow><mml:munder><mml:mo stretchy="true">→</mml:mo><mml:mrow><mml:msub><mml:mi>V</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:msub><mml:mi>V</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:mrow></mml:munder></mml:mrow></mml:mstyle></mml:mrow><mml:mrow><mml:mi>n</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mo>σ</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mfrac><mml:mo>·</mml:mo><mml:mrow><mml:mover accent="true"><mml:mi>x</mml:mi><mml:mo>⃗</mml:mo></mml:mover></mml:mrow><mml:mo><</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mo>∀</mml:mo><mml:mi>i</mml:mi><mml:mo>∈</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow><mml:mo stretchy="false">}</mml:mo></mml:mrow><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula>Notice that the hyperplanes separating the wedges are not contained in any of the wedges, and therefore the wedges are disjoint and have the same size.</p><p>The rotation of the coordinates correspond geometrically to a rotation around the vector <inline-formula id="IE104"><mml:math id="IM106"><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>, and this vector is contained in the intersection of all the hyperplanes.</p><p>Ignoring at first the points on the hyperplanes, take a point <italic>x</italic> of <inline-formula id="IE105"><mml:math id="IM107"><mml:mrow><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mi>w</mml:mi></mml:msub></mml:mrow></mml:math></inline-formula>: it is in one of the wedges, say <italic>W<sub>i</sub></italic>. The rotation of the coordinates of <italic>x</italic> gives a point in <inline-formula id="IE106"><mml:math id="IM108"><mml:mrow><mml:msub><mml:mi>W</mml:mi><mml:mrow><mml:mi>i</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> (or <inline-formula id="IE107"><mml:math id="IM109"><mml:mrow><mml:msub><mml:mi>W</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> if <italic>i</italic> = 0). Hence, either <italic>x</italic> is in <italic>W</italic><sub>0</sub> or one of its <italic>w</italic> – 1 consecutive rotations is in <italic>W</italic><sub>0</sub>. If it were not for the additional translation by <italic>δ</italic>, the <italic>k</italic>-mers mapping to <italic>W</italic><sub>0</sub> would constitute a universal set.</p><p>Starting from a <italic>k</italic>-mer <italic>m</italic> that maps to point <italic>x</italic>, any <italic>k</italic>-mer reachable from <italic>m</italic> by a path of at most <italic>w</italic> – 1 edges maps to a point where each coordinate differs from a rotation of <italic>x</italic> by at most <italic>σ</italic>. To compensate for <italic>δ</italic> and the points on the hyperplanes, we extend the wedge <italic>W</italic><sub>0</sub> by pushing the hyperplanes back by <italic>σ</italic> (i.e. we add some slabs parallel to the hyperplanes of thickness <italic>σ</italic>):
<disp-formula id="E17"><mml:math id="M16"><mml:mrow><mml:mover accent="true"><mml:mrow><mml:msub><mml:mi>W</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:mrow><mml:mo stretchy="true">¯</mml:mo></mml:mover><mml:mo>=</mml:mo><mml:mrow><mml:mo stretchy="true">{</mml:mo><mml:mrow><mml:mi>x</mml:mi><mml:mo>∈</mml:mo><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mi>w</mml:mi></mml:msub><mml:mo>|</mml:mo><mml:mfrac><mml:mrow><mml:mstyle displaystyle="true"><mml:mrow><mml:munder><mml:mo stretchy="true">→</mml:mo><mml:mrow><mml:msub><mml:mi>V</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:msub><mml:mi>V</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:mrow></mml:munder></mml:mrow></mml:mstyle></mml:mrow><mml:mrow><mml:mi>n</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mo>σ</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mfrac><mml:mo>·</mml:mo><mml:mrow><mml:mover accent="true"><mml:mi>x</mml:mi><mml:mo>⃗</mml:mo></mml:mover></mml:mrow><mml:mo>≤</mml:mo><mml:mo>σ</mml:mo><mml:mo>,</mml:mo><mml:mo>∀</mml:mo><mml:mi>i</mml:mi><mml:mo>∈</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow><mml:mo stretchy="false">}</mml:mo></mml:mrow><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula>By construction, the set <inline-formula id="IE108"><mml:math id="IM110"><mml:mrow><mml:msubsup><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mover accent="true"><mml:mrow><mml:msub><mml:mi>W</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:mrow><mml:mo stretchy="true">¯</mml:mo></mml:mover></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> is a universal set.</p><p>The slabs have a thickness of <italic>σ</italic>, which is a constant independent of <italic>k</italic>, hence only <italic>w</italic> – 1 dimensions of the slabs grow with <italic>k</italic> and the volume of the slabs is in proportion a negligible volume of the hypercube as <inline-formula id="IE109"><mml:math id="IM111"><mml:mrow><mml:mi>k</mml:mi><mml:mo>→</mml:mo><mml:mo>∞</mml:mo></mml:mrow></mml:math></inline-formula>. The slabs are represented by the set <inline-formula id="IE110"><mml:math id="IM112"><mml:mrow><mml:mi>s</mml:mi><mml:mo>=</mml:mo><mml:mrow><mml:mover accent="true"><mml:mrow><mml:msub><mml:mi>W</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:mrow><mml:mo stretchy="true">¯</mml:mo></mml:mover></mml:mrow><mml:mi mathvariant="normal">∖</mml:mi><mml:msub><mml:mi>W</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:mrow></mml:math></inline-formula>. It remains to show that the number of <italic>k</italic>-mers that map into the slabs, i.e. <inline-formula id="IE111"><mml:math id="IM113"><mml:mrow><mml:msubsup><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:mi>s</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>, is also asymptotically negligible compared to the total number of <italic>k</italic>-mers <italic>σ<sup>k</sup></italic>.</p></sec><sec><title><italic>3.1.3</italic> Asymptotic size of the universal set: binary alphabet</title><p>By the symmetry of the definition of the mapping function and of the wedges, the same number of <italic>k</italic>-mers map to each wedge, therefore <inline-formula id="IE112"><mml:math id="IM114"><mml:mrow><mml:mo>|</mml:mo><mml:msubsup><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi>W</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>|</mml:mo></mml:mrow></mml:math></inline-formula> is independent of <italic>i</italic> and because the wedges are disjoint, <inline-formula id="IE113"><mml:math id="IM115"><mml:mrow><mml:mo>|</mml:mo><mml:msubsup><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi>W</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>|</mml:mo><mml:mo>≤</mml:mo><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula>. All the hyperplanes are contained in <inline-formula id="IE114"><mml:math id="IM116"><mml:mrow><mml:mover accent="true"><mml:mrow><mml:msub><mml:mi>W</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:mrow><mml:mo stretchy="true">¯</mml:mo></mml:mover></mml:mrow></mml:math></inline-formula>, and therefore <inline-formula id="IE115"><mml:math id="IM117"><mml:mrow><mml:mo>|</mml:mo><mml:msubsup><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mover accent="true"><mml:mrow><mml:msub><mml:mi>W</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:mrow><mml:mo stretchy="true">¯</mml:mo></mml:mover></mml:mrow><mml:mo stretchy="true">)</mml:mo><mml:mo>|</mml:mo><mml:mo>≥</mml:mo><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula>. Hence,
<disp-formula id="E18"><label>(6)</label><mml:math id="M17"><mml:mrow><mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:msubsup><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi>W</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac><mml:mo>≤</mml:mo><mml:mfrac><mml:mn>1</mml:mn><mml:mi>w</mml:mi></mml:mfrac><mml:mo>≤</mml:mo><mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:msubsup><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mover accent="true"><mml:mrow><mml:msub><mml:mi>W</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:mrow><mml:mo stretchy="true">¯</mml:mo></mml:mover></mml:mrow><mml:mo stretchy="true">)</mml:mo><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac><mml:mo>=</mml:mo><mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:msubsup><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi>W</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac><mml:mo>+</mml:mo><mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:msubsup><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:mi>s</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula>and it suffices to show that the proportion of <italic>k</italic>-mers mapping into <italic>s</italic>, i.e. <inline-formula id="IE116"><mml:math id="IM118"><mml:mrow><mml:mo>|</mml:mo><mml:msubsup><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:mi>s</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>|</mml:mo><mml:mo>/</mml:mo><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:math></inline-formula>, is asymptotically 0.</p><p>Let’s first assume that the alphabet is binary, <italic>σ</italic> = 2.</p><statement id="mthst8"><p><italic>Proposition 3</italic>. The slabs are asymptotically negligible:
<disp-formula id="E19"><mml:math id="M18"><mml:mrow><mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:msubsup><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:mi>s</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mn>2</mml:mn><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac><mml:mstyle displaystyle="true"><mml:munder><mml:mo stretchy="true">→</mml:mo><mml:mrow><mml:mi>k</mml:mi><mml:mo>→</mml:mo><mml:mo>∞</mml:mo></mml:mrow></mml:munder></mml:mstyle><mml:mn>0.</mml:mn></mml:mrow></mml:math></disp-formula></p><p>P<sc>roof</sc>. The number of ways to sum up <italic>n</italic> binary numbers to a value <italic>v</italic> is <inline-formula id="IE117"><mml:math id="IM119"><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mi>n</mml:mi></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>v</mml:mi></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:math></inline-formula>. Hence, the number of <italic>k</italic>-mers mapping to <inline-formula id="IE118"><mml:math id="IM120"><mml:mrow><mml:mi>x</mml:mi><mml:mo>∈</mml:mo><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mi>w</mml:mi></mml:msub></mml:mrow></mml:math></inline-formula> is <inline-formula id="IE119"><mml:math id="IM121"><mml:mrow><mml:munderover><mml:mo>∏</mml:mo><mml:mrow><mml:mi>i</mml:mi><mml:mo>=</mml:mo><mml:mn>0</mml:mn></mml:mrow><mml:mrow><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:munderover><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mi>n</mml:mi></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>x</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo stretchy="true">]</mml:mo></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:mrow></mml:math></inline-formula>. The point at the center of the cube <inline-formula id="IE120"><mml:math id="IM122"><mml:mrow><mml:msub><mml:mi>O</mml:mi><mml:mrow><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mi>w</mml:mi></mml:msub></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>, which is also in all the slabs, has the largest number of <italic>k</italic>-mers mapping to it: <inline-formula id="IE121"><mml:math id="IM123"><mml:mrow><mml:msup><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mi>n</mml:mi></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mi>w</mml:mi></mml:msup></mml:mrow></mml:math></inline-formula>. The volume of a slab, which is bounded by an hyperplane and of thickness <italic>σ</italic> = 2, is <inline-formula id="IE122"><mml:math id="IM124"><mml:mrow><mml:mi>O</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>.</p></statement><p>The images of the mapping <italic>ψ<sub>w</sub></italic> are the points with integer coordinates, and these points are evenly distributed through out <inline-formula id="IE123"><mml:math id="IM125"><mml:mrow><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mi>w</mml:mi></mml:msub></mml:mrow></mml:math></inline-formula>. Hence, the number of points in a slab is proportional to its volume. We can therefore get an over-estimation of the number of <italic>k</italic>-mers mapping into the slabs by estimating the number of <italic>k</italic>-mers mapping to any point in the slab as the <inline-formula id="IE124"><mml:math id="IM126"><mml:mrow><mml:msup><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mi>n</mml:mi></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mi>w</mml:mi></mml:msup></mml:mrow></mml:math></inline-formula> (the maximum possible), and then multiply by the volume. Unfortunately, the approximation of the proportion of <italic>k</italic>-mers in the <italic>w</italic> – 1 slabs of <inline-formula id="IE125"><mml:math id="IM127"><mml:mrow><mml:mi>O</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo><mml:msup><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mi>n</mml:mi></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mi>w</mml:mi></mml:msup><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:msup><mml:mn>2</mml:mn><mml:mrow><mml:mo>−</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msup><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> is too crude and does not converge to 0 when <italic>k</italic> (hence <italic>n</italic>) goes to infinity.</p><p>Instead, we split the slabs into two parts: (i) the points within a small hypercube <inline-formula id="IE126"><mml:math id="IM128"><mml:mrow><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mo>α</mml:mo></mml:msub></mml:mrow></mml:math></inline-formula> centered at <inline-formula id="IE127"><mml:math id="IM129"><mml:mrow><mml:msub><mml:mi>O</mml:mi><mml:mrow><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mi>w</mml:mi></mml:msub></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> and of side length <inline-formula id="IE128"><mml:math id="IM130"><mml:mrow><mml:mn>2</mml:mn><mml:msup><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mo>α</mml:mo></mml:msup></mml:mrow></mml:math></inline-formula>; (ii) the points outside of that hypercube. As we shall see, choosing <inline-formula id="IE129"><mml:math id="IM131"><mml:mrow><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mn>2</mml:mn><mml:mo><</mml:mo><mml:mo>α</mml:mo><mml:mo><</mml:mo><mml:mi>w</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="true">(</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> gives the desired convergence. We use <inline-formula id="IE130"><mml:math id="IM132"><mml:mrow><mml:msup><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mi>n</mml:mi></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mi>w</mml:mi></mml:msup></mml:mrow></mml:math></inline-formula> as an upper-bound on the number of <italic>k</italic>-mers mapping to the points in <inline-formula id="IE131"><mml:math id="IM133"><mml:mrow><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mo>α</mml:mo></mml:msub></mml:mrow></mml:math></inline-formula>. For the points mapping outside of <inline-formula id="IE132"><mml:math id="IM134"><mml:mrow><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mo>α</mml:mo></mml:msub></mml:mrow></mml:math></inline-formula>, i.e. in the complement <inline-formula id="IE133"><mml:math id="IM135"><mml:mrow><mml:msubsup><mml:mi mathvariant="script">C</mml:mi><mml:mo>α</mml:mo><mml:mi mathvariant="normal">∁</mml:mi></mml:msubsup></mml:mrow></mml:math></inline-formula>, at least one coordinate is at distance <inline-formula id="IE134"><mml:math id="IM136"><mml:mrow><mml:mo>≥</mml:mo><mml:msup><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mo>α</mml:mo></mml:msup></mml:mrow></mml:math></inline-formula> from <inline-formula id="IE135"><mml:math id="IM137"><mml:mrow><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math></inline-formula>. The maximum number of <italic>k</italic>-mers mapping to a point <italic>x</italic> of <inline-formula id="IE136"><mml:math id="IM138"><mml:mrow><mml:msubsup><mml:mi mathvariant="script">C</mml:mi><mml:mo>α</mml:mo><mml:mi mathvariant="normal">∁</mml:mi></mml:msubsup></mml:mrow></mml:math></inline-formula> is when all the coordinates are equal to <inline-formula id="IE137"><mml:math id="IM139"><mml:mrow><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math></inline-formula>, except for one equal to <inline-formula id="IE138"><mml:math id="IM140"><mml:mrow><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:msup><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mo>α</mml:mo></mml:msup></mml:mrow></mml:math></inline-formula> or <inline-formula id="IE139"><mml:math id="IM141"><mml:mrow><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:msup><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mo>α</mml:mo></mml:msup></mml:mrow></mml:math></inline-formula>. Because of the symmetry of the binomial coefficient around <inline-formula id="IE140"><mml:math id="IM142"><mml:mrow><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn><mml:mo>,</mml:mo><mml:mo> </mml:mo><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mi>n</mml:mi></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn><mml:mo>−</mml:mo><mml:msup><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mo>α</mml:mo></mml:msup></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:msup><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mi>n</mml:mi></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mrow><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup></mml:mrow></mml:math></inline-formula> is an upper-bound on the number of <italic>k</italic>-mers mapping to a point outside of <inline-formula id="IE141"><mml:math id="IM143"><mml:mrow><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mo>α</mml:mo></mml:msub></mml:mrow></mml:math></inline-formula>.</p><p>In the following <italic>O</italic> expressions, <italic>w</italic> and <italic>σ</italic> = 2 are constants and will be included in the constant in the <italic>O</italic>, while <italic>k</italic> and <inline-formula id="IE142"><mml:math id="IM144"><mml:mrow><mml:mi>n</mml:mi><mml:mo>=</mml:mo><mml:mi>k</mml:mi><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula> go to infinity.</p><p>For (i), from the Stirling approximation <inline-formula id="IE143"><mml:math id="IM145"><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mi>x</mml:mi></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>x</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mo>∼</mml:mo><mml:msup><mml:mn>2</mml:mn><mml:mrow><mml:mi>x</mml:mi><mml:mo>+</mml:mo><mml:mn>0.5</mml:mn></mml:mrow></mml:msup><mml:mo>/</mml:mo><mml:msqrt><mml:mrow><mml:mo>π</mml:mo><mml:mi>x</mml:mi></mml:mrow></mml:msqrt></mml:mrow></mml:math></inline-formula>, and the volume of the intersection of <inline-formula id="IE144"><mml:math id="IM146"><mml:mrow><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mo>α</mml:mo></mml:msub></mml:mrow></mml:math></inline-formula> with the slabs of <inline-formula id="IE145"><mml:math id="IM147"><mml:mrow><mml:mi>O</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi>w</mml:mi><mml:msup><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mrow><mml:mo>α</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:msup><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>, we have:
<disp-formula id="E20"><label>(7)</label><mml:math id="M19"><mml:mrow><mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:msubsup><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mo>α</mml:mo></mml:msub><mml:mo>∩</mml:mo><mml:mi>S</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mn>2</mml:mn><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac><mml:mo>=</mml:mo><mml:mi>O</mml:mi><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:msup><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mfrac><mml:mrow><mml:msup><mml:mn>2</mml:mn><mml:mrow><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mn>0.5</mml:mn></mml:mrow></mml:msup></mml:mrow><mml:mrow><mml:msqrt><mml:mi>n</mml:mi></mml:msqrt></mml:mrow></mml:mfrac></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mi>w</mml:mi></mml:msup><mml:mi>w</mml:mi><mml:msup><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mfrac><mml:mi>n</mml:mi><mml:mn>2</mml:mn></mml:mfrac></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mrow><mml:mo>α</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:msup><mml:mfrac><mml:mn>1</mml:mn><mml:mrow><mml:msup><mml:mn>2</mml:mn><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:math></disp-formula><disp-formula id="E21"><label>(8)</label><mml:math id="M20"><mml:mrow><mml:mo>=</mml:mo><mml:mi>O</mml:mi><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mfrac><mml:mrow><mml:msup><mml:mn>2</mml:mn><mml:mrow><mml:mi>n</mml:mi><mml:mi>w</mml:mi></mml:mrow></mml:msup></mml:mrow><mml:mrow><mml:msup><mml:mn>2</mml:mn><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mo>α</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo><mml:mo>−</mml:mo><mml:mi>w</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msup></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:math></disp-formula><disp-formula id="E22"><label>(9)</label><mml:math id="M21"><mml:mrow><mml:mo>=</mml:mo><mml:mi>O</mml:mi><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mo>α</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo><mml:mo>−</mml:mo><mml:mi>w</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msup></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula>In <xref ref-type="disp-formula" rid="E21">Equation (8)</xref>, recall that <italic>nw </italic>=<italic> k</italic>. Therefore, <inline-formula id="IE146"><mml:math id="IM148"><mml:mrow><mml:mo>|</mml:mo><mml:msubsup><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mo>α</mml:mo></mml:msub><mml:mo>∩</mml:mo><mml:mi>S</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>|</mml:mo><mml:mo>/</mml:mo><mml:msup><mml:mn>2</mml:mn><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:math></inline-formula> converges to 0 if the power of <italic>n</italic> in <xref ref-type="disp-formula" rid="E22">Equation (9)</xref> is negative, that is if <inline-formula id="IE147"><mml:math id="IM149"><mml:mrow><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mo>α</mml:mo></mml:msub></mml:mrow></mml:math></inline-formula> is not too large and <inline-formula id="IE148"><mml:math id="IM150"><mml:mrow><mml:mo>α</mml:mo><mml:mo><</mml:mo><mml:mi>w</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="true">(</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>.</p><p>For (ii), also from Stirling approximation, we have the equivalence
<disp-formula id="E23"><mml:math id="M22"><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mi>x</mml:mi></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>y</mml:mi></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mo>∼</mml:mo><mml:mfrac><mml:mrow><mml:msup><mml:mi>x</mml:mi><mml:mrow><mml:mi>x</mml:mi><mml:mo>+</mml:mo><mml:mn>0.5</mml:mn></mml:mrow></mml:msup></mml:mrow><mml:mrow><mml:msqrt><mml:mrow><mml:mn>2</mml:mn><mml:mo>π</mml:mo></mml:mrow></mml:msqrt><mml:msup><mml:mi>y</mml:mi><mml:mrow><mml:mi>y</mml:mi><mml:mo>+</mml:mo><mml:mn>0.5</mml:mn></mml:mrow></mml:msup><mml:msup><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mi>x</mml:mi><mml:mo>−</mml:mo><mml:mi>y</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mrow><mml:mi>x</mml:mi><mml:mo>−</mml:mo><mml:mi>y</mml:mi><mml:mo>+</mml:mo><mml:mn>0.5</mml:mn></mml:mrow></mml:msup></mml:mrow></mml:mfrac><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula>Let <inline-formula id="IE149"><mml:math id="IM151"><mml:mrow><mml:mi>n</mml:mi><mml:mo>′</mml:mo><mml:mo>=</mml:mo><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math></inline-formula>, then <italic>x </italic>=<italic> n</italic> and <inline-formula id="IE150"><mml:math id="IM152"><mml:mrow><mml:mi>y</mml:mi><mml:mo>=</mml:mo><mml:mi>n</mml:mi><mml:mo>′</mml:mo><mml:mo>−</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mo>′</mml:mo><mml:mo>α</mml:mo></mml:mrow></mml:msup></mml:mrow></mml:math></inline-formula>. Then, the denominator of the binomial coefficient is (except for the <inline-formula id="IE151"><mml:math id="IM153"><mml:mrow><mml:msqrt><mml:mrow><mml:mn>2</mml:mn><mml:mo>π</mml:mo></mml:mrow></mml:msqrt></mml:mrow></mml:math></inline-formula> factor):
<disp-formula id="E24"><label>(10)</label><mml:math id="M23"><mml:mrow><mml:msup><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:msup><mml:mi>n</mml:mi><mml:mo>′</mml:mo></mml:msup><mml:mo>−</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mo>′</mml:mo><mml:mo>α</mml:mo></mml:mrow></mml:msup></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mrow><mml:msup><mml:mi>n</mml:mi><mml:mo>′</mml:mo></mml:msup><mml:mo>−</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mo>′</mml:mo><mml:mo>α</mml:mo></mml:mrow></mml:msup><mml:mo>+</mml:mo><mml:mn>0.5</mml:mn></mml:mrow></mml:msup><mml:msup><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mo>′</mml:mo></mml:msup><mml:mo>+</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mo>′</mml:mo><mml:mo>α</mml:mo></mml:mrow></mml:msup></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mrow><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mo>′</mml:mo></mml:msup><mml:mo>+</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mo>′</mml:mo><mml:mo>α</mml:mo></mml:mrow></mml:msup><mml:mo>+</mml:mo><mml:mn>0.5</mml:mn></mml:mrow></mml:msup></mml:mrow></mml:math></disp-formula><disp-formula id="E25"><label>(11)</label><mml:math id="M24"><mml:mrow><mml:mo>=</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mo>′</mml:mo><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:msup><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mo>′</mml:mo><mml:mo>α</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mrow><mml:msup><mml:mi>n</mml:mi><mml:mo>′</mml:mo></mml:msup><mml:mo>−</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mo>′</mml:mo><mml:mo>α</mml:mo></mml:mrow></mml:msup><mml:mo>+</mml:mo><mml:mn>0.5</mml:mn></mml:mrow></mml:msup><mml:msup><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mo>′</mml:mo><mml:mo>α</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mrow><mml:msup><mml:mi>n</mml:mi><mml:mo>′</mml:mo></mml:msup><mml:mo>+</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mo>′</mml:mo><mml:mo>α</mml:mo></mml:mrow></mml:msup><mml:mo>+</mml:mo><mml:mn>0.5</mml:mn></mml:mrow></mml:msup></mml:mrow></mml:math></disp-formula><disp-formula id="E26"><label>(12)</label><mml:math id="M25"><mml:mrow><mml:mo>∼</mml:mo><mml:msup><mml:mn>2</mml:mn><mml:mrow><mml:mo>−</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:msup><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo> </mml:mo><mml:mtext>exp</mml:mtext><mml:mo> </mml:mo><mml:mo></mml:mo><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mn>2</mml:mn><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mo>′</mml:mo><mml:mn>2</mml:mn><mml:mo>α</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:math></disp-formula>Hence, the proportion of <italic>k</italic>-mers mapping in the slab outside of <inline-formula id="IE152"><mml:math id="IM154"><mml:mrow><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mo>α</mml:mo></mml:msub></mml:mrow></mml:math></inline-formula> is:
<disp-formula id="E27"><label>(13)</label><mml:math id="M26"><mml:mrow><mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:msubsup><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mo>(</mml:mo><mml:msubsup><mml:mi mathvariant="script">C</mml:mi><mml:mo>α</mml:mo><mml:mi mathvariant="normal">∁</mml:mi></mml:msubsup><mml:mo>∩</mml:mo><mml:mi>S</mml:mi><mml:mo>)</mml:mo><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mn>2</mml:mn><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac><mml:mo>=</mml:mo><mml:mi>O</mml:mi><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:msup><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mfrac><mml:mrow><mml:msup><mml:mn>2</mml:mn><mml:mrow><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mn>0.5</mml:mn></mml:mrow></mml:msup></mml:mrow><mml:mrow><mml:msqrt><mml:mi>n</mml:mi></mml:msqrt></mml:mrow></mml:mfrac></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mrow><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mfrac><mml:mrow><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mn>0.5</mml:mn></mml:mrow></mml:msup><mml:mi>w</mml:mi><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:msup><mml:mn>2</mml:mn><mml:mrow><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup></mml:mrow><mml:mrow><mml:msup><mml:mn>2</mml:mn><mml:mi>k</mml:mi></mml:msup><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo> </mml:mo><mml:mtext>exp</mml:mtext><mml:mo> </mml:mo><mml:mo></mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mn>2</mml:mn><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mo>′</mml:mo><mml:mn>2</mml:mn><mml:mo>α</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mfrac></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:math></disp-formula><disp-formula id="E28"><label>(14)</label><mml:math id="M27"><mml:mrow><mml:mo>=</mml:mo><mml:mi>O</mml:mi><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mfrac><mml:mrow><mml:msup><mml:mn>2</mml:mn><mml:mrow><mml:mi>n</mml:mi><mml:mi>w</mml:mi></mml:mrow></mml:msup></mml:mrow><mml:mrow><mml:msup><mml:mn>2</mml:mn><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac><mml:mfrac><mml:mrow><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup></mml:mrow><mml:mrow><mml:mo> </mml:mo><mml:mtext>exp</mml:mtext><mml:mo> </mml:mo><mml:mo></mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mn>2</mml:mn><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mo>′</mml:mo><mml:mn>2</mml:mn><mml:mo>α</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mfrac></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula>In <xref ref-type="disp-formula" rid="E28">Equation (14)</xref>, both <inline-formula id="IE153"><mml:math id="IM155"><mml:mrow><mml:mi>n</mml:mi><mml:mo>=</mml:mo><mml:mi>k</mml:mi><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE154"><mml:math id="IM156"><mml:mrow><mml:mi>n</mml:mi><mml:mo>′</mml:mo><mml:mo>=</mml:mo><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math></inline-formula> grow linearly with <italic>k</italic>. Therefore, the proportion <inline-formula id="IE155"><mml:math id="IM157"><mml:mrow><mml:mo>|</mml:mo><mml:msubsup><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msubsup><mml:mo>(</mml:mo><mml:msubsup><mml:mi mathvariant="script">C</mml:mi><mml:mo>α</mml:mo><mml:mi mathvariant="normal">∁</mml:mi></mml:msubsup><mml:mo>∩</mml:mo><mml:mi>S</mml:mi><mml:mo>)</mml:mo><mml:mo>|</mml:mo><mml:mo>/</mml:mo><mml:msup><mml:mn>2</mml:mn><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:math></inline-formula> converges to 0 when the power of <inline-formula id="IE156"><mml:math id="IM158"><mml:mrow><mml:mi>n</mml:mi><mml:mo>′</mml:mo></mml:mrow></mml:math></inline-formula> in the exponential is positive, that is when <inline-formula id="IE157"><mml:math id="IM159"><mml:mrow><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mo>α</mml:mo></mml:msub></mml:mrow></mml:math></inline-formula> is large enough and <inline-formula id="IE158"><mml:math id="IM160"><mml:mrow><mml:mo>α</mml:mo><mml:mo>></mml:mo><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math></inline-formula>. □</p><p>The following proposition is then a direct consequence of Proposition 3 and Lemma 1.</p><statement id="mthst9"><p><italic>Proposition 4</italic>. On the binary alphabet, for any fixed <italic>w</italic>, there exists a sequence of universal sets <italic>U<sub>k</sub></italic> asymptotically of optimal size and a sequence of minimizers schemes <italic>f<sub>k</sub></italic> asymptotically of optimal density.</p></statement></sec><sec><title><italic>3.1.4</italic> Asymptotic size of the universal set: even alphabet</title><p>We now extend the previous result to even alphabets. Let’s assume that the alphabet Σ is even: <inline-formula id="IE159"><mml:math id="IM161"><mml:mrow><mml:mo>|</mml:mo><mml:mo>Σ</mml:mo><mml:mo>|</mml:mo><mml:mo>=</mml:mo><mml:mo>σ</mml:mo><mml:mo>=</mml:mo><mml:mn>2</mml:mn><mml:mo>σ</mml:mo><mml:mo>′</mml:mo></mml:mrow></mml:math></inline-formula>. We construct a graph homomorphism (<xref rid="bty258-B5" ref-type="bibr">Lempel, 1970</xref>; <xref rid="bty258-B9" ref-type="bibr">Lichiardopol, 2006</xref>) from the de Bruijn graph <inline-formula id="IE160"><mml:math id="IM162"><mml:mrow><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> of order <italic>k</italic> on the alphabet of size <italic>σ</italic> onto the de Bruijn graph <inline-formula id="IE161"><mml:math id="IM163"><mml:mrow><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> of order <italic>k</italic> on the binary alphabet. Consider the function <inline-formula id="IE162"><mml:math id="IM164"><mml:mrow><mml:mi>g</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mrow><mml:mo stretchy="true">⌊</mml:mo><mml:mrow><mml:mi>x</mml:mi><mml:mo>/</mml:mo><mml:mo>σ</mml:mo><mml:mo>′</mml:mo></mml:mrow><mml:mo stretchy="true">⌋</mml:mo></mml:mrow></mml:mrow></mml:math></inline-formula>. In other words, <italic>g</italic> maps the first half of the alphabet Σ to 0 and the second half to 1. Then, consider <inline-formula id="IE163"><mml:math id="IM165"><mml:mrow><mml:mo>φ</mml:mo><mml:mo>:</mml:mo><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub><mml:mo>→</mml:mo><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> which applies <italic>g</italic> to each base of a <italic>k</italic>-mer. That is, <inline-formula id="IE165"><mml:math id="IM166"><mml:mrow><mml:mi>y</mml:mi><mml:mo>=</mml:mo><mml:mo>φ</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> implies that <inline-formula id="IE166"><mml:math id="IM167"><mml:mrow><mml:mi>y</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo stretchy="true">]</mml:mo><mml:mo>=</mml:mo><mml:mi>g</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo stretchy="true">]</mml:mo><mml:mo stretchy="true">)</mml:mo><mml:mo>,</mml:mo><mml:mi>i</mml:mi><mml:mo>∈</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>.</p><p>It is simple to check that <inline-formula id="IE167"><mml:math id="IM168"><mml:mo>φ</mml:mo></mml:math></inline-formula> is an onto function and a graph homomorphism: if <inline-formula id="IE168"><mml:math id="IM169"><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo>,</mml:mo><mml:mi>m</mml:mi><mml:mo>′</mml:mo><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> is an edge of <inline-formula id="IE169"><mml:math id="IM170"><mml:mrow><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula>, then so is <inline-formula id="IE170"><mml:math id="IM171"><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mo>φ</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>,</mml:mo><mml:mo>φ</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo>′</mml:mo><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> in <inline-formula id="IE171"><mml:math id="IM172"><mml:mrow><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula>. Inductively, if <inline-formula id="IE172"><mml:math id="IM173"><mml:mrow><mml:msub><mml:mi>m</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mi>m</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow></mml:math></inline-formula> is a path of <inline-formula id="IE173"><mml:math id="IM174"><mml:mrow><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula>, then <inline-formula id="IE174"><mml:math id="IM175"><mml:mrow><mml:mo>φ</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi>m</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:mo>φ</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi>m</mml:mi><mml:mi>n</mml:mi></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> is a path of <inline-formula id="IE175"><mml:math id="IM176"><mml:mrow><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula>. Therefore, if <inline-formula id="IE176"><mml:math id="IM177"><mml:mrow><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>,</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> is a universal set in <inline-formula id="IE177"><mml:math id="IM178"><mml:mrow><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> that intersects every path of <italic>w</italic> vertices, then the set <inline-formula id="IE178"><mml:math id="IM179"><mml:mrow><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:msup><mml:mo>φ</mml:mo><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>,</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> is also a universal set of <inline-formula id="IE179"><mml:math id="IM180"><mml:mrow><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula>. Moreover, the same number of letters of Σ map to 0 and to 1: <inline-formula id="IE180"><mml:math id="IM181"><mml:mrow><mml:mo>|</mml:mo><mml:msup><mml:mi>g</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="true">(</mml:mo><mml:mn>0</mml:mn><mml:mo stretchy="true">)</mml:mo><mml:mo>|</mml:mo><mml:mo>=</mml:mo><mml:mo>|</mml:mo><mml:msup><mml:mi>g</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="true">(</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo><mml:mo>|</mml:mo><mml:mo>=</mml:mo><mml:mo>σ</mml:mo><mml:mo>′</mml:mo></mml:mrow></mml:math></inline-formula>. Then the number of <italic>k</italic>-mers of <inline-formula id="IE181"><mml:math id="IM182"><mml:mrow><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> that map to a <italic>k</italic>-mer <italic>m</italic> of <inline-formula id="IE182"><mml:math id="IM183"><mml:mrow><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> is
<disp-formula id="E29"><label>(15)</label><mml:math id="M28"><mml:mrow><mml:mo>|</mml:mo><mml:msup><mml:mo>φ</mml:mo><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>|</mml:mo><mml:mo>=</mml:mo><mml:munderover><mml:mo>∏</mml:mo><mml:mrow><mml:mi>i</mml:mi><mml:mo>=</mml:mo><mml:mn>0</mml:mn></mml:mrow><mml:mrow><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:munderover><mml:mo>|</mml:mo><mml:msup><mml:mi>g</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo stretchy="true">]</mml:mo><mml:mo stretchy="true">)</mml:mo><mml:mo>|</mml:mo><mml:mo>=</mml:mo><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:mo>′</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msup><mml:mo>=</mml:mo><mml:mfrac><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow><mml:mrow><mml:msup><mml:mn>2</mml:mn><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>We can now prove a generalization of Proposition 4.</p><statement id="mthst10"><p><italic>Theorem 1</italic>. On an even alphabet, for any fixed <italic>w</italic>, there exists a sequence of universal sets <italic>U<sub>k</sub></italic> asymptotically of optimal size and a sequence of minimizers schemes <italic>f<sub>k</sub></italic> asymptotically of optimal density.</p><p>P<sc>roof</sc>. Let <inline-formula id="IE183"><mml:math id="IM184"><mml:mrow><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>,</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> be the sequence of universal sets of <inline-formula id="IE184"><mml:math id="IM185"><mml:mrow><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> constructed in the Proof of Proposition 4. Then <inline-formula id="IE185"><mml:math id="IM186"><mml:mrow><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:msup><mml:mo>φ</mml:mo><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>,</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> is a sequence of universal sets of <inline-formula id="IE186"><mml:math id="IM187"><mml:mrow><mml:msub><mml:mi>D</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> where <inline-formula id="IE187"><mml:math id="IM188"><mml:mrow><mml:mo>|</mml:mo><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>|</mml:mo><mml:mo>=</mml:mo><mml:mo>|</mml:mo><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>,</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>|</mml:mo><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup><mml:mo>/</mml:mo><mml:msup><mml:mn>2</mml:mn><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:math></inline-formula>. Therefore, by Proposition 3:
<disp-formula id="E30"><label>(16)</label><mml:math id="M29"><mml:mrow><mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>,</mml:mo><mml:mo>σ</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac><mml:mo>=</mml:mo><mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:msub><mml:mi>U</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>,</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>|</mml:mo><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow><mml:mrow><mml:msup><mml:mn>2</mml:mn><mml:mi>k</mml:mi></mml:msup><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac><mml:mstyle displaystyle="true"><mml:munder><mml:mo stretchy="true">→</mml:mo><mml:mrow><mml:mi>k</mml:mi><mml:mo>→</mml:mo><mml:mo>∞</mml:mo></mml:mrow></mml:munder></mml:mstyle><mml:mfrac><mml:mn>1</mml:mn><mml:mi>w</mml:mi></mml:mfrac><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula>Lemma 1 proves the second part of the statement. □</p></statement></sec></sec><sec><title>3.2 Minimizers asymptotic behavior in <italic>w</italic></title><p>We now consider the converse problem where the length of the <italic>k</italic>-mer is fixed and <italic>w</italic> grows to infinity.</p><statement id="mthst11"><p><italic>Proposition 5</italic>. For any minimizers scheme <italic>f</italic> and any fixed <italic>k</italic>, the density function <inline-formula id="IE188"><mml:math id="IM189"><mml:mrow><mml:mi>w</mml:mi><mml:mo>→</mml:mo><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> is non-increasing.</p><p>P<sc>roof</sc>. Let <inline-formula id="IE189"><mml:math id="IM190"><mml:mrow><mml:msub><mml:mi>S</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> be any de Bruijn sequence of order <inline-formula id="IE190"><mml:math id="IM191"><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula>. Let <inline-formula id="IE191"><mml:math id="IM192"><mml:mrow><mml:msub><mml:mi>p</mml:mi><mml:mi>w</mml:mi></mml:msub><mml:mo>=</mml:mo><mml:msub><mml:mi mathvariant="script">S</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi>S</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE192"><mml:math id="IM193"><mml:mrow><mml:msub><mml:mi>p</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:msub><mml:mi mathvariant="script">S</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi>S</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> be the set of the positions of the minimizers in <inline-formula id="IE193"><mml:math id="IM194"><mml:mrow><mml:msub><mml:mi>S</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> when computing the minimizers for <italic>w</italic> and <italic>w</italic> + 1, respectively. Because the order of the de Bruijn sequence is large enough, <inline-formula id="IE194"><mml:math id="IM195"><mml:mrow><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:mo>|</mml:mo><mml:msub><mml:mi>p</mml:mi><mml:mi>w</mml:mi></mml:msub><mml:mo>|</mml:mo><mml:mo>/</mml:mo><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE195"><mml:math id="IM196"><mml:mrow><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:mo>|</mml:mo><mml:msub><mml:mi>p</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>|</mml:mo><mml:mo>/</mml:mo><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:math></inline-formula>. We now show that <inline-formula id="IE196"><mml:math id="IM197"><mml:mrow><mml:msub><mml:mi>p</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> is a subset of <italic>p<sub>w</sub></italic>.</p><p>Let <inline-formula id="IE197"><mml:math id="IM198"><mml:mrow><mml:mo>ℓ</mml:mo><mml:mo>=</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula>. Consider the windows <inline-formula id="IE198"><mml:math id="IM199"><mml:mrow><mml:msub><mml:mi>S</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo>,</mml:mo><mml:mo>ℓ</mml:mo><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE199"><mml:math id="IM200"><mml:mrow><mml:msub><mml:mi>S</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo>,</mml:mo><mml:mo>ℓ</mml:mo><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>, containing <italic>w</italic> and <italic>w</italic> + 1 <italic>k</italic>-mers, respectively, both starting at base <italic>i</italic> in <inline-formula id="IE200"><mml:math id="IM201"><mml:mrow><mml:msub><mml:mi>S</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula>. <inline-formula id="IE201"><mml:math id="IM202"><mml:mrow><mml:msub><mml:mi>S</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo>,</mml:mo><mml:mo>ℓ</mml:mo><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula> contains one extra <italic>k</italic>-mer compared to <inline-formula id="IE202"><mml:math id="IM203"><mml:mrow><mml:msub><mml:mi>S</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo>,</mml:mo><mml:mo>ℓ</mml:mo><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>, the right-most <italic>k</italic>-mer starting at position <italic>i </italic>+<italic> w</italic>. Hence, if a different minimizer is selected in these two windows when computing minimizers for <italic>w</italic> and <italic>w</italic> + 1 respectively, then the <italic>k</italic>-mer at position <italic>i </italic>+<italic> w</italic> must compare less than any <italic>k</italic>-mer in <inline-formula id="IE203"><mml:math id="IM204"><mml:mrow><mml:msub><mml:mi>S</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo>,</mml:mo><mml:mo>ℓ</mml:mo><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>. Then the <italic>k</italic>-mer at position <italic>i </italic>+<italic> w</italic> also compares less than any <italic>k</italic>-mer in <inline-formula id="IE204"><mml:math id="IM205"><mml:mrow><mml:msub><mml:mi>S</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mo>ℓ</mml:mo><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>, and the position <italic>i </italic>+<italic> w</italic> is also in <italic>p<sub>w</sub></italic>. □</p><p>This previous proposition and the previously known lower-bound on the density, such as <inline-formula id="IE205"><mml:math id="IM206"><mml:mrow><mml:mn>2</mml:mn><mml:mo>/</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>, might suggests that the density of a minimizers scheme goes to 0 asymptotically in <italic>w</italic>. That is not the case however, as shown in this next proposition.</p></statement><statement id="mthst12"><p><italic>Proposition 6</italic>. For any minimizers scheme <italic>f</italic>, <inline-formula id="IE206"><mml:math id="IM207"><mml:mrow><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo>≥</mml:mo><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:mo>−</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:math></inline-formula>.</p><p>P<sc>roof</sc>. Let <italic>μ</italic> be the <italic>k</italic>-mer that is the lowest for the ordering <italic>f</italic>. In the minimizers scheme, every instance of <italic>μ</italic> in the sequence is the left-most smallest <italic>k</italic>-mer for some window. Hence the algorithm selects as minimizers every instance of <italic>μ</italic>. In a de Bruijn sequence of order <inline-formula id="IE207"><mml:math id="IM208"><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:math></inline-formula>, every <italic>k</italic>-mer occurs the same number of times, <italic>σ<sup>w</sup></italic> times. Hence the density is <inline-formula id="IE208"><mml:math id="IM209"><mml:mrow><mml:mo>≥</mml:mo><mml:msup><mml:mo>σ</mml:mo><mml:mi>w</mml:mi></mml:msup><mml:mo>/</mml:mo><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msup><mml:mo>=</mml:mo><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:mo>−</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:math></inline-formula>. □</p><p>As the consequence, the expected density factor is not a constant but rather grows at least linearly <inline-formula id="IE209"><mml:math id="IM210"><mml:mrow><mml:mo>≥</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo><mml:mo>/</mml:mo><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:math></inline-formula>. Moreover this lower-bound is tight.</p></statement><statement id="mthst13"><p><italic>Theorem 2</italic>. For any minimizers scheme <italic>f</italic>, the density <inline-formula id="IE210"><mml:math id="IM211"><mml:mrow><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> converges asymptotically in <italic>w</italic> to <inline-formula id="IE211"><mml:math id="IM212"><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:mo>−</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:math></inline-formula>:
<disp-formula id="E31"><mml:math id="M30"><mml:mrow><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:munder><mml:mo stretchy="true">→</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>→</mml:mo><mml:mo>∞</mml:mo></mml:mrow></mml:munder><mml:mfrac><mml:mn>1</mml:mn><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>P<sc>roof</sc>. Let <inline-formula id="IE212"><mml:math id="IM213"><mml:mrow><mml:msub><mml:mi>S</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> be a de Bruijn sequence of order <italic>k </italic>+<italic> w</italic> and <italic>μ</italic> the smallest <italic>k</italic>-mer for the ordering <italic>f</italic>. In every window that contains <italic>μ</italic>, it is the selected minimizer. Let <italic>A<sub>w</sub></italic> be the set of all the windows of <inline-formula id="IE213"><mml:math id="IM214"><mml:mrow><mml:msub><mml:mi>S</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> that do not contain <italic>μ</italic>. As a worst case scenario, assume that in every window of <italic>A<sub>w</sub></italic>, a different minimizer is selected. In that worst case, the set of selected positions contains all the <italic>σ<sup>w</sup></italic> instances of <italic>μ</italic> in <inline-formula id="IE214"><mml:math id="IM215"><mml:mrow><mml:msub><mml:mi>S</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> and one position in each of the windows of <italic>A<sub>w</sub></italic>. This gives us an upper-bound on the density:
<disp-formula id="E32"><label>(17)</label><mml:math id="M31"><mml:mrow><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi>S</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:msub><mml:mi mathvariant="script">S</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:mfrac><mml:mo>≤</mml:mo><mml:mfrac><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mi>w</mml:mi></mml:msup><mml:mo>+</mml:mo><mml:mo>|</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>w</mml:mi></mml:msub><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:mfrac><mml:mo>=</mml:mo><mml:mfrac><mml:mn>1</mml:mn><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac><mml:mo>+</mml:mo><mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>w</mml:mi></mml:msub><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:mfrac><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula>We will show that as <italic>w</italic> increases, the proportion <inline-formula id="IE215"><mml:math id="IM216"><mml:mrow><mml:mo>|</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>w</mml:mi></mml:msub><mml:mo>|</mml:mo><mml:mo>/</mml:mo><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:math></inline-formula> goes to zero, in other words most windows contain <italic>μ</italic> and the only <italic>k</italic>-mer that matters with respect to the density is <italic>μ</italic>.</p><p>Because <inline-formula id="IE216"><mml:math id="IM217"><mml:mrow><mml:msub><mml:mi>S</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> is a de Bruijn sequence, every possible window of <italic>w</italic> consecutive <italic>k</italic>-mers occurs exactly <italic>σ</italic> times in <inline-formula id="IE217"><mml:math id="IM218"><mml:mrow><mml:msub><mml:mi>S</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula>. Hence, the proportion of interest <inline-formula id="IE218"><mml:math id="IM219"><mml:mrow><mml:mo>|</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>w</mml:mi></mml:msub><mml:mo>|</mml:mo><mml:mo>/</mml:mo><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:math></inline-formula> is exactly the probability of the event that <italic>μ</italic> is not in a window, and we can use a probabilistic argument. The event that a window <italic>ω</italic> does not contain the <italic>k</italic>-mer <italic>μ</italic> is a subset of the event that the non-overlapping <italic>k</italic>-mers starting at positions <inline-formula id="IE219"><mml:math id="IM220"><mml:mrow><mml:mi>i</mml:mi><mml:mo>·</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>i</mml:mi><mml:mo>∈</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mn>0</mml:mn><mml:mo>:</mml:mo><mml:mrow><mml:mo stretchy="true">⌊</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>/</mml:mo><mml:mi>k</mml:mi></mml:mrow><mml:mo stretchy="true">⌋</mml:mo></mml:mrow><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula> are not equal to <italic>μ</italic>. Hence,
<disp-formula id="E33"><label>(18)</label><mml:math id="M32"><mml:mrow><mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>w</mml:mi></mml:msub><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:mfrac><mml:mo>=</mml:mo><mml:mi>Pr</mml:mi><mml:mo></mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mo>μ</mml:mo><mml:mo>∉</mml:mo><mml:mo>ω</mml:mo><mml:mo stretchy="true">]</mml:mo><mml:mo>≤</mml:mo><mml:msup><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:mfrac><mml:mn>1</mml:mn><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mrow><mml:mrow><mml:mo stretchy="true">⌊</mml:mo><mml:mrow><mml:mfrac><mml:mi>w</mml:mi><mml:mi>k</mml:mi></mml:mfrac></mml:mrow><mml:mo stretchy="true">⌋</mml:mo></mml:mrow></mml:mrow></mml:msup></mml:mrow></mml:math></disp-formula><disp-formula id="E34"><label>(19)</label><mml:math id="M33"><mml:mrow><mml:mo>≤</mml:mo><mml:mtext>exp</mml:mtext><mml:mo> </mml:mo><mml:mo></mml:mo><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mo>−</mml:mo><mml:mfrac><mml:mi>w</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:mfrac></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula>For a fixed <italic>k</italic>, as <italic>w</italic> goes to infinity, this proportion goes to 0. <xref ref-type="disp-formula" rid="E32">Equation (17)</xref> combined with Proposition 6 gives the desired limit for <inline-formula id="IE220"><mml:math id="IM221"><mml:mrow><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula>, for all minimizers scheme <italic>f</italic>. □</p><p><italic>Theorem 2</italic> shows that for very large <italic>w</italic>, all the minimizers schemes are equivalent. Intuitively, when <italic>w</italic> is very large, say <inline-formula id="IE221"><mml:math id="IM222"><mml:mrow><mml:mi>w</mml:mi><mml:mo>≫</mml:mo><mml:msup><mml:mo>σ</mml:mo><mml:mi>k</mml:mi></mml:msup></mml:mrow></mml:math></inline-formula>, every window of <italic>w</italic> consecutive <italic>k</italic>-mers is expected to contain every possible <italic>k</italic>-mer. Hence almost every window contains <italic>μ</italic>, the absolute lowest <italic>k</italic>-mer and almost no other <italic>k</italic>-mer but <italic>μ</italic> is selected as a minimizer. This happens for any order on the <italic>k</italic>-mers.</p><p>For minimizers schemes, the density factor is <inline-formula id="IE222"><mml:math id="IM223"><mml:mrow><mml:mo>θ</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>w</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>, that is it grows linearly. This does not apply for local and forward schemes as the next proposition exhibits a forward scheme whose density factor is <inline-formula id="IE223"><mml:math id="IM224"><mml:mrow><mml:mi>O</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:msqrt><mml:mi>w</mml:mi></mml:msqrt><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>, and therefore a density whose limit is 0 at infinity. The insight for that proof is that a minimizers scheme for parameters <inline-formula id="IE224"><mml:math id="IM225"><mml:mrow><mml:mi>k</mml:mi><mml:mo>′</mml:mo><mml:mo>,</mml:mo><mml:mi>w</mml:mi><mml:mo>′</mml:mo></mml:mrow></mml:math></inline-formula>, different from <italic>k</italic>, <italic>w</italic>, is a valid local scheme for parameters <italic>k</italic>, <italic>w</italic>, so long as <inline-formula id="IE225"><mml:math id="IM226"><mml:mrow><mml:mi>w</mml:mi><mml:mo>′</mml:mo><mml:mo>≤</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE226"><mml:math id="IM227"><mml:mrow><mml:mi>w</mml:mi><mml:mo>′</mml:mo><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>′</mml:mo><mml:mo>≤</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:math></inline-formula>. This holds because any function taking a string of length at most <inline-formula id="IE227"><mml:math id="IM228"><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula> and returns a value within <inline-formula id="IE228"><mml:math id="IM229"><mml:mrow><mml:mo stretchy="true">[</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula> is a valid local scheme.</p></statement><statement id="mthst14"><p><italic>Proposition 7</italic>. There exists a forward scheme whose density factor is <inline-formula id="IE229"><mml:math id="IM230"><mml:mrow><mml:mi>O</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:msqrt><mml:mi>w</mml:mi></mml:msqrt><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>.</p><p>P<sc>roof</sc>. Let’s set <inline-formula id="IE230"><mml:math id="IM231"><mml:mrow><mml:mi>k</mml:mi><mml:mo>′</mml:mo><mml:mo>=</mml:mo><mml:msub><mml:mrow><mml:mtext>log</mml:mtext><mml:mo></mml:mo></mml:mrow><mml:mo>σ</mml:mo></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msqrt><mml:mi>w</mml:mi></mml:msqrt><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE231"><mml:math id="IM232"><mml:mrow><mml:mi>w</mml:mi><mml:mo>′</mml:mo><mml:mo>=</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mi>k</mml:mi><mml:mo>′</mml:mo></mml:mrow></mml:math></inline-formula> and consider a minimizers scheme <inline-formula id="IE232"><mml:math id="IM233"><mml:mrow><mml:mi>f</mml:mi><mml:mo>′</mml:mo></mml:mrow></mml:math></inline-formula> for parameters <inline-formula id="IE233"><mml:math id="IM234"><mml:mrow><mml:mi>k</mml:mi><mml:mo>′</mml:mo><mml:mo>,</mml:mo><mml:mi>w</mml:mi><mml:mo>′</mml:mo></mml:mrow></mml:math></inline-formula>. For large values of <italic>w</italic>, <inline-formula id="IE234"><mml:math id="IM235"><mml:mrow><mml:mi>w</mml:mi><mml:mo>′</mml:mo><mml:mo><</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula>, and <inline-formula id="IE235"><mml:math id="IM236"><mml:mrow><mml:mi>f</mml:mi><mml:mo>′</mml:mo></mml:mrow></mml:math></inline-formula> returns an offset in <inline-formula id="IE236"><mml:math id="IM237"><mml:mrow><mml:mo stretchy="true">[</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mi>w</mml:mi><mml:mo>′</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo><mml:mo>⊂</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>, hence <inline-formula id="IE237"><mml:math id="IM238"><mml:mrow><mml:mi>f</mml:mi><mml:mo>′</mml:mo></mml:mrow></mml:math></inline-formula> is a valid forward scheme for parameters <italic>k</italic>, <italic>w</italic>. In a de Bruijn sequence of order <italic>w </italic>+<italic> k</italic>, the minimum <italic>k′</italic>-mer <inline-formula id="IE238"><mml:math id="IM239"><mml:mrow><mml:mo>μ</mml:mo><mml:mo>′</mml:mo></mml:mrow></mml:math></inline-formula> of the ordering <inline-formula id="IE239"><mml:math id="IM240"><mml:mrow><mml:mi>f</mml:mi><mml:mo>′</mml:mo></mml:mrow></mml:math></inline-formula> occurs <inline-formula id="IE240"><mml:math id="IM241"><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:msup><mml:mi>k</mml:mi><mml:mo>′</mml:mo></mml:msup></mml:mrow></mml:msup></mml:mrow></mml:math></inline-formula> times, hence, following the same proof as Theorem 2, the density of <inline-formula id="IE241"><mml:math id="IM242"><mml:mrow><mml:mi>f</mml:mi><mml:mo>′</mml:mo></mml:mrow></mml:math></inline-formula> on <inline-formula id="IE242"><mml:math id="IM243"><mml:mrow><mml:msub><mml:mi>S</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> satisfies
<disp-formula id="E35"><label>(20)</label><mml:math id="M34"><mml:mrow><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>′</mml:mo><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mi>S</mml:mi><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:msub><mml:mi mathvariant="script">S</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>′</mml:mo><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:mfrac><mml:mo>≤</mml:mo><mml:mfrac><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:msup><mml:mi>k</mml:mi><mml:mo>′</mml:mo></mml:msup></mml:mrow></mml:msup><mml:mo>+</mml:mo><mml:mo>|</mml:mo><mml:mi>A</mml:mi><mml:msub><mml:mo>′</mml:mo><mml:mi>w</mml:mi></mml:msub><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:mfrac></mml:mrow></mml:math></disp-formula><disp-formula id="E36"><label>(21)</label><mml:math id="M35"><mml:mrow><mml:mo>≤</mml:mo><mml:mfrac><mml:mn>1</mml:mn><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:msup><mml:mi>k</mml:mi><mml:mo>′</mml:mo></mml:msup></mml:mrow></mml:msup></mml:mrow></mml:mfrac><mml:mo>+</mml:mo><mml:mtext>exp</mml:mtext><mml:mo> </mml:mo><mml:mo></mml:mo><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mo>−</mml:mo><mml:mfrac><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mi>k</mml:mi><mml:mo>′</mml:mo></mml:mrow><mml:mrow><mml:mi>k</mml:mi><mml:mo>′</mml:mo><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:msup><mml:mi>k</mml:mi><mml:mo>′</mml:mo></mml:msup></mml:mrow></mml:msup></mml:mrow></mml:mfrac></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula>where <inline-formula id="IE243"><mml:math id="IM244"><mml:mrow><mml:mi>A</mml:mi><mml:msub><mml:mo>′</mml:mo><mml:mi>w</mml:mi></mml:msub></mml:mrow></mml:math></inline-formula> is the set of windows not containing <inline-formula id="IE244"><mml:math id="IM245"><mml:mrow><mml:mo>μ</mml:mo><mml:mo>′</mml:mo></mml:mrow></mml:math></inline-formula>. Consequently, the density factor satisfies
<disp-formula id="E37"><label>(22)</label><mml:math id="M36"><mml:mrow><mml:msub><mml:mrow><mml:mtext>df</mml:mtext></mml:mrow><mml:mrow><mml:mi>f</mml:mi><mml:mo>′</mml:mo><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo>≤</mml:mo><mml:mfrac><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mrow><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:msup><mml:mi>k</mml:mi><mml:mo>′</mml:mo></mml:msup></mml:mrow></mml:msup></mml:mrow></mml:mfrac><mml:mo>+</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo><mml:mo> </mml:mo><mml:mtext>exp</mml:mtext><mml:mo> </mml:mo><mml:mo></mml:mo><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mo>−</mml:mo><mml:mfrac><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mi>k</mml:mi><mml:mo>′</mml:mo></mml:mrow><mml:mrow><mml:mi>k</mml:mi><mml:mo>′</mml:mo><mml:msup><mml:mo>σ</mml:mo><mml:mrow><mml:msup><mml:mi>k</mml:mi><mml:mo>′</mml:mo></mml:msup></mml:mrow></mml:msup></mml:mrow></mml:mfrac></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:math></disp-formula><disp-formula id="E38"><label>(23)</label><mml:math id="M37"><mml:mrow><mml:mo>≤</mml:mo><mml:mfrac><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mrow><mml:msqrt><mml:mi>w</mml:mi></mml:msqrt></mml:mrow></mml:mfrac><mml:mo>+</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo><mml:mo> </mml:mo><mml:mtext>exp</mml:mtext><mml:mo> </mml:mo><mml:mo></mml:mo><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mo>−</mml:mo><mml:mfrac><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:msub><mml:mrow><mml:mtext>log</mml:mtext><mml:mo></mml:mo></mml:mrow><mml:mo>σ</mml:mo></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msqrt><mml:mi>w</mml:mi></mml:msqrt><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mrow><mml:mo> </mml:mo><mml:msub><mml:mrow><mml:mtext>log</mml:mtext><mml:mo></mml:mo></mml:mrow><mml:mo>σ</mml:mo></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msqrt><mml:mi>w</mml:mi></mml:msqrt><mml:mo stretchy="true">)</mml:mo><mml:msqrt><mml:mi>w</mml:mi></mml:msqrt></mml:mrow></mml:mfrac></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula>Asymptotically, expression 23 is <inline-formula id="IE245"><mml:math id="IM246"><mml:mrow><mml:mi>O</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:msqrt><mml:mi>w</mml:mi></mml:msqrt><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>. □</p><p>Forward schemes do not necessarily have a linear growth for the density factor. The lowest asymptotic density factor achievable by local schemes and forward schemes is still an open question.</p></statement></sec><sec><title>3.3 Lower bound on forward schemes</title><p>When introducing the winnowing scheme, <xref rid="bty258-B18" ref-type="bibr">Schleimer <italic>et al.</italic> (2003)</xref> provided a lower-bound on the density factor for local schemes of <inline-formula id="IE246"><mml:math id="IM247"><mml:mrow><mml:mn>1.5</mml:mn><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mn>2</mml:mn><mml:mi>w</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>. Unfortunately, their definition of a local scheme differs slightly from ours as they assume that the input <italic>k</italic>-mers are first hashed into fingerprints and that those fingerprints can be assumed independent and uniformly distributed. This is a weaker setting than what is considered here.</p><p>Moreover, their theorem does not apply to all local schemes, but only to forward schemes. For a forward scheme, instead of counting the number of selected <italic>k</italic>-mers, we use instead <italic>charged windows</italic>. A window is charged if it is the window with the smallest starting position where a given <italic>k</italic>-mer is selected. More precisely, for a forward scheme <italic>f</italic>, a window is charged if its selected <italic>k</italic>-mer is different than in the preceding window, i.e. the window <italic>ω<sub>i</sub></italic> starting at position <italic>i</italic> is charged when <inline-formula id="IE247"><mml:math id="IM248"><mml:mrow><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mi>f</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mo>ω</mml:mo><mml:mi>i</mml:mi></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>></mml:mo><mml:mi>i</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:mi>f</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mo>ω</mml:mo><mml:mrow><mml:mi>i</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>. For a forward scheme, the number of charged window is equal to the number of selected <italic>k</italic>-mers and the density is equivalently computed from the number of charged windows. This property, which is not satisfied by general local schemes, is explicitly used in the proof of <xref rid="bty258-B18" ref-type="bibr">Schleimer <italic>et al.</italic> (2003)</xref> and in the proof of the following theorem.</p><p>The theorem below is a refinement of Theorem 1 of <xref rid="bty258-B18" ref-type="bibr">Schleimer <italic>et al.</italic> (2003)</xref> and it uses the same proof technique. The idea is to look at two windows that are disjoint, and therefore the choice of a selected <italic>k</italic>-mer in each window is independent from the choice in the other window, and to estimate the number of <italic>k</italic>-mers that must be selected between the two windows. We first have a Lemma.</p><statement id="mthst15"><p><italic>Lemma 2</italic>. Let <italic>X</italic> and <italic>Y</italic> be two discrete random variables with values in <inline-formula id="IE248"><mml:math id="IM249"><mml:mrow><mml:mo>{</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo>}</mml:mo></mml:mrow></mml:math></inline-formula> which are independent and have the same distribution. Then, <inline-formula id="IE249"><mml:math id="IM250"><mml:mrow><mml:mi>Pr</mml:mi><mml:mo></mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mi>X</mml:mi><mml:mo>≥</mml:mo><mml:mi>Y</mml:mi><mml:mo stretchy="true">]</mml:mo><mml:mo>≥</mml:mo><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mn>2</mml:mn><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mn>2</mml:mn><mml:mi>w</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>.</p><p>P<sc>roof</sc>. Because <italic>X</italic> and <italic>Y</italic> are IID, <inline-formula id="IE250"><mml:math id="IM251"><mml:mrow><mml:mi>Pr</mml:mi><mml:mo></mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mi>X</mml:mi><mml:mo>></mml:mo><mml:mi>Y</mml:mi><mml:mo stretchy="true">]</mml:mo><mml:mo>=</mml:mo><mml:mi>Pr</mml:mi><mml:mo></mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mi>Y</mml:mi><mml:mo>></mml:mo><mml:mi>X</mml:mi><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>, hence
<disp-formula id="E39"><label>(24)</label><mml:math id="M38"><mml:mrow><mml:mi>Pr</mml:mi><mml:mo></mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mi>X</mml:mi><mml:mo>></mml:mo><mml:mi>Y</mml:mi><mml:mo stretchy="true">]</mml:mo><mml:mo>=</mml:mo><mml:mfrac><mml:mrow><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:mi>Pr</mml:mi><mml:mo></mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mi>X</mml:mi><mml:mo>=</mml:mo><mml:mi>Y</mml:mi><mml:mo stretchy="true">]</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:mfrac></mml:mrow></mml:math></disp-formula><disp-formula id="E40"><label>(25)</label><mml:math id="M39"><mml:mrow><mml:mi>Pr</mml:mi><mml:mo></mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mi>X</mml:mi><mml:mo>≥</mml:mo><mml:mi>Y</mml:mi><mml:mo stretchy="true">]</mml:mo><mml:mo>=</mml:mo><mml:mfrac><mml:mrow><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:mi>Pr</mml:mi><mml:mo></mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mi>X</mml:mi><mml:mo>=</mml:mo><mml:mi>Y</mml:mi><mml:mo stretchy="true">]</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:mfrac><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>We now get a lower bound on <inline-formula id="IE251"><mml:math id="IM252"><mml:mrow><mml:mi>Pr</mml:mi><mml:mo></mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mi>X</mml:mi><mml:mo>=</mml:mo><mml:mi>Y</mml:mi><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>. Let <inline-formula id="IE252"><mml:math id="IM253"><mml:mrow><mml:mover accent="true"><mml:mi>u</mml:mi><mml:mo>⃗</mml:mo></mml:mover></mml:mrow></mml:math></inline-formula> be a vector whose coordinates are <inline-formula id="IE253"><mml:math id="IM254"><mml:mrow><mml:mi>Pr</mml:mi><mml:mo></mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mi>X</mml:mi><mml:mo>=</mml:mo><mml:mi>i</mml:mi><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula> for <inline-formula id="IE254"><mml:math id="IM255"><mml:mrow><mml:mi>i</mml:mi><mml:mo>∈</mml:mo><mml:mo>{</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo>}</mml:mo></mml:mrow></mml:math></inline-formula>, and let <inline-formula id="IE255"><mml:math id="IM256"><mml:mrow><mml:mover accent="true"><mml:mn>1</mml:mn><mml:mo>⃗</mml:mo></mml:mover></mml:mrow></mml:math></inline-formula> be the vector of all 1s. Because the variables are IID, <inline-formula id="IE256"><mml:math id="IM257"><mml:mrow><mml:mi>Pr</mml:mi><mml:mo></mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mi>X</mml:mi><mml:mo>=</mml:mo><mml:mi>Y</mml:mi><mml:mo stretchy="true">]</mml:mo><mml:mo>=</mml:mo><mml:mo>‖</mml:mo><mml:mrow><mml:mover accent="true"><mml:mi>u</mml:mi><mml:mo>⃗</mml:mo></mml:mover></mml:mrow><mml:msup><mml:mo>‖</mml:mo><mml:mn>2</mml:mn></mml:msup></mml:mrow></mml:math></inline-formula>, and by the Cauchy–Schwartz inequality
<disp-formula id="E41"><label>(26)</label><mml:math id="M40"><mml:mrow><mml:mo>|</mml:mo><mml:mrow><mml:mover accent="true"><mml:mn>1</mml:mn><mml:mo>⃗</mml:mo></mml:mover></mml:mrow><mml:mo>·</mml:mo><mml:mrow><mml:mover accent="true"><mml:mi>u</mml:mi><mml:mo>⃗</mml:mo></mml:mover></mml:mrow><mml:mo>|</mml:mo><mml:mo>=</mml:mo><mml:mn>1</mml:mn><mml:mo>≤</mml:mo><mml:mo>‖</mml:mo><mml:mrow><mml:mover accent="true"><mml:mn>1</mml:mn><mml:mo>⃗</mml:mo></mml:mover></mml:mrow><mml:msup><mml:mo>‖</mml:mo><mml:mn>2</mml:mn></mml:msup><mml:mo>‖</mml:mo><mml:mrow><mml:mover accent="true"><mml:mi>u</mml:mi><mml:mo>⃗</mml:mo></mml:mover></mml:mrow><mml:msup><mml:mo>‖</mml:mo><mml:mn>2</mml:mn></mml:msup><mml:mo>=</mml:mo><mml:mi>w</mml:mi><mml:mi>Pr</mml:mi><mml:mo></mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mi>X</mml:mi><mml:mo>=</mml:mo><mml:mi>Y</mml:mi><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></disp-formula></p><p>□</p></statement><statement id="mthst16"><p><italic>Theorem 3</italic>. The density of any forward scheme satisfies
<disp-formula id="E42"><mml:math id="M41"><mml:mrow><mml:msub><mml:mi>d</mml:mi><mml:mrow><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:msub><mml:mo>≥</mml:mo><mml:mfrac><mml:mrow><mml:mn>1.5</mml:mn><mml:mo>+</mml:mo><mml:mi>max</mml:mi><mml:mo></mml:mo><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mrow><mml:mo stretchy="true">⌊</mml:mo><mml:mrow><mml:mfrac><mml:mrow><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mi>w</mml:mi></mml:mrow><mml:mi>w</mml:mi></mml:mfrac></mml:mrow><mml:mo stretchy="true">⌋</mml:mo></mml:mrow></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mo>+</mml:mo><mml:mfrac><mml:mn>1</mml:mn><mml:mrow><mml:mn>2</mml:mn><mml:mi>w</mml:mi></mml:mrow></mml:mfrac></mml:mrow><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:mfrac><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>P<sc>roof</sc>. Let <inline-formula id="IE257"><mml:math id="IM258"><mml:mrow><mml:mi>f</mml:mi><mml:mo>:</mml:mo><mml:msup><mml:mo>Σ</mml:mo><mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo>→</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula> be a forward scheme, and consider two windows of <italic>w</italic> consecutive <italic>k</italic>-mers, <inline-formula id="IE258"><mml:math id="IM259"><mml:mrow><mml:msub><mml:mo>ω</mml:mo><mml:mn>1</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mi>S</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo>,</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE259"><mml:math id="IM260"><mml:mrow><mml:msub><mml:mo>ω</mml:mo><mml:mn>2</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mi>S</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>, starting, respectively, at base <italic>i</italic> and <inline-formula id="IE260"><mml:math id="IM261"><mml:mrow><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula> (<xref ref-type="fig" rid="bty258-F2">Fig. 2</xref>). The last base of <italic>ω</italic><sub>1</sub> is at index <inline-formula id="IE261"><mml:math id="IM262"><mml:mrow><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math></inline-formula>, hence there is no shared sequence between the two windows, and a gap of two bases between the two windows. Without loss of generality, we can assume that the input sequence is a de Bruijn sequence of large enough order so that every possible pair of windows <italic>ω</italic><sub>1</sub> and <italic>ω</italic><sub>2</sub> is encountered, the same number of times. We can therefore use a probabilistic argument: the starting position <italic>i</italic> is chosen at random, consequently the strings <italic>ω</italic><sub>1</sub> and <italic>ω</italic><sub>2</sub> are IID.</p></statement><fig id="bty258-F2" orientation="portrait" position="float"><label>Fig. 2.</label><caption><p>The sequence is represented by a thick vertical line, and each base is a tick mark. In this example, <italic>k</italic> = 3, <italic>w</italic> = 4, <inline-formula id="IE262"><mml:math id="IM263"><mml:mrow><mml:msub><mml:mi>X</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mo>ω</mml:mo><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE263"><mml:math id="IM264"><mml:mrow><mml:msub><mml:mi>X</mml:mi><mml:mn>2</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mo>ω</mml:mo><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math></inline-formula>. The first base, last <italic>k</italic>-mer start and last base of <italic>ω</italic><sub>1</sub> and <italic>ω</italic><sub>2</sub> are <italic>i</italic>, <inline-formula id="IE264"><mml:math id="IM265"><mml:mrow><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mo> </mml:mo><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE265"><mml:math id="IM266"><mml:mrow><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mo> </mml:mo><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mn>2</mml:mn><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mo> </mml:mo><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mn>2</mml:mn><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>2</mml:mn><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula>, respectively. The selected <italic>k</italic>-mers are marked with a circle at positions <italic>s</italic><sub>1</sub> and <italic>s</italic><sub>2</sub>. Δ is the number of bases between, and excluding, the selected <italic>k</italic>-mers. There are <italic>w </italic>+<italic> k</italic> windows that can be charged after <italic>ω</italic><sub>1</sub> and before <italic>ω</italic><sub>2</sub>, between bases <italic>i</italic> + 1 and <italic>i </italic>+<italic> w</italic> + <italic>k</italic> included</p></caption><graphic xlink:href="bty258f2"></graphic></fig><p>We are counting the number of charged windows starting at positions in the interval <inline-formula id="IE266"><mml:math id="IM267"><mml:mrow><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>, that is all the windows after <italic>ω</italic><sub>1</sub> and before <italic>ω</italic><sub>2</sub>. Consider the random variables of the offset of the selected <italic>k</italic>-mer in each window, <inline-formula id="IE267"><mml:math id="IM268"><mml:mrow><mml:msub><mml:mi>X</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mi>f</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mo>ω</mml:mo><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE268"><mml:math id="IM269"><mml:mrow><mml:msub><mml:mi>X</mml:mi><mml:mn>2</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mi>f</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mo>ω</mml:mo><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>. Because the windows <italic>ω</italic><sub>1</sub> and <italic>ω</italic><sub>2</sub> do not share any sequence, <italic>X</italic><sub>1</sub> and <italic>X</italic><sub>2</sub> are independent and have the same distribution. The respective positions of the selected <italic>k</italic>-mer in <italic>ω</italic><sub>1</sub> and <italic>ω</italic><sub>2</sub> is <inline-formula id="IE269"><mml:math id="IM270"><mml:mrow><mml:msub><mml:mi>s</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:msub><mml:mi>X</mml:mi><mml:mn>1</mml:mn></mml:msub></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE270"><mml:math id="IM271"><mml:mrow><mml:msub><mml:mi>s</mml:mi><mml:mn>2</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:msub><mml:mi>X</mml:mi><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:math></inline-formula>.</p><p>At least one window with starting index in <inline-formula id="IE271"><mml:math id="IM272"><mml:mrow><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:msub><mml:mi>s</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula> must be charged, as the <italic>k</italic>-mer selected in window <italic>ω</italic><sub>1</sub> is not in the window starting at position <inline-formula id="IE272"><mml:math id="IM273"><mml:mrow><mml:msub><mml:mi>s</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula>. Moreover, additional windows must be charged if the number of bases between <italic>s</italic><sub>1</sub> and <italic>s</italic><sub>2</sub> (excluding bases at <italic>s</italic><sub>1</sub> and <italic>s</italic><sub>2</sub>) is larger or equal to 2<italic>w</italic>. If Δ is the distance between <italic>s</italic><sub>1</sub> and <italic>s</italic><sub>2</sub>, the number of extra <italic>k</italic>-mers to select is <inline-formula id="IE273"><mml:math id="IM274"><mml:mrow><mml:mrow><mml:mo stretchy="true">⌊</mml:mo><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mo>Δ</mml:mo><mml:mo>−</mml:mo><mml:mi>w</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow><mml:mo stretchy="true">⌋</mml:mo></mml:mrow></mml:mrow></mml:math></inline-formula> if <inline-formula id="IE274"><mml:math id="IM275"><mml:mrow><mml:mo>Δ</mml:mo><mml:mo>≥</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula>, 0 otherwise. The number of bases between these two selected <italic>k</italic>-mers is
<disp-formula id="E43"><mml:math id="M42"><mml:mrow><mml:mo>Δ</mml:mo><mml:mo>=</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:msub><mml:mi>X</mml:mi><mml:mn>2</mml:mn></mml:msub><mml:mo>−</mml:mo><mml:msub><mml:mi>X</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mo stretchy="true">⌊</mml:mo><mml:mrow><mml:mi>k</mml:mi><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow><mml:mo stretchy="true">⌋</mml:mo></mml:mrow><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>r</mml:mi><mml:mo>+</mml:mo><mml:msub><mml:mi>X</mml:mi><mml:mn>2</mml:mn></mml:msub><mml:mo>−</mml:mo><mml:msub><mml:mi>X</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula>where <inline-formula id="IE275"><mml:math id="IM276"><mml:mrow><mml:mi>k</mml:mi><mml:mo>=</mml:mo><mml:mrow><mml:mo stretchy="true">⌊</mml:mo><mml:mrow><mml:mi>k</mml:mi><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow><mml:mo stretchy="true">⌋</mml:mo></mml:mrow><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>r</mml:mi></mml:mrow></mml:math></inline-formula>. Given that both <italic>X</italic><sub>1</sub> and <italic>X</italic><sub>2</sub> are in <inline-formula id="IE276"><mml:math id="IM277"><mml:mrow><mml:mo stretchy="true">[</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mi>w</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE277"><mml:math id="IM278"><mml:mrow><mml:mi>r</mml:mi><mml:mo>≥</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mo> </mml:mo><mml:msub><mml:mi>X</mml:mi><mml:mn>2</mml:mn></mml:msub><mml:mo>−</mml:mo><mml:msub><mml:mi>X</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>+</mml:mo><mml:mi>r</mml:mi><mml:mo>≥</mml:mo><mml:mo>−</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula>. Therefore <inline-formula id="IE278"><mml:math id="IM279"><mml:mrow><mml:mo>Δ</mml:mo><mml:mo>≥</mml:mo><mml:mrow><mml:mo stretchy="true">⌊</mml:mo><mml:mrow><mml:mi>k</mml:mi><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow><mml:mo stretchy="true">⌋</mml:mo></mml:mrow><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula> and at least an extra <inline-formula id="IE279"><mml:math id="IM280"><mml:mrow><mml:mrow><mml:mo stretchy="true">⌊</mml:mo><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mi>w</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow><mml:mo stretchy="true">⌋</mml:mo></mml:mrow></mml:mrow></mml:math></inline-formula> windows must be charged (provided that <inline-formula id="IE280"><mml:math id="IM281"><mml:mrow><mml:mi>k</mml:mi><mml:mo>≥</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula>).</p><p>When <inline-formula id="IE281"><mml:math id="IM282"><mml:mrow><mml:mo>Δ</mml:mo><mml:mo>≥</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mo stretchy="true">⌊</mml:mo><mml:mrow><mml:mi>k</mml:mi><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow><mml:mo stretchy="true">⌋</mml:mo></mml:mrow><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula>, or equivalently when <inline-formula id="IE282"><mml:math id="IM283"><mml:mrow><mml:msub><mml:mi>X</mml:mi><mml:mn>2</mml:mn></mml:msub><mml:mo>≥</mml:mo><mml:msub><mml:mi>X</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>−</mml:mo><mml:mi>r</mml:mi></mml:mrow></mml:math></inline-formula>, at least one extra window is charged. By Lemma 2, this event occurs with probability
<disp-formula id="E44"><mml:math id="M43"><mml:mrow><mml:mi>Pr</mml:mi><mml:mo></mml:mo><mml:mo stretchy="true">[</mml:mo><mml:msub><mml:mi>X</mml:mi><mml:mn>2</mml:mn></mml:msub><mml:mo>≥</mml:mo><mml:msub><mml:mi>X</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>−</mml:mo><mml:mi>r</mml:mi><mml:mo stretchy="true">]</mml:mo><mml:mo>≥</mml:mo><mml:mi>Pr</mml:mi><mml:mo></mml:mo><mml:mo stretchy="true">[</mml:mo><mml:msub><mml:mi>X</mml:mi><mml:mn>2</mml:mn></mml:msub><mml:mo>≥</mml:mo><mml:msub><mml:mi>X</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">]</mml:mo><mml:mo>≥</mml:mo><mml:mfrac><mml:mrow><mml:mn>1</mml:mn></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:mfrac><mml:mo>+</mml:mo><mml:mfrac><mml:mn>1</mml:mn><mml:mrow><mml:mn>2</mml:mn><mml:mi>w</mml:mi></mml:mrow></mml:mfrac><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>Hence, in any interval <inline-formula id="IE283"><mml:math id="IM284"><mml:mrow><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula> of length <italic>w </italic>+<italic> k</italic>, the expected number of charged windows is at least <inline-formula id="IE284"><mml:math id="IM285"><mml:mrow><mml:mn>1.5</mml:mn><mml:mo>+</mml:mo><mml:mi>max</mml:mi><mml:mo></mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mrow><mml:mo stretchy="true">⌊</mml:mo><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mi>w</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow><mml:mo stretchy="true">⌋</mml:mo></mml:mrow><mml:mo stretchy="true">)</mml:mo><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mn>2</mml:mn><mml:mi>w</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>, and the density of charged windows is as stated. □</p><p>This lower-bound is tight for some extremal cases. For <italic>w</italic> = 1, the lower-bound on the density is 1, which is the value of the density for any scheme. When <inline-formula id="IE285"><mml:math id="IM286"><mml:mrow><mml:mi>k</mml:mi><mml:mo>→</mml:mo><mml:mo>∞</mml:mo></mml:mrow></mml:math></inline-formula>, the lower-bound on the density goes to <inline-formula id="IE286"><mml:math id="IM287"><mml:mrow><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula>, which is achieved asymptotically by the orderings constructed in Section 3.1.</p><p>On the other hand, when <inline-formula id="IE287"><mml:math id="IM288"><mml:mrow><mml:mi>w</mml:mi><mml:mo>→</mml:mo><mml:mo>∞</mml:mo></mml:mrow></mml:math></inline-formula>, the lower-bound on density factor goes to 1.5. It is still an open question whether this bound can be reached asymptotically by a forward scheme.</p></sec></sec><sec><title>4 Discussion</title><sec><title>4.1 Asymptotic behavior in <italic>w</italic></title><p><xref ref-type="fig" rid="bty258-F3">Figure 3</xref> summarizes the known upper and lower-bounds for local, minimizers and forward schemes, for a fixed parameter <italic>k</italic> and varying <italic>w</italic>.
</p><fig id="bty258-F3" orientation="portrait" position="float"><label>Fig. 3.</label><caption><p>For a binary alphabet <italic>σ</italic> = 2 and a fix value of <italic>k</italic> = 3, this plots show the upper-bound and lower-bound for the local-schemes (thick lines ‘LS UB’ and ‘LS LB’) and for the minimizer-schemes (dashed lines ‘MS UB’ and ‘MS LB’). The thin line ‘FS LB’ is the lower-bound for forward scheme. In addition, in the inset, the gray lines show the actual best and worse density factor achievable by a minimizer schemes for <italic>k</italic> = 3 and for <inline-formula id="IE288"><mml:math id="IM289"><mml:mrow><mml:mi>w</mml:mi><mml:mo>∈</mml:mo><mml:mo stretchy="false">[</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mn>27</mml:mn><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:math></inline-formula></p></caption><graphic xlink:href="bty258f3"></graphic></fig><p>The dashed lines show the upper and lower-bound for minimizers schemes. In addition, we computed through exhaustive search (there are ‘only’ 2<sup>3</sup>! = 40 320 different orderings) the actual lowest and highest density factor achievable for <italic>k</italic> = 3 and <inline-formula id="IE289"><mml:math id="IM290"><mml:mrow><mml:mi>w</mml:mi><mml:mo>∈</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mn>27</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>. These values are shown in gray, and the inset zooms in on that region of the graph. The minimizers scheme is the most understood scheme, and the known bounds are tight asymptotically in <italic>w</italic>. Theorem 2 shows that for very large <italic>w</italic>, all the minimizers schemes are equivalent, as the number of selected positions is dominated by the occurrences of the lowest <italic>k</italic>-mer <italic>μ</italic> and this number is the same for any ordering. This is responsible for the linear lower-bound on the density factors. Local and forward schemes do not have that inherent limitation (Proposition 7).</p><p>The thicker lines show the upper and lower-bounds for the local schemes. The upper-bound is tight, as the constant function <inline-formula id="IE290"><mml:math id="IM291"><mml:mrow><mml:mi>f</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mo>ω</mml:mo><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mn>0</mml:mn></mml:mrow></mml:math></inline-formula>, that always picks the first <italic>k</italic>-mer in any window, selects every <italic>k</italic>-mer in the sequence and therefore has a density factor of <italic>w</italic> + 1. On the other hand, it is not known if the trivial lower-bound for local schemes (i.e. one <italic>k</italic>-mer per window hence a density factor of <inline-formula id="IE291"><mml:math id="IM292"><mml:mrow><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula>) is tight or not, even for asymptotic <italic>w</italic>. Theorem 3 shows that this trivial lower-bound cannot be achieved by a forward scheme (the thin line).</p><sec><title><italic>4.1.1</italic> Local schemes are more powerful</title><p>It would be conceivable that for any set of parameters <italic>k</italic>, <italic>w</italic>, there is always a forward scheme that is among the local schemes with the lowest density. Then, the lower-bound of Theorem 3 would also apply to local schemes. However, this is not the case. By formulating the problem of finding a local scheme with lowest density as an Integer Linear Program (ILP), we found set of parameters (e.g. <italic>k</italic> = 2 and <italic>w</italic> = 4) where none of the lowest density solutions are forward schemes. Therefore, the lower-bound on forward schemes may not apply to local scheme in general.</p><p>The local schemes are the largest class of schemes and the least understood. In fact, most of what is known about local schemes is derived from our knowledge of the minimizers schemes and forward schemes. The previous remark shows that the local schemes are strictly more powerful than the other type of schemes, and that the lower-bounds on the density that were previously thought to constrain local schemes (say <inline-formula id="IE292"><mml:math id="IM293"><mml:mrow><mml:mi>d</mml:mi><mml:mo>≥</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mn>1.5</mml:mn><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mn>2</mml:mn><mml:mi>w</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>/</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>w</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>) may not apply. New insights and a deeper understanding of local schemes are necessary to design local schemes with even lower densities. For example, to achieve a low density, a local scheme must not be a forward scheme, that is it must sometimes do backward jumps (i.e. pick <italic>k</italic>-mers in a non-increasing manner). Why such backward jumps are beneficial to reduce the number of selected <italic>k</italic>-mers is not yet understood.</p></sec></sec><sec><title>4.2 Asymptotic behavior in <italic>k</italic></title><p><xref ref-type="fig" rid="bty258-F4">Figure 4</xref> shows, for varying values of <italic>w</italic>, the density obtained by orderings compatible with the universal sets constructed in Section 3.1. The orderings are constructed such that <italic>k</italic>-mers mapping into the wedge <italic>W</italic><sub>0</sub> compare less to the <italic>k</italic>-mers mapping into the slabs, who also compare less than the <italic>k</italic>-mers mapping outside of <inline-formula id="IE293"><mml:math id="IM294"><mml:mrow><mml:mover accent="true"><mml:mrow><mml:msub><mml:mi>W</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:mrow><mml:mo stretchy="true">¯</mml:mo></mml:mover></mml:mrow></mml:math></inline-formula>. Ties are resolved using lexicographic order.
</p><fig id="bty258-F4" orientation="portrait" position="float"><label>Fig. 4.</label><caption><p>Each curve represents, for a fixed value of <italic>w</italic>, the density factor as a function of <italic>k</italic> obtained by minimizers schemes compatible with the universal sets constructed in Section 3.1. The value of <italic>w</italic> is written above the top left most point of each curve. The horizontal dotted line shows the previously believed lower bound for <italic>w</italic> = 2 </p></caption><graphic xlink:href="bty258f4"></graphic></fig><p>For <italic>w</italic> = 2, and <inline-formula id="IE294"><mml:math id="IM295"><mml:mrow><mml:mi>k</mml:mi><mml:mo>≥</mml:mo><mml:mn>14</mml:mn></mml:mrow></mml:math></inline-formula>, the density factor obtained is below <inline-formula id="IE295"><mml:math id="IM296"><mml:mrow><mml:mn>1.5</mml:mn><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mn>2</mml:mn><mml:mi>w</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mn>1.75</mml:mn></mml:mrow></mml:math></inline-formula>, that is below what was previously thought possible. Moreover, such a range of values for the parameters <italic>k</italic> and <italic>w</italic> is potentially useful for some applications. According to Theorem 1, all of the curves on <xref ref-type="fig" rid="bty258-F4">Figure 4</xref> have an asymptote of <inline-formula id="IE296"><mml:math id="IM297"><mml:mrow><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula>, although such low density factors may be reached for relatively large values of <italic>k</italic>, larger than useful in practice. Better orderings compatible with the universal sets than the simple one used here might exist to achieve lower density for smaller values of <italic>k</italic>. Also, even though local schemes are not asymptotically in <italic>k</italic> more powerful than minimizers schemes, local schemes might achieve lower densities for smaller values of <italic>k</italic> and therefore be more practical than the order used here.</p><p>One benefit of the construction of the universal sets in Section 3.1 is that it can be implemented as a test. That is, there is an indicator function using <italic>O</italic>(<italic>k</italic>) memory and <italic>O</italic>(<italic>k</italic>) time to check if a <italic>k</italic>-mer is in the universal set: for a given <italic>k</italic>-mer <italic>m</italic>, computing the vector <inline-formula id="IE297"><mml:math id="IM298"><mml:mrow><mml:msub><mml:mo>ψ</mml:mo><mml:mi>w</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> requires <italic>k</italic> additions. There is no need to pre-compute the universal set or hold it in memory. Similarly, the comparison between two <italic>k</italic>-mers takes <italic>O</italic>(<italic>k</italic>) time.</p><sec><title><italic>4.2.1</italic> Minimum size universal sets</title><p>In <xref rid="bty258-B14" ref-type="bibr">Orenstein <italic>et al.</italic> (2017)</xref>, we proposed the problem of finding universal sets of minimum size in the de Bruijn graph, and gave a heuristic algorithm to find small, although not necessarily minimum, universal sets. In particular, the use of a heuristic was justified by the difficulty of finding vertex cover for path of length <italic>ℓ</italic> in a Directed Acyclic Graph (DAG) (<xref rid="bty258-B15" ref-type="bibr">Paindavoine and Vialla, 2015</xref>). Although this problem is NP-hard for general DAGs, the construction given in Section 3.1 provides a solution that is asymptotically optimal in the particular case of de Bruijn graphs.</p></sec><sec><title><italic>4.2.2</italic> Cycle structure of the de Bruijn graph</title><p>In the following, we propose a high level and intuitive description of why the construction given in Section 3.1 works asymptotically, when <italic>k</italic> is much larger than <italic>w</italic>. Consider a cycle <inline-formula id="IE298"><mml:math id="IM299"><mml:mrow><mml:msub><mml:mi>C</mml:mi><mml:mo>=</mml:mo></mml:msub></mml:mrow></mml:math></inline-formula> of length <italic>ℓ</italic> = <italic>w</italic> in <italic>D<sub>k</sub></italic>. This cycle could have one node in each of the wedges <italic>W<sub>i</sub></italic>. On the other hand, a smaller cycle <italic>C</italic><sub><</sub> of length <inline-formula id="IE299"><mml:math id="IM300"><mml:mrow><mml:mo>ℓ</mml:mo><mml:mo><</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula> cannot have a node in each of the <italic>w</italic> wedges. Therefore, it must have some nodes, if not all, inside of the slabs, close to the diagonal of the hypercube <inline-formula id="IE300"><mml:math id="IM301"><mml:mrow><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mi>w</mml:mi></mml:msub></mml:mrow></mml:math></inline-formula>. For a larger cycle <italic>C</italic><sub>></sub> of length <inline-formula id="IE301"><mml:math id="IM302"><mml:mrow><mml:mo>ℓ</mml:mo><mml:mo>></mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula>, if <italic>ℓ</italic> is a multiple of <italic>w</italic>, the cycle could rotate around the wedges <italic>W<sub>i</sub></italic>, with no nodes falling in the slabs. If <italic>ℓ</italic> is not a multiple of <italic>w</italic>, some nodes of <italic>C</italic><sub>></sub>, but not all, must fall in the slabs as well.</p><p>Let <inline-formula id="IE302"><mml:math id="IM303"><mml:mrow><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mo>ℓ</mml:mo></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> be the number of cycles of length <italic>ℓ</italic> in <italic>D<sub>k</sub></italic>. For a fixed <italic>ℓ</italic>, the function <inline-formula id="IE303"><mml:math id="IM304"><mml:mrow><mml:mi>k</mml:mi><mml:mo>→</mml:mo><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mo>ℓ</mml:mo></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> is increasing until <inline-formula id="IE304"><mml:math id="IM305"><mml:mrow><mml:mi>k</mml:mi><mml:mo>=</mml:mo><mml:mo>ℓ</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula>, then it is constant (<xref rid="bty258-B11" ref-type="bibr">Maurer, 1992</xref>). In other words, when <italic>k</italic> becomes large, the number of cycles of length <inline-formula id="IE305"><mml:math id="IM306"><mml:mrow><mml:mo>≤</mml:mo><mml:mi>w</mml:mi></mml:mrow></mml:math></inline-formula> remains constant, while the number of larger cycles grows, and it grows very quickly. Asymptotically, we can ‘ignore’ the fine grain cycle structure of the de Bruijn graph as the behavior is dominated by long cycles, which tend to be more regular with respect to our embedding.</p><p>Conversely, for values of <italic>k</italic> in the same order of magnitude as <italic>w</italic>, the precise cycle structure of the de Bruijn graph matters, and designing small universal sets or low density schemes requires taking this cycle structure into account.</p></sec></sec></sec><sec><title>5 Conclusion</title><p>In this study, through the asymptotic analysis of minimizers, forward and local schemes, we deepened the theoretical understanding of these techniques and thereby showed that greater improvements than previously thought are possible. In particular, we completely characterized the behavior asymptotically in <italic>k</italic> and gave an efficient algorithm to create the first known optimal minimizers schemes. Because the minimizers schemes are the weakest type of schemes, this shows that all schemes are optimal asymptotically in <italic>k</italic>. For forward schemes, we gave a refined lower-bound that applies to all parameters <italic>k</italic> and <italic>w</italic>.</p><p>The asymptotic behavior in <italic>w</italic> is markedly different than the asymptotic behavior in <italic>k</italic>. For large <italic>w</italic>, the lower-bound for the minimizers schemes is higher than for the forward scheme, which is higher than for local schemes.</p><p>The local schemes are not well understood at all. Although we do have some examples of optimal local schemes found through ILP or brute force search, there is currently no algorithm to generate local schemes with low density. Every algorithm proposed so far is a forward scheme. A greater understanding of local schemes holds, at least for large values of <italic>w</italic>, the greatest promise to design even better schemes.</p></sec><sec><title>Funding</title><p>This work was supported in part by the Gordon and Betty Moore Foundation’s Data-Driven Discovery Initiative through Grant GBMF4554 to C.K., by the US National Science Foundation (CCF-1256087, CCF-1319998) and by the US National Institutes of Health (R01HG007104 and R01GM122935).</p><p><italic>Conflict of Interest</italic>: none declared.</p></sec></body><back><ref-list><title>References</title><ref id="bty258-B1"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>de Bruijn</surname><given-names>N.G.</given-names></name></person-group> (<year>1946</year>)
<article-title>A combinatorial problem</article-title>. <source>Proc. Section Sci. Koninklijke Nederlandse Akademie Van Wetenschappen Te Amsterdam</source>, <volume>49</volume>, <fpage>758</fpage>–<lpage>764</lpage>.</mixed-citation></ref><ref id="bty258-B2"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Deorowicz</surname><given-names>S.</given-names></name></person-group><etal>et al</etal> (<year>2015</year>)
<article-title>KMC 2: fast and resource-frugal k-mer counting</article-title>. <source>Bioinformatics</source>, <volume>31</volume>, <fpage>1569</fpage>–<lpage>1576</lpage>.<pub-id pub-id-type="pmid">25609798</pub-id></mixed-citation></ref><ref id="bty258-B3"><mixed-citation publication-type="book"><person-group person-group-type="author"><name name-style="western"><surname>Grabowski</surname><given-names>S.</given-names></name>, <name name-style="western"><surname>Raniszewski</surname><given-names>M.</given-names></name></person-group> (<year>2015</year>) <chapter-title>Sampling the Suffix Array with Minimizers</chapter-title> In: <person-group person-group-type="editor"><name name-style="western"><surname>Iliopoulos</surname><given-names>C.</given-names></name>, <name name-style="western"><surname>Puglisi</surname><given-names>S.</given-names></name>, <name name-style="western"><surname>Yilmaz</surname><given-names>E.</given-names></name></person-group> (eds.), <source>String Processing and Information Retrieval, Number 9309 in Lecture Notes in Computer Science</source>.
<publisher-name>Springer International Publishing</publisher-name>,
<publisher-loc>Cham</publisher-loc>, pp. <fpage>287</fpage>–<lpage>298</lpage>. ISBN: 978-3-319-23826-5.</mixed-citation></ref><ref id="bty258-B4"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Kawulok</surname><given-names>J.</given-names></name>, <name name-style="western"><surname>Deorowicz</surname><given-names>S.</given-names></name></person-group> (<year>2015</year>)
<article-title>CoMeta: classification of Metagenomes using k-mers</article-title>. <source>Plos One</source>, <volume>10</volume>, <fpage>e0121453.</fpage><pub-id pub-id-type="pmid">25884504</pub-id></mixed-citation></ref><ref id="bty258-B5"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Lempel</surname><given-names>A.</given-names></name></person-group> (<year>1970</year>)
<article-title>On a homomorphism of the de Bruijn graph and its applications to the design of feedback shift registers</article-title>. <source>IEEE Trans. Computers</source>, <volume>C-19</volume>, <fpage>1204</fpage>–<lpage>1209</lpage>.</mixed-citation></ref><ref id="bty258-B6"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Li</surname><given-names>H.</given-names></name></person-group> (<year>2016</year>)
<article-title>Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences</article-title>. <source>Bioinformatics</source>, <volume>32</volume>, <fpage>2103</fpage>–<lpage>2110</lpage>.<pub-id pub-id-type="pmid">27153593</pub-id></mixed-citation></ref><ref id="bty258-B7"><mixed-citation publication-type="other"><person-group person-group-type="author"><name name-style="western"><surname>Li</surname><given-names>Y.</given-names></name>, <name name-style="western"><surname>XifengYan</surname><given-names>X.</given-names></name></person-group> (<year>2015</year>) MSPKmerCounter: a fast and memory efficient approach for K-mer counting. arXiv: 1505.06550.</mixed-citation></ref><ref id="bty258-B8"><mixed-citation publication-type="other"><person-group person-group-type="author"><name name-style="western"><surname>Li</surname><given-names>Y.</given-names></name></person-group><etal>et al</etal> (<year>2013</year>) Memory efficient minimum substring partitioning. In: <italic>Proceedings of the 39th International Conference on Very Large Data Bases</italic>, PVLDB’13. pp. 169–180. VLDB Endowment, Trento, Italy.</mixed-citation></ref><ref id="bty258-B9"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Lichiardopol</surname><given-names>N.</given-names></name></person-group> (<year>2006</year>)
<article-title>Independence number of de Bruijn graphs</article-title>. <source>Discrete Math</source>., <volume>306</volume>, <fpage>1145</fpage>–<lpage>1160</lpage>.</mixed-citation></ref><ref id="bty258-B10"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Marçais</surname><given-names>G.</given-names></name></person-group><etal>et al</etal> (<year>2017</year>)
<article-title>Improving the performance of minimizers and winnowing schemes</article-title>. <source>Bioinformatics</source>, <volume>33</volume>, <fpage>i110</fpage>–<lpage>i117</lpage>.<pub-id pub-id-type="pmid">28881970</pub-id></mixed-citation></ref><ref id="bty258-B11"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Maurer</surname><given-names>U.M.</given-names></name></person-group> (<year>1992</year>)
<article-title>Asymptotically-tight bounds on the number of cycles in generalized de Bruijn-Good graphs</article-title>. <source>Discrete Appl. Math</source>., <volume>37–38</volume>, <fpage>421</fpage>–<lpage>436</lpage>.</mixed-citation></ref><ref id="bty258-B12"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Mykkeltveit</surname><given-names>J.</given-names></name></person-group> (<year>1972</year>)
<article-title>A proof of Golomb’s conjecture for the de Bruijn graph</article-title>. <source>J. Combinatorial Theory, Ser. B</source>, <volume>13</volume>, <fpage>40</fpage>–<lpage>45</lpage>.</mixed-citation></ref><ref id="bty258-B13"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Ondov</surname><given-names>B.D.</given-names></name></person-group><etal>et al</etal> (<year>2016</year>)
<article-title>Mash: fast genome and metagenome distance estimation using MinHash</article-title>. <source>Genome Biol</source>., <volume>17</volume>, <fpage>132.</fpage><pub-id pub-id-type="pmid">27323842</pub-id></mixed-citation></ref><ref id="bty258-B14"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Orenstein</surname><given-names>Y.</given-names></name></person-group><etal>et al</etal> (<year>2017</year>)
<article-title>Designing small universal k-mer hitting sets for improved analysis of high-throughput sequencing</article-title>. <source>PLOS Comput. Biol</source>., <volume>13</volume>, <fpage>e1005777.</fpage><pub-id pub-id-type="pmid">28968408</pub-id></mixed-citation></ref><ref id="bty258-B15"><mixed-citation publication-type="book"><person-group person-group-type="author"><name name-style="western"><surname>Paindavoine</surname><given-names>M.</given-names></name>, <name name-style="western"><surname>Vialla</surname><given-names>B.</given-names></name></person-group> (<year>2015</year>) <chapter-title>Minimizing the number of bootstrappings in fully homomorphic encryption</chapter-title> In: <source>Selected Areas in Cryptography–SAC 2015, Lecture Notes in Computer Science</source>.
<publisher-name>Springer</publisher-name>, Cham, pp. <fpage>25</fpage>–<lpage>43</lpage>.</mixed-citation></ref><ref id="bty258-B16"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Roberts</surname><given-names>M.</given-names></name></person-group><etal>et al</etal> (<year>2004a</year>)
<article-title>A preprocessor for shotgun assembly of large genomes</article-title>. <source>J. Comput. Biol</source>., <volume>11</volume>, <fpage>734</fpage>–<lpage>752</lpage>.<pub-id pub-id-type="pmid">15579242</pub-id></mixed-citation></ref><ref id="bty258-B17"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Roberts</surname><given-names>M.</given-names></name></person-group><etal>et al</etal> (<year>2004b</year>)
<article-title>Reducing storage requirements for biological sequence comparison</article-title>. <source>Bioinformatics</source>, <volume>20</volume>, <fpage>3363</fpage>–<lpage>3369</lpage>.<pub-id pub-id-type="pmid">15256412</pub-id></mixed-citation></ref><ref id="bty258-B18"><mixed-citation publication-type="other"><person-group person-group-type="author"><name name-style="western"><surname>Schleimer</surname><given-names>S.</given-names></name></person-group><etal>et al</etal> (<year>2003</year>) Winnowing: local algorithms for document fingerprinting. In: <italic>Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data</italic>, SIGMOD ’03. ACM, New York, NY, USA, pp. 76–85.</mixed-citation></ref><ref id="bty258-B19"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Wood</surname><given-names>D.E.</given-names></name>, <name name-style="western"><surname>Salzberg</surname><given-names>S.L.</given-names></name></person-group> (<year>2014</year>)
<article-title>Kraken: ultrafast metagenomic sequence classification using exact alignments</article-title>. <source>Genome Biol</source>., <volume>15</volume>, <fpage>R46.</fpage><pub-id pub-id-type="pmid">24580807</pub-id></mixed-citation></ref><ref id="bty258-B20"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Ye</surname><given-names>C.</given-names></name></person-group><etal>et al</etal> (<year>2012</year>)
<article-title>Exploiting sparseness in de novo genome assembly</article-title>. <source>BMC Bioinformatics</source>, <volume>13</volume>, <fpage>S1.</fpage></mixed-citation></ref></ref-list></back></pmc></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Pmc/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000B22 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Pmc/Corpus/biblio.hfd -nk 000B22 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Sante
|area= MersV1
|flux= Pmc
|étape= Corpus
|type= RBID
|clé= PMC:6037127
|texte= Asymptotically optimal minimizers schemes
}}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Pmc/Corpus/RBID.i -Sk "pubmed:29949995" \
| HfdSelect -Kh $EXPLOR_AREA/Data/Pmc/Corpus/biblio.hfd \
| NlmPubMed2Wicri -a MersV1
| This area was generated with Dilib version V0.6.33. |  |