Locality-sensitive hashing for the edit distance
Identifieur interne : 000B23 ( Pmc/Corpus ); précédent : 000B22; suivant : 000B24Locality-sensitive hashing for the edit distance
Auteurs : Guillaume Marçais ; Dan Deblasio ; Prashant Pandey ; Carl KingsfordSource :
- Bioinformatics [ 1367-4803 ] ; 2019.
Abstract
Sequence alignment is a central operation in bioinformatics pipeline and, despite many improvements, remains a computationally challenging problem. Locality-sensitive hashing (LSH) is one method used to estimate the likelihood of two sequences to have a proper alignment. Using an LSH, it is possible to separate, with high probability and relatively low computation, the pairs of sequences that do not have high-quality alignment from those that may. Therefore, an LSH reduces the overall computational requirement while not introducing many false negatives (i.e. omitting to report a valid alignment). However, current LSH methods treat sequences as a bag of
We present an LSH method, called Order Min Hash (OMH), for the edit distance. This method is a refinement of the minHash LSH used to approximate the Jaccard similarity, in that OMH is sensitive not only to the
The code to generate the results is available at
Url:
DOI: 10.1093/bioinformatics/btz354
PubMed: 31510667
PubMed Central: 6612865
Links to Exploration step
PMC:6612865Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Locality-sensitive hashing for the edit distance</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="btz354-aff1">Computational Biology Department, 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="btz354-aff1">Computational Biology Department, Carnegie Mellon University, Pittsburgh, PA, USA</nlm:aff></affiliation></author><author><name sortKey="Pandey, Prashant" sort="Pandey, Prashant" uniqKey="Pandey P" first="Prashant" last="Pandey">Prashant Pandey</name><affiliation><nlm:aff id="btz354-aff1">Computational Biology Department, 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="btz354-aff1">Computational Biology Department, Carnegie Mellon University, Pittsburgh, PA, USA</nlm:aff></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">PMC</idno><idno type="pmid">31510667</idno><idno type="pmc">6612865</idno><idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC6612865</idno><idno type="RBID">PMC:6612865</idno><idno type="doi">10.1093/bioinformatics/btz354</idno><date when="2019">2019</date><idno type="wicri:Area/Pmc/Corpus">000B23</idno><idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000B23</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Locality-sensitive hashing for the edit distance</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="btz354-aff1">Computational Biology Department, 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="btz354-aff1">Computational Biology Department, Carnegie Mellon University, Pittsburgh, PA, USA</nlm:aff></affiliation></author><author><name sortKey="Pandey, Prashant" sort="Pandey, Prashant" uniqKey="Pandey P" first="Prashant" last="Pandey">Prashant Pandey</name><affiliation><nlm:aff id="btz354-aff1">Computational Biology Department, 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="btz354-aff1">Computational Biology Department, 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="2019">2019</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>Sequence alignment is a central operation in bioinformatics pipeline and, despite many improvements, remains a computationally challenging problem. Locality-sensitive hashing (LSH) is one method used to estimate the likelihood of two sequences to have a proper alignment. Using an LSH, it is possible to separate, with high probability and relatively low computation, the pairs of sequences that do not have high-quality alignment from those that may. Therefore, an LSH reduces the overall computational requirement while not introducing many false negatives (i.e. omitting to report a valid alignment). However, current LSH methods treat sequences as a bag of <italic>k</italic>-mers and do not take into account the relative ordering of <italic>k</italic>-mers in sequences. In addition, due to the lack of a practical LSH method for edit distance, in practice, LSH methods for Jaccard similarity or Hamming similarity are used as a proxy.</p></sec><sec id="s2"><title>Results</title><p>We present an LSH method, called Order Min Hash (OMH), for the edit distance. This method is a refinement of the minHash LSH used to approximate the Jaccard similarity, in that OMH is sensitive not only to the <italic>k</italic>-mer contents of the sequences but also to the relative order of the <italic>k</italic>-mers in the sequences. We present theoretical guarantees of the OMH as a gapped LSH.</p></sec><sec id="s3"><title>Availability and implementation</title><p>The code to generate the results is available at <ext-link ext-link-type="uri" xlink:href="http://github.com/Kingsford-Group/omhismb2019">http://github.com/Kingsford-Group/omhismb2019</ext-link>.</p></sec><sec id="s4"><title>Supplementary information</title><p><xref ref-type="supplementary-material" rid="sup1">Supplementary data</xref> are available at <italic>Bioinformatics</italic> online.</p></sec></div></front><back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="Aldous, D" uniqKey="Aldous D">D. Aldous</name></author><author><name sortKey="Diaconis, P" uniqKey="Diaconis P">P. Diaconis</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Alonso, O" uniqKey="Alonso O">O. Alonso</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Backurs, A" uniqKey="Backurs A">A. Backurs</name></author><author><name sortKey="Indyk, P" uniqKey="Indyk P">P. Indyk</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Bar Yossef, Z" uniqKey="Bar Yossef Z">Z. Bar-Yossef</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Berlin, K" uniqKey="Berlin K">K. Berlin</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Broder, A Z" uniqKey="Broder A">A.Z. Broder</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Chum, O" uniqKey="Chum O">O. Chum</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Drew, J" uniqKey="Drew J">J. Drew</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Fredman, M L" uniqKey="Fredman M">M.L. Fredman</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Gollapudi, S" uniqKey="Gollapudi S">S. Gollapudi</name></author><author><name sortKey="Panigrahy, R" uniqKey="Panigrahy R">R. Panigrahy</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Harris, R S" uniqKey="Harris R">R.S. Harris</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Hunt, J W" uniqKey="Hunt J">J.W. Hunt</name></author><author><name sortKey="Szymanski, T G" uniqKey="Szymanski T">T.G. Szymanski</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Indyk, P" uniqKey="Indyk P">P. Indyk</name></author><author><name sortKey="Motwani, R" uniqKey="Motwani R">R. Motwani</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Jaffe, D B" uniqKey="Jaffe D">D.B. Jaffe</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Jain, C" uniqKey="Jain C">C. Jain</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Kushilevitz, E" uniqKey="Kushilevitz E">E. Kushilevitz</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Langmead, B" uniqKey="Langmead B">B. Langmead</name></author><author><name sortKey="Salzberg, S L" uniqKey="Salzberg S">S.L. Salzberg</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Lee, H" uniqKey="Lee H">H. Lee</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Levenshtein, V I" uniqKey="Levenshtein V">V.I. Levenshtein</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Li, H" uniqKey="Li H">H. Li</name></author><author><name sortKey="Durbin, R" uniqKey="Durbin R">R. Durbin</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Liu, C M" uniqKey="Liu C">C.-M. Liu</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Luo, C" uniqKey="Luo C">C. Luo</name></author><author><name sortKey="Shrivastava, A" uniqKey="Shrivastava A">A. Shrivastava</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="Myers, E W" uniqKey="Myers E">E.W. Myers</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="Ostrovsky, R" uniqKey="Ostrovsky R">R. Ostrovsky</name></author><author><name sortKey="Rabani, Y" uniqKey="Rabani Y">Y. Rabani</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Raff, E" uniqKey="Raff E">E. Raff</name></author><author><name sortKey="Nicholas, C" uniqKey="Nicholas C">C. Nicholas</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Shrivastava, A" uniqKey="Shrivastava A">A. Shrivastava</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Wu, W" uniqKey="Wu W">W. Wu</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Zhao, M" uniqKey="Zhao M">M. Zhao</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">31510667</article-id><article-id pub-id-type="pmc">6612865</article-id><article-id pub-id-type="doi">10.1093/bioinformatics/btz354</article-id><article-id pub-id-type="publisher-id">btz354</article-id><article-categories><subj-group subj-group-type="heading"><subject>Ismb/Eccb 2019 Conference Proceedings</subject><subj-group subj-group-type="category-toc-heading"><subject>Comparative and Functional Genomics</subject></subj-group></subj-group></article-categories><title-group><article-title>Locality-sensitive hashing for the edit distance</article-title></title-group><contrib-group><contrib contrib-type="author"><name><surname>Marçais</surname><given-names>Guillaume</given-names></name><xref ref-type="corresp" rid="btz354-cor1"></xref><pmc-comment>gmarcais@cs.cmu.edu </pmc-comment>
<xref ref-type="aff" rid="btz354-aff1"></xref></contrib><contrib contrib-type="author"><name><surname>DeBlasio</surname><given-names>Dan</given-names></name><xref ref-type="aff" rid="btz354-aff1"></xref></contrib><contrib contrib-type="author"><name><surname>Pandey</surname><given-names>Prashant</given-names></name><xref ref-type="aff" rid="btz354-aff1"></xref></contrib><contrib contrib-type="author"><name><surname>Kingsford</surname><given-names>Carl</given-names></name><xref ref-type="corresp" rid="btz354-cor1"></xref><pmc-comment>carlk@cs.cmu.edu </pmc-comment>
<xref ref-type="aff" rid="btz354-aff1"></xref></contrib></contrib-group><aff id="btz354-aff1">Computational Biology Department, Carnegie Mellon University, Pittsburgh, PA, USA</aff><author-notes><corresp id="btz354-cor1">To whom correspondence should be addressed. <email>gmarcais@cs.cmu.edu</email> or <email>carlk@cs.cmu.edu</email></corresp></author-notes><pub-date pub-type="ppub"><month>7</month><year>2019</year></pub-date><pub-date pub-type="epub" iso-8601-date="2019-07-05"><day>05</day><month>7</month><year>2019</year></pub-date><pub-date pub-type="pmc-release"><day>05</day><month>7</month><year>2019</year></pub-date><pmc-comment> PMC Release delay is 0 months and 0 days and was based on the
<volume>35</volume><issue>14</issue><fpage>i127</fpage><lpage>i135</lpage><permissions><copyright-statement>© The Author(s) 2019. Published by Oxford University Press.</copyright-statement><copyright-year>2019</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="btz354.pdf"></self-uri><abstract><title>Abstract</title><sec id="s1"><title>Motivation</title><p>Sequence alignment is a central operation in bioinformatics pipeline and, despite many improvements, remains a computationally challenging problem. Locality-sensitive hashing (LSH) is one method used to estimate the likelihood of two sequences to have a proper alignment. Using an LSH, it is possible to separate, with high probability and relatively low computation, the pairs of sequences that do not have high-quality alignment from those that may. Therefore, an LSH reduces the overall computational requirement while not introducing many false negatives (i.e. omitting to report a valid alignment). However, current LSH methods treat sequences as a bag of <italic>k</italic>-mers and do not take into account the relative ordering of <italic>k</italic>-mers in sequences. In addition, due to the lack of a practical LSH method for edit distance, in practice, LSH methods for Jaccard similarity or Hamming similarity are used as a proxy.</p></sec><sec id="s2"><title>Results</title><p>We present an LSH method, called Order Min Hash (OMH), for the edit distance. This method is a refinement of the minHash LSH used to approximate the Jaccard similarity, in that OMH is sensitive not only to the <italic>k</italic>-mer contents of the sequences but also to the relative order of the <italic>k</italic>-mers in the sequences. We present theoretical guarantees of the OMH as a gapped LSH.</p></sec><sec id="s3"><title>Availability and implementation</title><p>The code to generate the results is available at <ext-link ext-link-type="uri" xlink:href="http://github.com/Kingsford-Group/omhismb2019">http://github.com/Kingsford-Group/omhismb2019</ext-link>.</p></sec><sec id="s4"><title>Supplementary information</title><p><xref ref-type="supplementary-material" rid="sup1">Supplementary data</xref> are available at <italic>Bioinformatics</italic> online.</p></sec></abstract><funding-group><award-group award-type="grant"><funding-source><named-content content-type="funder-name">Gordon and Betty Moore Foundation</named-content><named-content content-type="funder-identifier">10.13039/100000936</named-content></funding-source></award-group><award-group award-type="grant"><funding-source><named-content content-type="funder-name">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 Institutes of Health</named-content></funding-source><award-id>R01GM122935</award-id></award-group><award-group award-type="grant"><funding-source><named-content content-type="funder-name">The Shurl and Kay Curci Foundation</named-content></funding-source></award-group></funding-group><counts><page-count count="9"></page-count></counts></article-meta></front><body><sec><title>1 Introduction</title><p>Measuring sequence similarity is the core of many algorithms in computational biology. For example, in the overlap–layout–consensus paradigm to assemble genomes (e.g. <xref rid="btz354-B14" ref-type="bibr">Jaffe <italic>et al.</italic>, 2003</xref>; <xref rid="btz354-B26" ref-type="bibr">Myers <italic>et al.</italic>, 2000</xref>), the first overlap step consists of aligning the reads against one another to determine which pairs have a significant alignment (an overlap). In meta-genomics, sequencing reads, or longer sequences created from these reads, are aligned against known genomes, or against one another to cluster the sequences, to determine the constituent species of the sample. Sequence similarity is also at the heart of the many general sequence aligners, either genome to genome [e.g. MUMmer4 (<xref rid="btz354-B24" ref-type="bibr">Marçais <italic>et al.</italic>, 2018</xref>), LASTZ (<xref rid="btz354-B11" ref-type="bibr">Harris, 2007</xref>)] or reads to genome [e.g. Bowtie2 (<xref rid="btz354-B17" ref-type="bibr">Langmead and Salzberg, 2012</xref>), BWA (<xref rid="btz354-B20" ref-type="bibr">Li and Durbin, 2010</xref>)], that are used in countless pipelines in bioinformatics.</p><p>Despite many algorithmic and engineering improvements [e.g. implementation on SIMD (<xref rid="btz354-B33" ref-type="bibr">Zhao <italic>et al.</italic>, 2013</xref>) and GPU (<xref rid="btz354-B21" ref-type="bibr">Liu <italic>et al.</italic>, 2012</xref>)], computing the sequence alignment or edit distance between two sequences takes approximately quadratic time in the length of the input sequences, which remains computationally expensive in practice. Given that the edit distance is likely not computable in strong subquadratic time (<xref rid="btz354-B3" ref-type="bibr">Backurs and Indyk, 2015</xref>), most aligners rely on heuristics to more quickly detect sequences with a high probability of having an alignment.</p><p>Recent aligners, such as Mash (<xref rid="btz354-B27" ref-type="bibr">Ondov <italic>et al.</italic>, 2016</xref>), Mashmap (<xref rid="btz354-B15" ref-type="bibr">Jain <italic>et al.</italic>, 2017</xref>), or overlappers such as MHap (<xref rid="btz354-B5" ref-type="bibr">Berlin <italic>et al.</italic>, 2015</xref>), use a method called ‘locality-sensitive hashing’ (LSH) to reduce the amount of work necessary (<xref rid="btz354-B13" ref-type="bibr">Indyk and Motwani, 1998</xref>). The procedure is a dimensionality reduction method and works in two steps. First, the sequences (or part of the sequences) are summarized into <italic>sketches</italic> that are much smaller than the original sequences while preserving important information to estimate how similar two sequences are. Second, by directly comparing those sketches (with no need to refer to the original sequences) or by using these sketches as keys into hash tables, the software finds pairs of sequences that are likely to be similar. A more thorough, and computationally expensive, alignment procedure may then be used on the candidate pairs to refine the actual alignments.</p><p>In an LSH method, the distance between sketches is used as a first approximation for the distance between the sequences. That is, with high probability, two sequences which are very similar must have sketches which are similar, and conversely dissimilar sequences have dissimilar sketches. More precise definition of these concepts is given in Section 2.</p><p>Instead of using an LSH for the edit distance or an alignment score, in practice sequence alignment programs use the minHash LSH (<xref rid="btz354-B6" ref-type="bibr">Broder, 1997</xref>) for the Jaccard similarity or an LSH for the Hamming distance as a proxy for the edit distance. Although these two techniques have proven themselves useful in practice, they suffer from one major flaw: neither the Jaccard similarity nor the Hamming similarity directly corresponds to the edit distance (see Section 2.2 for examples). In fact, it is possible to find sequences that are indistinguishable according to the Jaccard similarity, but have large edit distance. Similarly, with the Hamming distance, there exist sequences with very low edit distance that are completely dissimilar according to the Hamming similarity.</p><p>Depending on the problem and the software implementation, the cases above can lead to false negatives (an alignment is missed) and a decrease in precision, or false positives (a nonexistent potential alignment reported) and extra computational work. An LSH method for edit distance instead of the proxy Jaccard or Hamming similarities would reduce both of these issues.</p><p>Although multiple definitions are possible for sequence similarity (or distance), in this study, we focus on the edit distance (a.k.a. Levenshtein distance, <xref rid="btz354-B19" ref-type="bibr">Levenshtein, 1966</xref>), which is the number of operations (mismatch, insertion, deletion) needed to transform a string into another one.</p><p>Two methods that are LSH for the edit distance have been described previously. <xref rid="btz354-B4" ref-type="bibr">Bar-Yossef <italic>et al.</italic> (2004)</xref> propose a sketch that can distinguish, with some probability, between sequences with edit distance <inline-formula id="IE1"><mml:math id="IM1"><mml:mrow><mml:mo>≤</mml:mo><mml:mi>t</mml:mi></mml:mrow></mml:math></inline-formula> from sequences with edit distance <inline-formula id="IE2"><mml:math id="IM2"><mml:mrow><mml:mo>≥</mml:mo><mml:msup><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mi mathvariant="italic">tn</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mrow><mml:mn>2</mml:mn><mml:mo>/</mml:mo><mml:mn>3</mml:mn></mml:mrow></mml:msup></mml:mrow></mml:math></inline-formula>, where <italic>n</italic> is the length of the sequences, for any <inline-formula id="IE3"><mml:math id="IM3"><mml:mrow><mml:mi>t</mml:mi><mml:mo>≤</mml:mo><mml:msqrt><mml:mi>n</mml:mi></mml:msqrt></mml:mrow></mml:math></inline-formula>. They use an indirect method to obtain an LSH for the edit distance: first they embed the edit distance space into a Hamming space with low distortion, and second, apply an LSH on the Hamming space. That is, the input sequence is first transformed into a bit vector of high dimension, then sketching for the Hamming distance is applied to obtain an LSH for the edit distance.</p><p>Similarly, <xref rid="btz354-B28" ref-type="bibr">Ostrovsky and Rabani (2007)</xref> propose a two-step method, where the edit distance space is first embedded into an <inline-formula id="IE4"><mml:math id="IM4"><mml:mrow><mml:msub><mml:mrow><mml:mi>ℓ</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub></mml:mrow></mml:math></inline-formula> space with low distortion, then a sketching algorithm for the <inline-formula id="IE5"><mml:math id="IM5"><mml:mrow><mml:msub><mml:mrow><mml:mi>ℓ</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub></mml:mrow></mml:math></inline-formula> (<xref rid="btz354-B16" ref-type="bibr">Kushilevitz <italic>et al.</italic>, 2000</xref>) is used to obtain an LSH for the edit distance. This method can distinguish between sequences with edit distance <inline-formula id="IE6"><mml:math id="IM6"><mml:mrow><mml:mo>≤</mml:mo><mml:mi>t</mml:mi></mml:mrow></mml:math></inline-formula> and edit distance <inline-formula id="IE7"><mml:math id="IM7"><mml:mrow><mml:mo>≥</mml:mo><mml:mi>t</mml:mi><mml:mo>·</mml:mo><mml:msup><mml:mrow><mml:mn>2</mml:mn></mml:mrow><mml:mrow><mml:mi>c</mml:mi><mml:msqrt><mml:mrow><mml:mo> </mml:mo><mml:mtext>log</mml:mtext><mml:mo> </mml:mo><mml:mi>n</mml:mi><mml:mo> </mml:mo><mml:mtext>log</mml:mtext><mml:mo> </mml:mo><mml:mo> </mml:mo><mml:mtext>log</mml:mtext><mml:mo> </mml:mo><mml:mi>n</mml:mi></mml:mrow></mml:msqrt></mml:mrow></mml:msup></mml:mrow></mml:math></inline-formula>, for some constant <italic>c</italic>.</p><p>We propose a simpler and direct method that is an LSH for the edit distance. Our method is an extension to the minHash method. We call our method OMH for Order Min Hash, and it can be seen as a correction of the minHash method. The probability of hash collision in the OMH method is the product of two probabilities. The first is the probability to select a <italic>k</italic>-mer from the set of common <italic>k</italic>-mers between the two sequences. This probability is similar to minHash that estimates the Jaccard similarity between the <italic>k</italic>-mer contents of two sequences. However, there is one key difference: the minHash method estimates the Jaccard similarity which treats sequences as sets of <italic>k</italic>-mers, and the number of occurrences of each <italic>k</italic>-mer in the sequences is ignored, whereas OMH estimates the <italic>weighted Jaccard</italic>, where the number of occurrences of a <italic>k</italic>-mer in a sequence is significant, i.e. the weighted Jaccard works with multi-sets. The second probability is the likelihood that the common <italic>k</italic>-mers appear in the same relative order in the two sequences. Therefore, OMH is sensitive not only to the <italic>k</italic>-mer content of the sequences but also to the order of the <italic>k</italic>-mers in the sequences.</p><p>The sketch proposed for OMH is only slightly bigger than the sketch for minHash while maintaining significantly more information about the similarity of two sequences. In addition to providing an estimate for the edit distance between two sequences, it also provides an estimate of the <italic>k</italic>-mer content similarity (the weighted Jaccard) and how similar the relative order is between the common <italic>k</italic>-mers of the two sequences.</p><p>Section 2 summarizes the notation used though out and main results. Detailed proofs of the results are given in Section 3. Section 4 discusses some practical consideration on the implementation of the sketches.</p></sec><sec><title>2 Main results</title><sec><title>2.1 Concepts and definitions</title><p><italic>Similarity and dissimilarity</italic>. A <italic>dissimilarity</italic> is a function <inline-formula id="IE8"><mml:math id="IM8"><mml:mrow><mml:mi>d</mml:mi><mml:mo>:</mml:mo><mml:mi mathvariant="script">U</mml:mi><mml:mo>×</mml:mo><mml:mi mathvariant="script">U</mml:mi><mml:mo>→</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula> that indicates the distance between two elements in the universe <inline-formula id="IE9"><mml:math id="IM9"><mml:mi mathvariant="script">U</mml:mi></mml:math></inline-formula>. <italic>d</italic> satisfies the triangle inequality and <inline-formula id="IE10"><mml:math id="IM10"><mml:mrow><mml:mi>d</mml:mi><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>0</mml:mn></mml:mrow></mml:math></inline-formula> means that <italic>x </italic>= <italic> y</italic>. In other words, a dissimilarity is a normalized distance. A <italic>similarity</italic> is a function <inline-formula id="IE11"><mml:math id="IM11"><mml:mrow><mml:mi>s</mml:mi><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:mrow></mml:math></inline-formula> such that <inline-formula id="IE12"><mml:math id="IM12"><mml:mrow><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:mi>s</mml:mi></mml:mrow></mml:math></inline-formula> is a dissimilarity. Hence, a dissimilarity defines a similarity and vice versa. We will therefore use either of the terms ‘edit dissimilarity’ or ‘edit similarity’.</p><p>Given two strings <inline-formula id="IE13"><mml:math id="IM13"><mml:mrow><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>∈</mml:mo><mml:msup><mml:mrow><mml:mo>Σ</mml:mo></mml:mrow><mml:mi>n</mml:mi></mml:msup></mml:mrow></mml:math></inline-formula> of length <italic>n</italic> (where Σ is the alphabet of size <inline-formula id="IE14"><mml:math id="IM14"><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>), the Hamming dissimilarity <inline-formula id="IE15"><mml:math id="IM15"><mml:mrow><mml:msub><mml:mrow><mml:mi mathvariant="normal">H</mml:mi></mml:mrow><mml:mi mathvariant="normal">d</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> is the number of indices at which <italic>S</italic><sub>1</sub> and <italic>S</italic><sub>2</sub> differ divided by <italic>n</italic>: <inline-formula id="IE16"><mml:math id="IM16"><mml:mrow><mml:msub><mml:mrow><mml:mi mathvariant="normal">H</mml:mi></mml:mrow><mml:mi mathvariant="normal">d</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mo> | </mml:mo><mml:mo stretchy="true">{</mml:mo><mml:mi>i</mml:mi><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:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo stretchy="true">]</mml:mo><mml:mo>≠</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><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:mi>n</mml:mi></mml:mrow></mml:math></inline-formula> (<inline-formula id="IE17"><mml:math id="IM17"><mml:mrow><mml:mo stretchy="true">[</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula> denotes the set <inline-formula id="IE18"><mml:math id="IM18"><mml:mrow><mml:mo stretchy="true">{</mml:mo><mml:mn>0</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>1</mml:mn><mml:mo stretchy="true">}</mml:mo></mml:mrow></mml:math></inline-formula>). The edit dissimilarity <inline-formula id="IE19"><mml:math id="IM19"><mml:mrow><mml:msub><mml:mrow><mml:mi mathvariant="normal">E</mml:mi></mml:mrow><mml:mi mathvariant="normal">d</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> (a.k.a. normalized edit distance) is the minimum number of indels (short for insertion or deletion) and mismatches necessary to transform <italic>S</italic><sub>1</sub> into <italic>S</italic><sub>2</sub>, divided by <italic>n</italic>. Given two sets <italic>A</italic> and <italic>B</italic>, the Jaccard similarity is <inline-formula id="IE20"><mml:math id="IM20"><mml:mrow><mml:mi mathvariant="normal">J</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi>A</mml:mi><mml:mo>,</mml:mo><mml:mi>B</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mo> | </mml:mo><mml:mi>A</mml:mi><mml:mo>∩</mml:mo><mml:mi>B</mml:mi><mml:mo> | </mml:mo><mml:mo>/</mml:mo><mml:mo> | </mml:mo><mml:mi>A</mml:mi><mml:mo>∪</mml:mo><mml:mi>B</mml:mi><mml:mo> | </mml:mo></mml:mrow></mml:math></inline-formula>.</p><p><italic>Gapped LSH</italic>. Let <inline-formula id="IE21"><mml:math id="IM21"><mml:mi mathvariant="script">H</mml:mi></mml:math></inline-formula> be a set of hash functions defined on a set <inline-formula id="IE22"><mml:math id="IM22"><mml:mi mathvariant="script">U</mml:mi></mml:math></inline-formula> (the universe). A probability distribution on the set <inline-formula id="IE23"><mml:math id="IM23"><mml:mi mathvariant="script">H</mml:mi></mml:math></inline-formula> is called <inline-formula id="IE24"><mml:math id="IM24"><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula><italic>-sensitive</italic> for the similarity <italic>s</italic> when
<disp-formula id="E1"><label>(1)</label><mml:math id="M1"><mml:mrow><mml:mi>s</mml:mi><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:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>⇒</mml:mo><mml:munder><mml:mrow><mml:mi>Pr</mml:mi></mml:mrow><mml:mrow><mml:mi>h</mml:mi><mml:mo>∈</mml:mo><mml:mi mathvariant="script">H</mml:mi></mml:mrow></mml:munder><mml:mo stretchy="true">[</mml:mo><mml:mi>h</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mi>h</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi>y</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">]</mml:mo><mml:mo>≥</mml:mo><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula><disp-formula id="E2"><label>(2)</label><mml:math id="M2"><mml:mrow><mml:mi>s</mml:mi><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:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>⇒</mml:mo><mml:munder><mml:mrow><mml:mi>Pr</mml:mi></mml:mrow><mml:mrow><mml:mi>h</mml:mi><mml:mo>∈</mml:mo><mml:mi mathvariant="script">H</mml:mi></mml:mrow></mml:munder><mml:mo stretchy="true">[</mml:mo><mml:mi>h</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mi>h</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi>y</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">]</mml:mo><mml:mo>≤</mml:mo><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula>where <inline-formula id="IE25"><mml:math id="IM25"><mml:mrow><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>≥</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE26"><mml:math id="IM26"><mml:mrow><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>≥</mml:mo><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:math></inline-formula>. A similarity admits a <italic>gapped LSH</italic> scheme if there exists a distribution on a set of hash functions that is <inline-formula id="IE27"><mml:math id="IM27"><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>-sensitive. In the definition above, the probability is taken over the choice of the hash function in <inline-formula id="IE28"><mml:math id="IM28"><mml:mi mathvariant="script">H</mml:mi></mml:math></inline-formula> and the implications hold for any choice of <italic>x</italic> and <inline-formula id="IE29"><mml:math id="IM29"><mml:mrow><mml:mi>y</mml:mi><mml:mo>∈</mml:mo><mml:mi mathvariant="script">U</mml:mi></mml:mrow></mml:math></inline-formula>. In a gapped LSH, the probability of a hash collision is increased (<inline-formula id="IE30"><mml:math id="IM30"><mml:mrow><mml:mo>≥</mml:mo><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub></mml:mrow></mml:math></inline-formula>) between similar elements, and less likely (<inline-formula id="IE31"><mml:math id="IM31"><mml:mrow><mml:mo>≤</mml:mo><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:math></inline-formula>) for dissimilar elements.</p><p>In the following, the probabilities are always taken over the choice of the hashing function, even though we may omit the ‘<inline-formula id="IE32"><mml:math id="IM32"><mml:mrow><mml:mi>h</mml:mi><mml:mo>∈</mml:mo><mml:mi mathvariant="script">H</mml:mi></mml:mrow></mml:math></inline-formula>’ subscript.</p><p><italic>LSH</italic>. An LSH for a similarity is a family of hash functions that is <inline-formula id="IE33"><mml:math id="IM33"><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mi>r</mml:mi><mml:mo>,</mml:mo><mml:mi>r</mml:mi><mml:mo>,</mml:mo><mml:mi>r</mml:mi><mml:mo>,</mml:mo><mml:mi>r</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>-sensitive for any <inline-formula id="IE34"><mml:math id="IM34"><mml:mrow><mml:mi>r</mml:mi><mml:mo>∈</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>. Equivalently, the family of hash functions satisfies <inline-formula id="IE35"><mml:math id="IM35"><mml:mrow><mml:mi>Pr</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mi>h</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mi>h</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi>y</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">]</mml:mo><mml:mo>=</mml:mo><mml:mi>s</mml:mi><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>. In practice a gapped LSH is typically used to put elements into a hash table where there is high likelihood of a collision, whereas a full LSH can be used as a direct estimator of the underlying measurement.</p><p><italic>minHash sketch</italic>. Let the universe <inline-formula id="IE36"><mml:math id="IM36"><mml:mi mathvariant="script">U</mml:mi></mml:math></inline-formula> be a family of sets on the ground set <italic>X</italic> (i.e. <inline-formula id="IE37"><mml:math id="IM37"><mml:mrow><mml:mi mathvariant="script">U</mml:mi><mml:mo>⊂</mml:mo><mml:mi mathvariant="script">P</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi>X</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>). The minHash LSH for the Jaccard similarity is defined as the uniform distribution on the set <inline-formula id="IE38"><mml:math id="IM38"><mml:mrow><mml:msub><mml:mrow><mml:mi mathvariant="script">H</mml:mi></mml:mrow><mml:mrow><mml:mi>min</mml:mi></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:mo stretchy="true">{</mml:mo><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mo>π</mml:mo></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>A</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:msub><mml:mrow><mml:mrow><mml:mi>min</mml:mi></mml:mrow></mml:mrow><mml:mrow><mml:mi>x</mml:mi><mml:mo>∈</mml:mo><mml:mi>A</mml:mi></mml:mrow></mml:msub><mml:mo>π</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo> | </mml:mo><mml:mo>π</mml:mo><mml:mo> </mml:mo><mml:mtext>is</mml:mtext><mml:mo> </mml:mo><mml:mi mathvariant="normal">a</mml:mi><mml:mo> </mml:mo><mml:mtext>permutation</mml:mtext><mml:mo> </mml:mo><mml:mtext>of</mml:mtext><mml:mo> </mml:mo><mml:mi mathvariant="normal">X</mml:mi><mml:mo stretchy="true">}</mml:mo></mml:mrow></mml:math></inline-formula>. That is, the hash function selects the smallest element of the set <italic>A</italic> according to some ordering <italic>π</italic> of the elements of the ground set <italic>X</italic>. This family of hash functions is <inline-formula id="IE39"><mml:math id="IM39"><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mi>s</mml:mi><mml:mo>,</mml:mo><mml:mi>s</mml:mi><mml:mo>,</mml:mo><mml:mi>s</mml:mi><mml:mo>,</mml:mo><mml:mi>s</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>-sensitive for any value of <inline-formula id="IE40"><mml:math id="IM40"><mml:mrow><mml:mi>s</mml:mi><mml:mo>∈</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>, or equivalently <inline-formula id="IE41"><mml:math id="IM41"><mml:mrow><mml:mi>Pr</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mi>h</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi>A</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mi>h</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi>B</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">]</mml:mo><mml:mo>=</mml:mo><mml:mi mathvariant="normal">J</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi>A</mml:mi><mml:mo>,</mml:mo><mml:mi>B</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>.</p><p><italic>LSH for Hamming similarity</italic>. The Hamming similarity between two sequences with same length <italic>n</italic> is the proportion of positions which are equal: <inline-formula id="IE42"><mml:math id="IM42"><mml:mrow><mml:msub><mml:mrow><mml:mi mathvariant="normal">H</mml:mi></mml:mrow><mml:mi mathvariant="normal">s</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mo> | </mml:mo><mml:mo stretchy="true">{</mml:mo><mml:mi>i</mml:mi><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:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo stretchy="true">]</mml:mo><mml:mo>=</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><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:mi>n</mml:mi></mml:mrow></mml:math></inline-formula>. For the Hamming similarity, the uniform distribution on <inline-formula id="IE43"><mml:math id="IM43"><mml:mrow><mml:mi mathvariant="script">H</mml:mi><mml:mo>=</mml:mo><mml:mo stretchy="true">{</mml:mo><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mi>i</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>S</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mi>S</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>i</mml:mi><mml:mo>∈</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="true">]</mml:mo><mml:mo stretchy="true">}</mml:mo></mml:mrow></mml:math></inline-formula> satisfies <inline-formula id="IE44"><mml:math id="IM44"><mml:mrow><mml:mi>Pr</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mi>h</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mi>h</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">]</mml:mo><mml:mo>=</mml:mo><mml:msub><mml:mrow><mml:mi mathvariant="normal">H</mml:mi></mml:mrow><mml:mi mathvariant="normal">s</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>.</p><p><italic>String k-mer set</italic>. For a sequence <italic>S</italic>, the set of its constituent <italic>k</italic>-mers is <inline-formula id="IE45"><mml:math id="IM45"><mml:mrow><mml:msub><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi></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 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 stretchy="true">]</mml:mo><mml:mo> | </mml:mo><mml:mi>i</mml:mi><mml:mo>∈</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mo> | </mml:mo><mml:mi>S</mml:mi><mml:mo> | </mml:mo><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:mo stretchy="true">}</mml:mo></mml:mrow></mml:math></inline-formula>, where <inline-formula id="IE46"><mml:math id="IM46"><mml:mrow><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 stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula> is the substring of length <italic>k</italic> starting at index <italic>i</italic>. By extension, the Jaccard similarity between two sequences is the Jaccard similarity between their <italic>k</italic>-mer sets: <inline-formula id="IE47"><mml:math id="IM47"><mml:mrow><mml:mi mathvariant="normal">J</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mi mathvariant="normal">J</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>.</p><p><italic>Weighted Jaccard</italic>. The weighted Jaccard similarity on multi-sets (or weighted sets) is defined similarly to the Jaccard similarity on sets, where the intersection and union take the multiplicity of the elements into account. More precisely, a multi-set <italic>A</italic> is defined by an index function <inline-formula id="IE48"><mml:math id="IM48"><mml:mrow><mml:msub><mml:mrow><mml:mo>χ</mml:mo></mml:mrow><mml:mi>A</mml:mi></mml:msub><mml:mo>:</mml:mo><mml:mi mathvariant="script">U</mml:mi><mml:mo>→</mml:mo><mml:mi mathvariant="double-struck">N</mml:mi></mml:mrow></mml:math></inline-formula>, where <inline-formula id="IE49"><mml:math id="IM49"><mml:mrow><mml:msub><mml:mrow><mml:mo>χ</mml:mo></mml:mrow><mml:mi>A</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> gives the multiplicity of <italic>x</italic> in <italic>A</italic> (zero if not present in <italic>A</italic>). The index function of the intersection of two multi-sets is the minimum of the index functions, and for the union it is the maximum. Then, the weighted Jaccard is defined by
<disp-formula id="E3"><mml:math id="M3"><mml:mrow><mml:msup><mml:mrow><mml:mi mathvariant="normal">J</mml:mi></mml:mrow><mml:mi mathvariant="normal">w</mml:mi></mml:msup><mml:mo stretchy="true">(</mml:mo><mml:mi>A</mml:mi><mml:mo>,</mml:mo><mml:mi>B</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mfrac><mml:mrow><mml:munder><mml:mo>∑</mml:mo><mml:mrow><mml:mi>x</mml:mi><mml:mo>∈</mml:mo><mml:mi mathvariant="script">U</mml:mi></mml:mrow></mml:munder><mml:mrow><mml:mi>min</mml:mi></mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mo>χ</mml:mo></mml:mrow><mml:mi>A</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mo>χ</mml:mo></mml:mrow><mml:mi>B</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mrow><mml:munder><mml:mo>∑</mml:mo><mml:mrow><mml:mi>x</mml:mi><mml:mo>∈</mml:mo><mml:mi mathvariant="script">U</mml:mi></mml:mrow></mml:munder><mml:mrow><mml:mi>max</mml:mi></mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mo>χ</mml:mo></mml:mrow><mml:mi>A</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mo>χ</mml:mo></mml:mrow><mml:mi>B</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mfrac><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula>This is a direct extension to the set definitions, where the index function takes values in {0, 1}.</p></sec><sec><title>2.2 Jaccard and Hamming similarities differ from edit similarity</title><p>Similarly to the definition of the LSH, we say that a similarity <italic>f</italic><sub>1</sub> is a <inline-formula id="IE50"><mml:math id="IM50"><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>t</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>t</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>-proxy for the similarity <italic>f</italic><sub>2</sub> if
<disp-formula id="E4"><label>(3)</label><mml:math id="M4"><mml:mrow><mml:msub><mml:mrow><mml:mi>f</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><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:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>⇒</mml:mo><mml:msub><mml:mrow><mml:mi>f</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><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:msub><mml:mrow><mml:mi>t</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub></mml:mrow></mml:math></disp-formula><disp-formula id="E5"><label>(4)</label><mml:math id="M5"><mml:mrow><mml:msub><mml:mrow><mml:mi>f</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><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:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>⇒</mml:mo><mml:msub><mml:mrow><mml:mi>f</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><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:msub><mml:mrow><mml:mi>t</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:math></disp-formula>That is high similarity for <italic>f</italic><sub>1</sub> implies high similarity for <italic>f</italic><sub>2</sub>, and the converse. Because of the similar structure between the definitions of sensitivity and proxy, if <italic>f</italic><sub>1</sub> is not a proxy for <italic>f</italic><sub>2</sub> (for any non-trivial choice of parameters <inline-formula id="IE51"><mml:math id="IM51"><mml:mrow><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>t</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>t</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:math></inline-formula>), then an LSH for <italic>f</italic><sub>1</sub> is not an LSH for <italic>f</italic><sub>2</sub>.</p><p>We show here that neither the Hamming similarity nor the Jaccard similarity is a good proxy for the edit dissimilarity. More precisely, only one of the implications above is satisfied.</p><p><italic>Jaccard similarity differs from edit similarity</italic>. A low Jaccard similarity does imply a low edit similarity (<xref ref-type="disp-formula" rid="E5">Equation 4</xref>). On the other hand, consider the sequence <inline-formula id="IE52"><mml:math id="IM52"><mml:mrow><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mn>0</mml:mn><mml:mo>…</mml:mo><mml:mn>01</mml:mn><mml:mo>…</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula> that has <italic>n</italic> − <italic>k</italic> 0s followed by <italic>k</italic> 1s, and <italic>S</italic><sub>2</sub> with <italic>k</italic> 0s followed by <italic>n</italic> − <italic>k</italic> 1s (<italic>k</italic> fixed, <italic>n</italic> arbitrarily large). The <italic>k</italic>-mer sets of <italic>S</italic><sub>1</sub> and <italic>S</italic><sub>2</sub> are identical, hence <inline-formula id="IE53"><mml:math id="IM53"><mml:mrow><mml:mi mathvariant="normal">J</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula>, while the edit similarity is <inline-formula id="IE54"><mml:math id="IM54"><mml:mrow><mml:mo>≤</mml:mo><mml:mn>2</mml:mn><mml:mi>k</mml:mi><mml:mo>/</mml:mo><mml:mi>n</mml:mi></mml:mrow></mml:math></inline-formula>. These sequences are indistinguishable according to the Jaccard similarity while having arbitrarily small edit similarity (<xref ref-type="disp-formula" rid="E4">Equation 3</xref> not satisfied).</p><p><italic>Weighted Jaccard similarity differs from edit similarity</italic>. Consider two de Bruijn sequences: sequences of length <italic>σ<sup>k</sup></italic> containing every <italic>k</italic>-mer exactly once (<xref rid="btz354-B31" ref-type="bibr">van Aardenne-Ehrenfest and de Bruijn, 1951</xref>). There is a very, very large number of such sequences [<inline-formula id="IE55"><mml:math id="IM55"><mml:mrow><mml:msup><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mo>σ</mml:mo><mml:mo>!</mml:mo><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mrow><mml:msup><mml:mrow><mml:mo>σ</mml:mo></mml:mrow><mml:mrow><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup></mml:mrow></mml:msup><mml:mo>/</mml:mo><mml:msup><mml:mrow><mml:mo>σ</mml:mo></mml:mrow><mml:mi>n</mml:mi></mml:msup></mml:mrow></mml:math></inline-formula>], and although any two such sequences have exactly the same <italic>k</italic>-mer content, they might otherwise have a very low edit similarity. Both the Jaccard and weighted Jaccard similarities fail to distinguish between de Bruijn sequences, regardless of their mutual edit dissimilarity.</p><p>For example, the two sequences <monospace>1111011001010000111</monospace> and <monospace>0000101001111011000</monospace> of length 19 each contain exactly the 16 possible 4-mers; hence, their Jaccard and weighted Jaccard similarities are 1. Their edit similarity is only <inline-formula id="IE56"><mml:math id="IM56"><mml:mrow><mml:mo>≈</mml:mo><mml:mn>0.37</mml:mn></mml:mrow></mml:math></inline-formula>. By comparison, two random binary sequences of length 19 have an average edit similarity of <inline-formula id="IE57"><mml:math id="IM57"><mml:mrow><mml:mo>≈</mml:mo><mml:mn>0.62</mml:mn></mml:mrow></mml:math></inline-formula> and an average Jaccard similarity of <inline-formula id="IE58"><mml:math id="IM58"><mml:mrow><mml:mo>≈</mml:mo><mml:mn>0.36</mml:mn></mml:mrow></mml:math></inline-formula>. In other words, these two de Bruijn sequences are much more dissimilar than two random sequences despite having a perfect Jaccard similarity.</p><p>More generally, both Jaccard and weighted Jaccard similarities treat sequences as bags of <italic>k</italic>-mers. The information on relative order of these <italic>k</italic>-mers within the sequence is ignored, although it is of great importance for the edit similarity. In contrast, an OMH sketch does retain some information on the order of the <italic>k</italic>-mers in the original sequence. In the case of the two de Bruijn sequences above, the proportion of pairs of <italic>k</italic>-mers that are in the same relative order in the two sequences is 0.4. The expected similarity between the OMH sketches of these sequences is also equal to 0.4.</p><p><italic>Hamming similarity differs from edit similarity</italic>. A high Hamming similarity does imply a high edit similarity (<xref ref-type="disp-formula" rid="E4">Equation 3</xref>). The opposite is not true however. Consider the sequences of length <italic>n</italic>, <inline-formula id="IE59"><mml:math id="IM59"><mml:mrow><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mn>0101</mml:mn><mml:mo>…</mml:mo><mml:mn>01</mml:mn></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE60"><mml:math id="IM60"><mml:mrow><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mn>1010</mml:mn><mml:mo>…</mml:mo><mml:mn>10</mml:mn></mml:mrow></mml:math></inline-formula>. These sequences have a Hamming similarity of 0 and an edit similarity of <inline-formula id="IE61"><mml:math id="IM61"><mml:mrow><mml:mo>≥</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:mn>2</mml:mn><mml:mo>/</mml:mo><mml:mi>n</mml:mi></mml:mrow></mml:math></inline-formula> (two indels). That is, these sequences are as dissimilar as possible according to the Hamming dissimilarity, but an arbitrarily high edit similarity (<xref ref-type="disp-formula" rid="E5">Equation 4</xref> not satisfied).</p><p>The Hamming similarity is very sensitive to the absolute position in the string. A single shift between two sequences has a large impact on the Hamming similarity but only a unit cost for the edit similarity. An OMH sketch on the other hand only contains relative order between <italic>k</italic>-mers and is indifferent to changes in absolute position.</p></sec><sec><title>2.3 LSH for the edit similarity</title><p>An LSH for the edit similarity must be sensitive to the <italic>k</italic>-mer content of the strings and the relative order of these <italic>k</italic>-mers, but relatively insensitive to the absolute position of the <italic>k</italic>-mers in the string. This motivates the definition below. Similarly to the minHash, <italic>k</italic>-mers are selected at random by using a permutation on the <italic>k</italic>-mers. Additionally, to preserve information about relative order, <inline-formula id="IE62"><mml:math id="IM62"><mml:mi>ℓ</mml:mi></mml:math></inline-formula><italic>k</italic>-mers are selected at once and recorded in the order they appear in the sequence (rather than the order defined by the permutation).</p><p>Additionally, the method must handle repeated <italic>k</italic>-mers. Two copies of the same <italic>k</italic>-mer occur at different positions in the sequence, and it is important for the relative ordering between <italic>k</italic>-mers to distinguish between these two copies. We make <italic>k</italic>-mers unique by appending to them their ‘occurrence number’.</p><p>More precisely, for a string <italic>S</italic> of length <inline-formula id="IE63"><mml:math id="IM63"><mml:mrow><mml:mo> | </mml:mo><mml:mi>S</mml:mi><mml:mo> | </mml:mo><mml:mo>=</mml:mo><mml:mi>n</mml:mi></mml:mrow></mml:math></inline-formula>, consider the set <inline-formula id="IE64"><mml:math id="IM64"><mml:mrow><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></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> of the pairs of the <italic>k</italic>-mers and their occurrence number. If there are <italic>x</italic> copies of <italic>m</italic> in sequence <italic>S</italic>, then the <italic>x</italic> pairs <inline-formula id="IE65"><mml:math id="IM65"><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo>,</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:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo>,</mml:mo><mml:mi>x</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> are in the set <inline-formula id="IE66"><mml:math id="IM66"><mml:mrow><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></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>, and the occurrence number denotes the number of other copies of <italic>m</italic> that are in the sequence <italic>S</italic> to the left of this particular copy. That is, if <italic>m</italic> is the <italic>k</italic>-mer at position <italic>i</italic> in <italic>S</italic> (i.e. <inline-formula id="IE67"><mml:math id="IM67"><mml:mrow><mml:mi>m</mml:mi><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>k</mml:mi><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>), then its occurrence number is <inline-formula id="IE68"><mml:math id="IM68"><mml:mrow><mml:mo> | </mml:mo><mml:mo stretchy="true">{</mml:mo><mml:mi>j</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>S</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mi>j</mml:mi><mml:mo>:</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="true">]</mml:mo><mml:mo>=</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">}</mml:mo><mml:mo> | </mml:mo></mml:mrow></mml:math></inline-formula>. This set is the ‘multi-set’ of the <italic>k</italic>-mer content of string <italic>S</italic>, or the ‘weighted set’ of <italic>k</italic>-mers where the number of occurrences is the weight of the <italic>k</italic>-mer (hence the <italic>w</italic> superscript). We call a pair (<italic>m</italic>, <italic>i</italic>) of a <italic>k</italic>-mer and an occurrence number a ‘uniquified’ <italic>k</italic>-mer.</p><p>A permutation <italic>π</italic> of <inline-formula id="IE69"><mml:math id="IM69"><mml:mrow><mml:msup><mml:mrow><mml:mo>Σ</mml:mo></mml:mrow><mml:mi>k</mml:mi></mml:msup><mml:mo>×</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula> defines two functions <inline-formula id="IE70"><mml:math id="IM70"><mml:mrow><mml:msubsup><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow><mml:mi>w</mml:mi></mml:msubsup></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE71"><mml:math id="IM71"><mml:mrow><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula>. <inline-formula id="IE72"><mml:math id="IM72"><mml:mrow><mml:msubsup><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow><mml:mi>w</mml:mi></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 stretchy="true">(</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>m</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>o</mml:mi></mml:mrow><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 stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>m</mml:mi></mml:mrow><mml:mi>ℓ</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>o</mml:mi></mml:mrow><mml:mi>ℓ</mml:mi></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> is a vector of length <inline-formula id="IE73"><mml:math id="IM73"><mml:mi>ℓ</mml:mi></mml:math></inline-formula> of elements of <inline-formula id="IE74"><mml:math id="IM74"><mml:mrow><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></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> such that:
<list list-type="bullet"><list-item><p>the pairs (<italic>m<sub>i</sub></italic>, <italic>o<sub>i</sub></italic>) are the <inline-formula id="IE75"><mml:math id="IM75"><mml:mi>ℓ</mml:mi></mml:math></inline-formula> smallest elements of <inline-formula id="IE76"><mml:math id="IM76"><mml:mrow><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></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> according to <italic>π</italic>,</p></list-item><list-item><p>the pairs are listed in the vector in the order in which the <italic>k</italic>-mer appears in the sequence <italic>S</italic>. That is, if <italic>i</italic> < <italic>j</italic>, <inline-formula id="IE77"><mml:math id="IM77"><mml:mrow><mml:msub><mml:mrow><mml:mi>m</mml:mi></mml:mrow><mml:mi>i</mml:mi></mml:msub><mml:mo>=</mml:mo><mml:mi>S</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mi>x</mml:mi><mml:mo>:</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE78"><mml:math id="IM78"><mml:mrow><mml:msub><mml:mrow><mml:mi>m</mml:mi></mml:mrow><mml:mi>j</mml:mi></mml:msub><mml:mo>=</mml:mo><mml:mi>S</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mi>y</mml:mi><mml:mo>:</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>, then <italic>x</italic> < <italic>y</italic>.</p></list-item></list></p><p>The vector <inline-formula id="IE79"><mml:math id="IM79"><mml:mrow><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></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 stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>m</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>m</mml:mi></mml:mrow><mml:mi>ℓ</mml:mi></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> contains only the <italic>k</italic>-mers from <inline-formula id="IE80"><mml:math id="IM80"><mml:mrow><mml:msubsup><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow><mml:mi>w</mml:mi></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>, in the same order. The OMH method is defined as the uniform distribution on the set of hash functions <inline-formula id="IE81"><mml:math id="IM81"><mml:mrow><mml:msub><mml:mrow><mml:mi mathvariant="script">H</mml:mi></mml:mrow><mml:mrow><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>ℓ</mml:mi></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:mo stretchy="true">{</mml:mo><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo> | </mml:mo><mml:mo>π</mml:mo><mml:mo> </mml:mo><mml:mi mathvariant="normal">a</mml:mi><mml:mo> </mml:mo><mml:mtext>permutation</mml:mtext><mml:mo> </mml:mo><mml:mtext>of</mml:mtext><mml:mo> </mml:mo><mml:msup><mml:mrow><mml:mo>Σ</mml:mo></mml:mrow><mml:mi>k</mml:mi></mml:msup><mml:mo>×</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="true">]</mml:mo><mml:mo stretchy="true">}</mml:mo></mml:mrow></mml:math></inline-formula>.</p><p>For extreme cases, where <inline-formula id="IE82"><mml:math id="IM82"><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>=</mml:mo><mml:mi>n</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>, the vector contains overlapping <italic>k</italic>-mers that cover the entire sequence <italic>S</italic>. In that case, equality of the hash values implies strict equality of the sequences.</p><p>At the other extreme, where <inline-formula id="IE83"><mml:math id="IM83"><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula>, the vectors contain only one <italic>k</italic>-mer and no relative order information is preserved. In that case, only the <italic>k</italic>-mer content similarity between <italic>S</italic><sub>1</sub> and <italic>S</italic><sub>2</sub> matters.</p><p>The weighted Jaccard similarity <inline-formula id="IE84"><mml:math id="IM84"><mml:mrow><mml:msup><mml:mrow><mml:mi mathvariant="normal">J</mml:mi></mml:mrow><mml:mi mathvariant="normal">w</mml:mi></mml:msup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> of two sequences is the weighted Jaccard of their <italic>k</italic>-mer content (seen as multi-set). Because <italic>k</italic>-mers were made unique by their occurrence number in <inline-formula id="IE85"><mml:math id="IM85"><mml:mrow><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></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>, the weighted Jaccard similarity is equivalently defined as <inline-formula id="IE86"><mml:math id="IM86"><mml:mrow><mml:msup><mml:mrow><mml:mi mathvariant="normal">J</mml:mi></mml:mrow><mml:mi mathvariant="normal">w</mml:mi></mml:msup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mi mathvariant="normal">J</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>,</mml:mo><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>.</p><p><statement id="mthst1"><p><sc>Theorem</sc> 1. <italic>When</italic><inline-formula id="IE87"><mml:math id="IM87"><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula><italic>, OMH is an LSH for the weighted Jaccard similarity</italic>:
<disp-formula id="E6"><label>(5)</label><mml:math id="M6"><mml:mrow><mml:mi>Pr</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">]</mml:mo><mml:mo>=</mml:mo><mml:msup><mml:mrow><mml:mi mathvariant="normal">J</mml:mi></mml:mrow><mml:mi mathvariant="normal">w</mml:mi></mml:msup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p><sc>Proof</sc>. This proof is similar to that of minHash and the Jaccard similarity (<xref rid="btz354-B6" ref-type="bibr">Broder, 1997</xref>). Because every uniquified <italic>k</italic>-mer in <inline-formula id="IE88"><mml:math id="IM88"><mml:mrow><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>∪</mml:mo><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> has the same probability of being selected, the probability of having a hash collision is the same as selected a <italic>k</italic>-mer from the intersection where the probability of picking a <italic>k</italic>-mer is weighted by its maximum occurrence number. □</p></statement></p><p>As we shall see in Section 4.4, the weighted Jaccard similarity contains approximately the same information as the Jaccard similarity with respect to the edit similarity.</p><p>For the general case <inline-formula id="IE89"><mml:math id="IM89"><mml:mrow><mml:mn>1</mml:mn><mml:mo><</mml:mo><mml:mi>ℓ</mml:mi><mml:mo><</mml:mo><mml:mi>n</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>, we shall prove the following theorem in Section 3 that OMH is a gapped LSH for the edit dissimilarity.</p><p><statement id="mthst2"><p><sc>Theorem</sc> 2. <italic>For any</italic><inline-formula id="IE90"><mml:math id="IM90"><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>∈</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mn>2</mml:mn><mml:mo>,</mml:mo><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula><italic>and any</italic><inline-formula id="IE91"><mml:math id="IM91"><mml:mrow><mml:mn>1</mml:mn><mml:mo>></mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>≥</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>></mml:mo><mml:mn>0</mml:mn></mml:mrow></mml:math></inline-formula><italic>, there exist functions</italic><inline-formula id="IE92"><mml:math id="IM92"><mml:mrow><mml:msubsup><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mrow><mml:mi>n</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>ℓ</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:mo>·</mml:mo><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula><italic>and</italic><inline-formula id="IE93"><mml:math id="IM93"><mml:mrow><mml:msubsup><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mrow><mml:mi>n</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>ℓ</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:mo>·</mml:mo><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula><italic>such that OMH is</italic><inline-formula id="IE94"><mml:math id="IM94"><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msubsup><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mrow><mml:mi>n</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>ℓ</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>,</mml:mo><mml:msubsup><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mrow><mml:mi>n</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>ℓ</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:math></inline-formula><italic>-sensitive for the edit distance</italic>.</p><p>The actual functions <italic>p</italic><sup>1</sup> and <italic>p</italic><sup>2</sup> are explicitly defined in Section 3, but they may not be easily expressed with elementary functions in general.</p></statement></p></sec></sec><sec><title>3 Proofs of main results</title><p>We shall now prove Theorem 2 that OMH is sensitive for the edit similarity by exhibiting the relations between parameters <inline-formula id="IE95"><mml:math id="IM95"><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> that satisfy <xref ref-type="disp-formula" rid="E1">Equations (1)</xref> and <xref ref-type="disp-formula" rid="E2">(2)</xref>. We will break the proof in two lemmas that provide the relations between <italic>s</italic><sub>1</sub>, <italic>p</italic><sub>1</sub> and between <italic>s</italic><sub>2</sub>, <italic>p</italic><sub>2</sub>. In the following, <italic>S</italic><sub>1</sub> and <italic>S</italic><sub>2</sub> are two sequences of length <italic>n</italic>. The number of <italic>k</italic>-mers in each of these sequences is <inline-formula id="IE96"><mml:math id="IM96"><mml:mrow><mml:msub><mml:mrow><mml:mi>n</mml:mi></mml:mrow><mml:mi>k</mml:mi></mml:msub><mml:mo>=</mml:mo><mml:mi>n</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>.</p><p>In the following, we assume that a binomial coefficient <inline-formula id="IE97"><mml:math id="IM97"><mml:mrow><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mi>n</mml:mi></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>k</mml:mi></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:mrow></mml:math></inline-formula> where <italic>n</italic> is negative or null is equal to 0. In these proofs, it means that the probability of choosing elements from the empty set is zero.</p><p><statement id="mthst3"><p><sc>Lemma</sc> 1. <inline-formula id="IE98"><mml:math id="IM98"><mml:mrow><mml:msub><mml:mrow><mml:mi mathvariant="normal">E</mml:mi></mml:mrow><mml:mi mathvariant="normal">s</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>≥</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>⇒</mml:mo><mml:mi>Pr</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">]</mml:mo><mml:mo>≥</mml:mo><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub></mml:mrow></mml:math></inline-formula> when
<disp-formula id="E7"><label>(6)</label><mml:math id="M7"><mml:mrow><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mfrac><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>ℓ</mml:mi></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:msub><mml:mrow><mml:mi>n</mml:mi></mml:mrow><mml:mi>k</mml:mi></mml:msub><mml:mo>+</mml:mo><mml:mi mathvariant="italic">kn</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>ℓ</mml:mi></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:mfrac><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p><sc>Proof</sc>. The situation is similar to the minHash method. Suppose that <inline-formula id="IE99"><mml:math id="IM99"><mml:mrow><mml:msub><mml:mrow><mml:mi mathvariant="normal">E</mml:mi></mml:mrow><mml:mi mathvariant="normal">s</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>≥</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub></mml:mrow></mml:math></inline-formula>, then the edit dissimilarity <inline-formula id="IE100"><mml:math id="IM100"><mml:mrow><mml:msub><mml:mrow><mml:mi mathvariant="normal">E</mml:mi></mml:mrow><mml:mi mathvariant="normal">d</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msub><mml:mrow><mml:mi mathvariant="normal">E</mml:mi></mml:mrow><mml:mi mathvariant="normal">s</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>≤</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub></mml:mrow></mml:math></inline-formula> and the number of mismatches and indels is <inline-formula id="IE101"><mml:math id="IM101"><mml:mrow><mml:mo>≤</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>. Any alignment between <italic>s</italic><sub>1</sub> and <italic>s</italic><sub>2</sub> has at most <inline-formula id="IE102"><mml:math id="IM102"><mml:mrow><mml:mi>n</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> mismatches and indels, because <inline-formula id="IE103"><mml:math id="IM103"><mml:mrow><mml:msub><mml:mrow><mml:mi mathvariant="normal">E</mml:mi></mml:mrow><mml:mi mathvariant="normal">d</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>≤</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub></mml:mrow></mml:math></inline-formula>. Therefore, there are at least <inline-formula id="IE104"><mml:math id="IM104"><mml:mrow><mml:msub><mml:mrow><mml:mi>n</mml:mi></mml:mrow><mml:mi>k</mml:mi></mml:msub><mml:mo>−</mml:mo><mml:mi mathvariant="italic">kn</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula><italic>k</italic>-mers in the aligned bases, as an error (mismatch or indel) affects at most <italic>k</italic> consecutive <italic>k</italic>-mers.</p></statement></p><p>Similarly, the size of the set <inline-formula id="IE105"><mml:math id="IM105"><mml:mrow><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>∪</mml:mo><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> is maximized when all the <italic>k</italic>-mers that are not part of the alignment are different. Then, <inline-formula id="IE106"><mml:math id="IM106"><mml:mrow><mml:mo> | </mml:mo><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>∪</mml:mo><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo> | </mml:mo></mml:mrow></mml:math></inline-formula> is at most <inline-formula id="IE107"><mml:math id="IM107"><mml:mrow><mml:msub><mml:mrow><mml:mi>n</mml:mi></mml:mrow><mml:mi>k</mml:mi></mml:msub><mml:mo>+</mml:mo><mml:mi mathvariant="italic">kn</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>.</p><p>We estimate the probability to have a hash collision from the number of uniquified <italic>k</italic>-mers in the aligned bases. As seen in <xref ref-type="fig" rid="btz354-F1">Figure 1</xref>, it is possible for a <italic>k</italic>-mer <italic>m</italic> with different occurrence numbers to be part of the aligned bases. Any permutation that has <inline-formula id="IE108"><mml:math id="IM108"><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mi>m</mml:mi><mml:mo>,</mml:mo><mml:mn>0</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> in the lowest <inline-formula id="IE109"><mml:math id="IM109"><mml:mi>ℓ</mml:mi></mml:math></inline-formula> uniquified <italic>k</italic>-mers does not lead to a hash collision. Let <italic>x</italic> be the number of <italic>k</italic>-mers in the aligned bases with occurrence number that disagree between <italic>S</italic><sub>1</sub> and <italic>S</italic><sub>2</sub>. Therefore, there are at least <italic>x k</italic>-mers outside of the aligned bases representing at least <inline-formula id="IE110"><mml:math id="IM110"><mml:mrow><mml:mi>x</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> unaligned bases. Given that the edit similarity is <inline-formula id="IE111"><mml:math id="IM111"><mml:mrow><mml:mo>≥</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub></mml:mrow></mml:math></inline-formula>, the number of unaligned bases is at most <inline-formula id="IE112"><mml:math id="IM112"><mml:mrow><mml:mn>2</mml:mn><mml:mi>n</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE113"><mml:math id="IM113"><mml:mrow><mml:mi>x</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:mn>2</mml:mn><mml:mi>n</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>. Consequently, the number of <italic>k</italic>-mers in the aligned bases to choose from is at least the number of <italic>k</italic>-mers in the aligned bases (<inline-formula id="IE114"><mml:math id="IM114"><mml:mrow><mml:msub><mml:mrow><mml:mi>n</mml:mi></mml:mrow><mml:mi>k</mml:mi></mml:msub><mml:mo>−</mml:mo><mml:mi mathvariant="italic">kn</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>) minus the number of <italic>k</italic>-mers with disagreeing occurrence number (<italic>x</italic>) <inline-formula id="IE115"><mml:math id="IM115"><mml:mrow><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>.
</p><fig id="btz354-F1" orientation="portrait" position="float"><label>Fig. 1.</label><caption><p>For an alignment between <italic>S</italic><sub>1</sub> and <italic>S</italic><sub>2</sub>, the gray area represents the aligned bases. A particular <italic>k</italic>-mer <italic>m</italic> is shown with its occurrence numbers. The occurrence number of the matched <italic>k</italic>-mer pairs in the aligned bases may not agree (as in this example). For every such <italic>m</italic> with a mismatch occurrence number in the aligned bases, there must exist an instance of <italic>m</italic> outside the aligned bases [<inline-formula id="IE116"><mml:math id="IM116"><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>m</mml:mi><mml:mo>,</mml:mo><mml:mn>0</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></inline-formula> in <italic>S</italic><sub>1</sub> here]</p></caption><graphic xlink:href="btz354f1"></graphic></fig><p>Every element of <inline-formula id="IE117"><mml:math id="IM117"><mml:mrow><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>∪</mml:mo><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> has an equal probability to be in the lowest <inline-formula id="IE118"><mml:math id="IM118"><mml:mi>ℓ</mml:mi></mml:math></inline-formula> elements according to a permutation <italic>π</italic>; therefore, the probability of having a hash collision is:
<disp-formula id="E8"><label>(7)</label><mml:math id="M8"><mml:mrow><mml:mtable><mml:mtr columnalign="left"><mml:mtd columnalign="left"><mml:mrow><mml:mi>Pr</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">]</mml:mo><mml:mo>≥</mml:mo><mml:mi>Pr</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:msubsup><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:msubsup><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:mtd></mml:mtr><mml:mtr columnalign="left"><mml:mtd columnalign="left"><mml:mrow><mml:mo>≥</mml:mo><mml:mfrac><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>ℓ</mml:mi></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:msub><mml:mrow><mml:mi>n</mml:mi></mml:mrow><mml:mi>k</mml:mi></mml:msub><mml:mo>+</mml:mo><mml:mi mathvariant="italic">kn</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>ℓ</mml:mi></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:mfrac><mml:mo>.</mml:mo></mml:mrow></mml:mtd></mml:mtr></mml:mtable></mml:mrow></mml:math></disp-formula>This defines the relationship between <italic>p</italic><sub>1</sub> and <italic>s</italic><sub>1</sub> as in <xref ref-type="disp-formula" rid="E7">Equation (6)</xref>.</p><p>□</p><p>For the proof of <xref ref-type="disp-formula" rid="E2">Equation (2)</xref>, we will consider its contrapositive
<disp-formula id="E9"><label>(8)</label><mml:math id="M9"><mml:mrow><mml:mi>Pr</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">]</mml:mo><mml:mo>≥</mml:mo><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>⇒</mml:mo><mml:msub><mml:mrow><mml:mi mathvariant="normal">E</mml:mi></mml:mrow><mml:mi mathvariant="normal">s</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>></mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>That is for any two sequences with high probability of having a hash collision, the edit similarity of the sequences must be high.</p><p>To have a high probability of collision between two sketches, the sequences must (i) have a large number of common <italic>k</italic>-mers and (ii) these common <italic>k</italic>-mers should be mostly in the same relative order. The first condition corresponds to the sequences having a large weighted Jaccard similarity.</p><p>The second condition is related to common subsequences (CSs) between sequences of <italic>k</italic>-mers. A ‘common subsequence’ between <inline-formula id="IE119"><mml:math id="IM119"><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>a</mml:mi></mml:mrow><mml:mi>i</mml:mi></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE120"><mml:math id="IM120"><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>b</mml:mi></mml:mrow><mml:mi>i</mml:mi></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> is a sequence of elements that are in both <inline-formula id="IE121"><mml:math id="IM121"><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>a</mml:mi></mml:mrow><mml:mi>i</mml:mi></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE122"><mml:math id="IM122"><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>b</mml:mi></mml:mrow><mml:mi>i</mml:mi></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> and appear in the same order (formally an increasing function <inline-formula id="IE123"><mml:math id="IM123"><mml:mo>φ</mml:mo></mml:math></inline-formula> such that <inline-formula id="IE124"><mml:math id="IM124"><mml:mrow><mml:msub><mml:mrow><mml:mi>a</mml:mi></mml:mrow><mml:mrow><mml:mo>φ</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>i</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:msub><mml:mrow><mml:mi>b</mml:mi></mml:mrow><mml:mrow><mml:mo>φ</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>i</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula>). We emphasize here that the ‘sequences’ considered here are not DNA sequences, but ordered lists of <italic>k</italic>-mers <inline-formula id="IE125"><mml:math id="IM125"><mml:mrow><mml:msub><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>a</mml:mi></mml:mrow><mml:mi>i</mml:mi></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mrow><mml:mi>i</mml:mi><mml:mo>∈</mml:mo><mml:mi mathvariant="double-struck">N</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula>.</p><p>If the sequences <italic>S</italic><sub>1</sub> and <italic>S</italic><sub>2</sub> have a long CS of <italic>k</italic>-mers, then the probability to pick <inline-formula id="IE126"><mml:math id="IM126"><mml:mi>ℓ</mml:mi></mml:math></inline-formula><italic>k</italic>-mers in the same order between the common <italic>k</italic>-mers of <italic>S</italic><sub>1</sub> and <italic>S</italic><sub>2</sub> will be high. In turn, the presence of a long CS of <italic>k</italic>-mers implies a high similarity.</p><p>Considering <xref ref-type="disp-formula" rid="E9">Equation (8)</xref>, we are looking for the lowest similarity (<italic>s</italic><sub>2</sub>) that is achievable given a high probability (<italic>p</italic><sub>2</sub>) of hash collision. This is done in two parts: (i) finding the lowest weighted Jaccard between <italic>S</italic><sub>1</sub> and <italic>S</italic><sub>2</sub> given the high hash collision rate and (ii) constructing a worse case example of having many CSs of <italic>k</italic>-mers while not having any long CS. This second problem is equivalent to finding, for a given <italic>L</italic>, a single sequence with as many as possible increasing subsequences of length <italic>L</italic> (see Lemma 3).</p><p><statement id="mthst4"><p><sc>Lemma</sc> 2. <inline-formula id="IE127"><mml:math id="IM127"><mml:mrow><mml:msub><mml:mrow><mml:mi mathvariant="normal">E</mml:mi></mml:mrow><mml:mi mathvariant="normal">s</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>≤</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>⇒</mml:mo><mml:mi>Pr</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">]</mml:mo><mml:mo>≤</mml:mo><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:math></inline-formula> when
<disp-formula id="E10"><label>(9)</label><mml:math id="M10"><mml:mrow><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mfrac><mml:mrow><mml:msup><mml:mrow><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mfrac><mml:mrow><mml:msub><mml:mrow><mml:mi>n</mml:mi></mml:mrow><mml:mi>k</mml:mi></mml:msub></mml:mrow><mml:mrow><mml:mi>n</mml:mi><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>−</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:mfrac></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:mrow><mml:mi>ℓ</mml:mi></mml:msup><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mi>n</mml:mi><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>−</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>ℓ</mml:mi></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:msub><mml:mrow><mml:mi>n</mml:mi></mml:mrow><mml:mi>k</mml:mi></mml:msub></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>ℓ</mml:mi></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:mfrac><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p><sc>Proof</sc>. We use the notation <inline-formula id="IE128"><mml:math id="IM128"><mml:mrow><mml:mo stretchy="true">{</mml:mo><mml:msubsup><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:mi>S</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">}</mml:mo></mml:mrow></mml:math></inline-formula> for the set of elements in the vector <inline-formula id="IE129"><mml:math id="IM129"><mml:mrow><mml:msubsup><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow><mml:mi>w</mml:mi></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> (in other words, because all the elements are unique by construction, the elements without order).</p></statement></p><p>As mentioned above, we consider the contrapositive state in <xref ref-type="disp-formula" rid="E9">Equation (8)</xref>. We have that
<disp-formula id="E11"><label>(10)</label><mml:math id="M11"><mml:mrow><mml:mtable><mml:mtr columnalign="left"><mml:mtd columnalign="left"><mml:mrow><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo><</mml:mo><mml:mi>Pr</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">]</mml:mo><mml:mo>=</mml:mo></mml:mrow></mml:mtd></mml:mtr><mml:mtr columnalign="left"><mml:mtd columnalign="left"><mml:mrow><mml:mi>Pr</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo> | </mml:mo><mml:mo stretchy="true">{</mml:mo><mml:msubsup><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">}</mml:mo><mml:mo>=</mml:mo><mml:mo stretchy="true">{</mml:mo><mml:msubsup><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">}</mml:mo><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:mtd></mml:mtr><mml:mtr columnalign="left"><mml:mtd columnalign="left"><mml:mrow><mml:mo>·</mml:mo><mml:mi>Pr</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mo stretchy="true">{</mml:mo><mml:msubsup><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">}</mml:mo><mml:mo>=</mml:mo><mml:mo stretchy="true">{</mml:mo><mml:msubsup><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">}</mml:mo><mml:mo stretchy="true">]</mml:mo><mml:mo>.</mml:mo></mml:mrow></mml:mtd></mml:mtr></mml:mtable></mml:mrow></mml:math></disp-formula></p><p>Under the conditional event (<italic>C</italic>) that <inline-formula id="IE130"><mml:math id="IM130"><mml:mrow><mml:mo stretchy="false">{</mml:mo><mml:msubsup><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">}</mml:mo><mml:mo>=</mml:mo><mml:mo stretchy="false">{</mml:mo><mml:msubsup><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">}</mml:mo></mml:mrow></mml:math></inline-formula>, we have <inline-formula id="IE131"><mml:math id="IM131"><mml:mrow><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>⇔</mml:mo><mml:msubsup><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:msubsup><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></inline-formula>. The reverse implication (<inline-formula id="IE132"><mml:math id="IM132"><mml:mo>⇐</mml:mo></mml:math></inline-formula>) is always true as <italic>h</italic> is obtained from <italic>h<sup>w</sup></italic> by using only the <italic>k</italic>-mer in each element. The forward implication (<inline-formula id="IE133"><mml:math id="IM133"><mml:mo>⇒</mml:mo></mml:math></inline-formula>) holds thanks to (<italic>C</italic>). Given that the <italic>k</italic>-mers are listed in order in which they appear in the respective sequences, they are also listed in order of their occurrence number, and because the content in the weighted vectors <italic>h<sup>w</sup></italic> is the same, the equality of the unweighted vectors <italic>h</italic> implies equality of the weighted vectors.</p><p>Let <inline-formula id="IE134"><mml:math id="IM134"><mml:mrow><mml:mi>m</mml:mi><mml:mo>=</mml:mo><mml:mo> | </mml:mo><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>∩</mml:mo><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo> | </mml:mo></mml:mrow></mml:math></inline-formula> be the size of the intersection of the weighted <italic>k</italic>-mer sets. The event (<italic>C</italic>) occurs when the <inline-formula id="IE135"><mml:math id="IM135"><mml:mi>ℓ</mml:mi></mml:math></inline-formula> smallest <italic>k</italic>-mers/occurrence number pairs according to the permutation <italic>π</italic> belong to the intersection <inline-formula id="IE136"><mml:math id="IM136"><mml:mrow><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>∩</mml:mo><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>. Therefore,
<disp-formula id="E12"><label>(11)</label><mml:math id="M12"><mml:mrow><mml:mtable><mml:mtr columnalign="left"><mml:mtd columnalign="left"><mml:mrow><mml:mi>Pr</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mo stretchy="true">{</mml:mo><mml:msubsup><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">}</mml:mo><mml:mo>=</mml:mo><mml:mo stretchy="true">{</mml:mo><mml:msubsup><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">}</mml:mo><mml:mo stretchy="true">]</mml:mo><mml:mo>=</mml:mo><mml:mfrac><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mo> | </mml:mo><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>∩</mml:mo><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo> | </mml:mo></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>ℓ</mml:mi></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mo> | </mml:mo><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>∪</mml:mo><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo> | </mml:mo></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>ℓ</mml:mi></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:mfrac></mml:mrow></mml:mtd></mml:mtr><mml:mtr columnalign="left"><mml:mtd columnalign="left"><mml:mrow><mml:mo>≤</mml:mo><mml:mfrac><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mi>m</mml:mi></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>ℓ</mml:mi></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:msub><mml:mrow><mml:mi>n</mml:mi></mml:mrow><mml:mi>k</mml:mi></mml:msub></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>ℓ</mml:mi></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:mfrac><mml:mo>.</mml:mo></mml:mrow></mml:mtd></mml:mtr></mml:mtable></mml:mrow></mml:math></disp-formula></p><p>Consider now the sequences <inline-formula id="IE137"><mml:math id="IM137"><mml:mrow><mml:msubsup><mml:mrow><mml:mi>M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE138"><mml:math id="IM138"><mml:mrow><mml:msubsup><mml:mrow><mml:mi>M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> of the elements of <inline-formula id="IE139"><mml:math id="IM139"><mml:mrow><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>∩</mml:mo><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> listed in the order in which they occur in <italic>S</italic><sub>1</sub> and <italic>S</italic><sub>2</sub>, respectively. Both of these sequences have length <italic>m</italic>. Then, the event that <inline-formula id="IE140"><mml:math id="IM140"><mml:mrow><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> under the condition (<italic>C</italic>) is equivalent to having the hash function <inline-formula id="IE141"><mml:math id="IM141"><mml:mrow><mml:msubsup><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow><mml:mi>w</mml:mi></mml:msubsup></mml:mrow></mml:math></inline-formula> picking a CS of length <inline-formula id="IE142"><mml:math id="IM142"><mml:mi>ℓ</mml:mi></mml:math></inline-formula> between <inline-formula id="IE143"><mml:math id="IM143"><mml:mrow><mml:msubsup><mml:mrow><mml:mi>M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE144"><mml:math id="IM144"><mml:mrow><mml:msubsup><mml:mrow><mml:mi>M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>. Because the elements of these sequences are never repeated (it is a list of uniquified <italic>k</italic>-mers), the problem of finding CSs between <inline-formula id="IE145"><mml:math id="IM145"><mml:mrow><mml:msubsup><mml:mrow><mml:mi>M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE146"><mml:math id="IM146"><mml:mrow><mml:msubsup><mml:mrow><mml:mi>M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> is identical to finding increasing subsequences (IS) in a sequence of integers of length <italic>m</italic> (<xref rid="btz354-B9" ref-type="bibr">Fredman, 1975</xref>; <xref rid="btz354-B12" ref-type="bibr">Hunt and Szymanski, 1977</xref>).
<disp-formula id="E13"><label>(12)</label><mml:math id="M13"><mml:mrow><mml:mi>Pr</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo> | </mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>C</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">]</mml:mo><mml:mo>≤</mml:mo></mml:mrow><mml:mrow><mml:munder><mml:mrow><mml:mi>max</mml:mi></mml:mrow><mml:mrow><mml:mo>π</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:mrow></mml:munder><mml:mi>Pr</mml:mi><mml:mo stretchy="true">[</mml:mo><mml:mtext>pick</mml:mtext><mml:mo> </mml:mo><mml:mtext>IS</mml:mtext><mml:mo> </mml:mo><mml:mtext>of</mml:mtext><mml:mo> </mml:mo><mml:mtext>length</mml:mtext><mml:mo> </mml:mo><mml:mi>ℓ</mml:mi><mml:mo> </mml:mo><mml:mtext>in</mml:mtext><mml:mo> </mml:mo><mml:mo>π</mml:mo><mml:mo stretchy="true">(</mml:mo><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 stretchy="true">]</mml:mo><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula>where <inline-formula id="IE147"><mml:math id="IM147"><mml:mrow><mml:mo stretchy="true">[</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">]</mml:mo><mml:mo>!</mml:mo></mml:mrow></mml:math></inline-formula> is the set of all permutations of <inline-formula id="IE148"><mml:math id="IM148"><mml:mrow><mml:mo stretchy="true">[</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula>. Together, <xref ref-type="disp-formula" rid="IE10 IE11 IE12 IE13 IE14">Equations (10–12)</xref>, and Lemma 3 imply that the following holds for any choice of sequences <italic>S</italic><sub>1</sub>, <italic>S</italic><sub>2</sub>:
<disp-formula id="E15"><label>(13)</label><mml:math id="M14"><mml:mrow><mml:mtable><mml:mtr columnalign="left"><mml:mtd columnalign="left"><mml:mrow><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo><</mml:mo><mml:munder><mml:mrow><mml:mi>max</mml:mi></mml:mrow><mml:mtable><mml:mtr><mml:mtd><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>≤</mml:mo><mml:mi>m</mml:mi><mml:mo>,</mml:mo></mml:mrow></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mrow><mml:mi>m</mml:mi><mml:mo>≤</mml:mo><mml:msub><mml:mrow><mml:mi>n</mml:mi></mml:mrow><mml:mi>k</mml:mi></mml:msub></mml:mrow></mml:mtd></mml:mtr></mml:mtable></mml:munder><mml:mfrac><mml:mrow><mml:msup><mml:mrow><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mfrac><mml:mi>m</mml:mi><mml:mi>L</mml:mi></mml:mfrac></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:mrow><mml:mi>ℓ</mml:mi></mml:msup><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mi>L</mml:mi></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>ℓ</mml:mi></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mi>m</mml:mi></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>ℓ</mml:mi></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:mfrac><mml:mfrac><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mi>m</mml:mi></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>ℓ</mml:mi></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:msub><mml:mrow><mml:mi>n</mml:mi></mml:mrow><mml:mi>k</mml:mi></mml:msub></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>ℓ</mml:mi></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:mfrac></mml:mrow></mml:mtd></mml:mtr><mml:mtr columnalign="left"><mml:mtd columnalign="left"><mml:mrow><mml:mo><</mml:mo><mml:mfrac><mml:mrow><mml:msup><mml:mrow><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mfrac><mml:mrow><mml:msub><mml:mrow><mml:mi>n</mml:mi></mml:mrow><mml:mi>k</mml:mi></mml:msub></mml:mrow><mml:mi>L</mml:mi></mml:mfrac></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:mrow><mml:mi>ℓ</mml:mi></mml:msup><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mi>L</mml:mi></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>ℓ</mml:mi></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:msub><mml:mrow><mml:mi>n</mml:mi></mml:mrow><mml:mi>k</mml:mi></mml:msub></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>ℓ</mml:mi></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:mfrac><mml:mo>,</mml:mo></mml:mrow></mml:mtd></mml:mtr></mml:mtable></mml:mrow></mml:math></disp-formula>where <italic>L</italic> is the length of the longest CS between <inline-formula id="IE149"><mml:math id="IM149"><mml:mrow><mml:msubsup><mml:mrow><mml:mi>M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE150"><mml:math id="IM150"><mml:mrow><mml:msubsup><mml:mrow><mml:mi>M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>. The function on the right-hand side of <xref ref-type="disp-formula" rid="E15">Equation (13)</xref> is an increasing function of <italic>L</italic>, equal to 0 when <inline-formula id="IE151"><mml:math id="IM151"><mml:mrow><mml:mi>L</mml:mi><mml:mo><</mml:mo><mml:mi>ℓ</mml:mi></mml:mrow></mml:math></inline-formula>, and equal to 1 when <inline-formula id="IE152"><mml:math id="IM152"><mml:mrow><mml:mi>L</mml:mi><mml:mo>=</mml:mo><mml:mi>n</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>. Given that <inline-formula id="IE153"><mml:math id="IM153"><mml:mrow><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>≥</mml:mo><mml:msub><mml:mrow><mml:mi>E</mml:mi></mml:mrow><mml:mi>s</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>≥</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>L</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:mo>/</mml:mo><mml:mi>n</mml:mi></mml:mrow></mml:math></inline-formula>, replacing <italic>L</italic> by <inline-formula id="IE154"><mml:math id="IM154"><mml:mrow><mml:mi>n</mml:mi><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>−</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula> in <xref ref-type="disp-formula" rid="E15">Equation (13)</xref> gives the desired relation between <italic>s</italic><sub>2</sub> and <italic>p</italic><sub>2</sub> of <xref ref-type="disp-formula" rid="E10">Equation (9)</xref>.□</p><p>Finally, we prove the relationship between the length of the longest increasing subsequence (LIS) and the largest number of sequences of maximal length.</p><p><statement id="mthst5"><p><sc>Lemma</sc> 3. For <inline-formula id="IE155"><mml:math id="IM155"><mml:mrow><mml:mi>i</mml:mi><mml:mo>,</mml:mo><mml:mi>n</mml:mi><mml:mo>,</mml:mo><mml:mi>ℓ</mml:mi><mml:mo>∈</mml:mo><mml:mi mathvariant="double-struck">N</mml:mi><mml:mo>,</mml:mo><mml:mo> </mml:mo><mml:mi>n</mml:mi><mml:mo>≥</mml:mo><mml:mi>i</mml:mi><mml:mo>≥</mml:mo><mml:mi>ℓ</mml:mi></mml:mrow></mml:math></inline-formula>, for any sequence of length <italic>n</italic> with an LIS of at most <italic>i</italic>, the largest number of increasing subsequences of length <inline-formula id="IE156"><mml:math id="IM156"><mml:mi>ℓ</mml:mi></mml:math></inline-formula> is
<disp-formula id="E16"><mml:math id="M15"><mml:mrow><mml:msup><mml:mrow><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mfrac><mml:mi>n</mml:mi><mml:mi>i</mml:mi></mml:mfrac></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:mrow><mml:mi>ℓ</mml:mi></mml:msup><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mi>i</mml:mi></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>ℓ</mml:mi></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mo>,</mml:mo></mml:mrow></mml:math></disp-formula>and this bound is tight.</p><p><sc>Proof</sc>. The proof relies on the properties of patience sorting (<xref rid="btz354-B1" ref-type="bibr">Aldous and Diaconis, 1999</xref>). Patience sorting for a shuffled deck of cards works as follows:</p></statement></p><p><list list-type="bullet"><list-item><p>The algorithm creates stacks of cards where in each stack the cards are in decreasing order from the bottom to the top of the stack. The stacks are organized in a line, left to right.</p></list-item><list-item><p>At each round, the next card of the deck is examined and added to the top of the left most stack it can go on, i.e. the left most stack with a top card whose value is higher than the new card.</p></list-item><list-item><p>If no existing stack is suitable, a new stack is created to the right with the new card.</p></list-item></list></p><p>After all the cards are drawn and organized in stacks (see <xref ref-type="fig" rid="btz354-F2">Fig. 2</xref>), the following properties hold: (i) no two cards from an increasing subsequence in the original deck are in the same stack, and (ii) the number of stacks is equal to the LIS (see <xref rid="btz354-B1" ref-type="bibr">Aldous and Diaconis, 1999</xref>, Lemma 1).
</p><fig id="btz354-F2" orientation="portrait" position="float"><label>Fig. 2.</label><caption><p>An example of stacks created when sorting a deck of cards. The LIS is 6, with the arrows showing a possible increasing subsequence of maximal length. To maximize the number of possible subsequences of maximum length, the height of the stacks have to be equal</p></caption><graphic xlink:href="btz354f2"></graphic></fig><p>Fix <inline-formula id="IE157"><mml:math id="IM157"><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo><mml:mo>∈</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mi>i</mml:mi><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula> and a sequence <italic>S</italic> of length <italic>n</italic> with LIS of <inline-formula id="IE158"><mml:math id="IM158"><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo></mml:mrow></mml:math></inline-formula>. At the end of patience sorting of <italic>S</italic>, let <inline-formula id="IE159"><mml:math id="IM159"><mml:mrow><mml:mi mathvariant="bold">s</mml:mi><mml:mo>=</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>0</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo><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 vector of the height of each of the stacks. Then, an upper bound on the number of increasing subsequence of length <inline-formula id="IE160"><mml:math id="IM160"><mml:mi>ℓ</mml:mi></mml:math></inline-formula> in <italic>S</italic> is
<disp-formula id="E17"><label>(14)</label><mml:math id="M16"><mml:mrow><mml:mi>g</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi mathvariant="bold">s</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:munder><mml:mo>∑</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mrow><mml:mi>A</mml:mi><mml:mo>⊂</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo>′</mml:mo><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mrow><mml:mo> | </mml:mo><mml:mi>A</mml:mi><mml:mo> | </mml:mo><mml:mo>=</mml:mo><mml:mi>ℓ</mml:mi></mml:mrow></mml:mtd></mml:mtr></mml:mtable></mml:munder><mml:mrow><mml:munder><mml:mo>∏</mml:mo><mml:mrow><mml:mi>j</mml:mi><mml:mo>∈</mml:mo><mml:mi>A</mml:mi></mml:mrow></mml:munder><mml:mrow><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mi>j</mml:mi></mml:msub></mml:mrow></mml:mrow><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>This is an upper bound as every choice of <inline-formula id="IE161"><mml:math id="IM161"><mml:mi>ℓ</mml:mi></mml:math></inline-formula> elements from different stacks does not necessarily define a valid increasing subsequence of <italic>S</italic>. We show that <italic>g</italic> reaches its maximum when <inline-formula id="IE162"><mml:math id="IM162"><mml:mrow><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>0</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mo>⋯</mml:mo><mml:mo>=</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mi>i</mml:mi><mml:mo>′</mml:mo></mml:mrow></mml:math></inline-formula>.</p><p>Because the set <inline-formula id="IE163"><mml:math id="IM163"><mml:mrow><mml:mi>C</mml:mi><mml:mo>=</mml:mo><mml:mo stretchy="false">{</mml:mo><mml:mi mathvariant="bold">s</mml:mi><mml:mo>=</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>0</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo> | </mml:mo><mml:munder><mml:mo>∑</mml:mo><mml:mi>j</mml:mi></mml:munder><mml:mrow><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mi>j</mml:mi></mml:msub></mml:mrow><mml:mo>=</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">}</mml:mo></mml:mrow></mml:math></inline-formula> is compact, <italic>g</italic> reaches a maximum on <italic>C</italic>. Suppose that in <bold>s</bold>, not all the <italic>s<sub>j</sub></italic> are equal; without loss of generality, assume that <inline-formula id="IE164"><mml:math id="IM164"><mml:mrow><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo><mml:mo>−</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE165"><mml:math id="IM165"><mml:mrow><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> are distinct. Set <inline-formula id="IE166"><mml:math id="IM166"><mml:mrow><mml:mo>α</mml:mo><mml:mo>=</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo><mml:mo>−</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mo>+</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>/</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math></inline-formula> and consider the point <inline-formula id="IE167"><mml:math id="IM167"><mml:mrow><mml:mi mathvariant="bold">s</mml:mi><mml:mo>′</mml:mo><mml:mo>=</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>0</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo><mml:mo>−</mml:mo><mml:mn>3</mml:mn></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:mo>α</mml:mo><mml:mo>,</mml:mo><mml:mo>α</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></inline-formula>. Let us also use the notation
<disp-formula id="E18"><mml:math id="M17"><mml:mrow><mml:mo>ρ</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:munder><mml:mo>∑</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mrow><mml:mi>A</mml:mi><mml:mo>⊂</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo>′</mml:mo><mml:mo>−</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mrow><mml:mo> | </mml:mo><mml:mi>A</mml:mi><mml:mo> | </mml:mo><mml:mo>=</mml:mo><mml:mi>x</mml:mi></mml:mrow></mml:mtd></mml:mtr></mml:mtable></mml:munder><mml:mrow><mml:munder><mml:mo>∏</mml:mo><mml:mrow><mml:mi>j</mml:mi><mml:mo>∈</mml:mo><mml:mi>A</mml:mi></mml:mrow></mml:munder><mml:mrow><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mi>j</mml:mi></mml:msub></mml:mrow></mml:mrow><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>Then, we split the sum in <inline-formula id="IE168"><mml:math id="IM168"><mml:mrow><mml:mi>g</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi mathvariant="bold">s</mml:mi><mml:mo>′</mml:mo><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> into the terms containing neither <inline-formula id="IE169"><mml:math id="IM169"><mml:mrow><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo><mml:mo>−</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> nor <inline-formula id="IE170"><mml:math id="IM170"><mml:mrow><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> (<inline-formula id="IE171"><mml:math id="IM171"><mml:mrow><mml:mo>=</mml:mo><mml:mo>ρ</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>ℓ</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>), the terms that contain one of <inline-formula id="IE172"><mml:math id="IM172"><mml:mrow><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo><mml:mo>−</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> or <inline-formula id="IE173"><mml:math id="IM173"><mml:mrow><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> (<inline-formula id="IE174"><mml:math id="IM174"><mml:mrow><mml:mo>=</mml:mo><mml:mn>2</mml:mn><mml:mo>α</mml:mo><mml:mo>ρ</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>ℓ</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>) and the terms that contain both (<inline-formula id="IE175"><mml:math id="IM175"><mml:mrow><mml:mo>=</mml:mo><mml:msup><mml:mrow><mml:mo>α</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:msup><mml:mo>ρ</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>ℓ</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>), and we use the inequality <inline-formula id="IE176"><mml:math id="IM176"><mml:mrow><mml:msup><mml:mrow><mml:mo>α</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:msup><mml:mo>></mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo><mml:mo>−</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> (arithmetic mean is larger than geometric mean):
<disp-formula id="E19"><mml:math id="M18"><mml:mrow><mml:mtable><mml:mtr columnalign="left"><mml:mtd columnalign="left"><mml:mrow><mml:mi>g</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi mathvariant="bold">s</mml:mi><mml:mo>′</mml:mo><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mo>ρ</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>ℓ</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>+</mml:mo><mml:mn>2</mml:mn><mml:mo>α</mml:mo><mml:mo>ρ</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>ℓ</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo><mml:mo>+</mml:mo><mml:msup><mml:mrow><mml:mo>α</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:msup><mml:mo>ρ</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>ℓ</mml:mi><mml:mo>−</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mtd></mml:mtr><mml:mtr columnalign="left"><mml:mtd columnalign="left"><mml:mrow><mml:mo>></mml:mo><mml:mo>ρ</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>ℓ</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>+</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo><mml:mo>−</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mo>+</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>ρ</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>ℓ</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo><mml:mo>+</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo><mml:mo>−</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>ρ</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>ℓ</mml:mi><mml:mo>−</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mtd></mml:mtr><mml:mtr columnalign="left"><mml:mtd columnalign="left"><mml:mrow><mml:mo>=</mml:mo><mml:mi>g</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi mathvariant="bold">s</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>.</mml:mo></mml:mrow></mml:mtd></mml:mtr></mml:mtable></mml:mrow></mml:math></disp-formula></p><p>Hence, <inline-formula id="IE177"><mml:math id="IM177"><mml:mrow><mml:mi>g</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi mathvariant="bold">s</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>, where <bold>s</bold> contains two distinct values, is not maximum, and <italic>g</italic> must reach its maximum when all the <italic>s<sub>j</sub></italic> are equal. Furthermore, in that case <inline-formula id="IE178"><mml:math id="IM178"><mml:mrow><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mi>j</mml:mi></mml:msub><mml:mo>=</mml:mo><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mi>i</mml:mi><mml:mo>′</mml:mo></mml:mrow></mml:math></inline-formula>.</p><p>Therefore,
<disp-formula id="E20"><label>(15)</label><mml:math id="M19"><mml:mrow><mml:munder><mml:mrow><mml:mi>max</mml:mi></mml:mrow><mml:mrow><mml:mi mathvariant="bold">s</mml:mi><mml:mo>∈</mml:mo><mml:mi>C</mml:mi></mml:mrow></mml:munder><mml:mi>g</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi mathvariant="bold">s</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:munder><mml:mo>∑</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mrow><mml:mi>A</mml:mi><mml:mo>⊂</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mi>i</mml:mi><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mrow><mml:mo> | </mml:mo><mml:mi>A</mml:mi><mml:mo> | </mml:mo><mml:mo>=</mml:mo><mml:mi>ℓ</mml:mi></mml:mrow></mml:mtd></mml:mtr></mml:mtable></mml:munder><mml:mrow><mml:msup><mml:mrow><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mfrac><mml:mi>n</mml:mi><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo></mml:mrow></mml:mfrac></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:mrow><mml:mi>ℓ</mml:mi></mml:msup></mml:mrow><mml:mo>=</mml:mo><mml:msup><mml:mrow><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:mfrac><mml:mi>n</mml:mi><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo></mml:mrow></mml:mfrac></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:mrow><mml:mi>ℓ</mml:mi></mml:msup><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mtable><mml:mtr><mml:mtd><mml:mi>i</mml:mi><mml:mo>′</mml:mo></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mi>ℓ</mml:mi></mml:mtd></mml:mtr></mml:mtable><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mo>≜</mml:mo><mml:msub><mml:mrow><mml:mi>m</mml:mi></mml:mrow><mml:mrow><mml:mi>n</mml:mi><mml:mo>,</mml:mo><mml:mi>ℓ</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>i</mml:mi><mml:mo>′</mml:mo><mml:mo stretchy="true">)</mml:mo><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>The function <inline-formula id="IE179"><mml:math id="IM179"><mml:mrow><mml:msub><mml:mrow><mml:mi>m</mml:mi></mml:mrow><mml:mrow><mml:mi>n</mml:mi><mml:mo>,</mml:mo><mml:mi>ℓ</mml:mi></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mo>·</mml:mo><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> defined above is increasing and the maximum is reached for <inline-formula id="IE180"><mml:math id="IM180"><mml:mrow><mml:mi>i</mml:mi><mml:mo>′</mml:mo><mml:mo>=</mml:mo><mml:mi>i</mml:mi></mml:mrow></mml:math></inline-formula>.</p><p>Finally, consider the sequence <italic>S</italic>(<italic>i</italic>, <italic>n</italic>), <italic>i</italic> divides <italic>n</italic>, defined by blocks:
<disp-formula id="E21"><mml:math id="M20"><mml:mrow><mml:munder><mml:munder><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mi>n</mml:mi><mml:mo>/</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:mn>0</mml:mn></mml:mrow><mml:mo stretchy="true">︸</mml:mo></mml:munder><mml:mrow><mml:mtext>block</mml:mtext><mml:mo> </mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:munder><mml:munder><mml:munder><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mn>2</mml:mn><mml:mi>n</mml:mi><mml:mo>/</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:mo stretchy="true">(</mml:mo><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mi>i</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mo stretchy="true">︸</mml:mo></mml:munder><mml:mrow><mml:mtext>block</mml:mtext><mml:mo> </mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:munder><mml:mo>⋯</mml:mo><mml:munder><mml:munder><mml:mrow><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:mo>⋯</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mi>i</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mo stretchy="true">︸</mml:mo></mml:munder><mml:mrow><mml:mtext>block</mml:mtext><mml:mi>i</mml:mi></mml:mrow></mml:munder><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>Each block is of length <italic>n</italic>/<italic>i</italic>, the numbers in each blocks are in decreasing order, and the start of the blocks are in increasing order: block <italic>j</italic> is the decreasing sequence <inline-formula id="IE181"><mml:math id="IM181"><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mi mathvariant="italic">jn</mml:mi><mml:mo>/</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:mo stretchy="true">(</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mi>j</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="true">)</mml:mo><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mi>i</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>.</p><p>When the patience sorting algorithm is applied to the list <italic>S</italic>(<italic>i</italic>, <italic>n</italic>), the stacks are filled up one by one, from bottom to top and from left to right, and have the same height of <italic>n</italic>/<italic>i</italic>. Therefore, any choice of one element in each stack is a valid increasing subsequence of <italic>S</italic>(<italic>i</italic>, <italic>n</italic>) and the bound of <xref ref-type="disp-formula" rid="E20">Equation (15)</xref> is attained. □</p><p>Finally, we can restate and prove the main theorem.</p><p><statement id="mthst6"><p><sc>Theorem</sc> 2. <italic>For any</italic><inline-formula id="IE182"><mml:math id="IM182"><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>∈</mml:mo><mml:mo stretchy="true">[</mml:mo><mml:mn>2</mml:mn><mml:mo>,</mml:mo><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula><italic>and any</italic><inline-formula id="IE183"><mml:math id="IM183"><mml:mrow><mml:mn>1</mml:mn><mml:mo>></mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>≥</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>></mml:mo><mml:mn>0</mml:mn></mml:mrow></mml:math></inline-formula><italic>, there exist functions</italic><inline-formula id="IE184"><mml:math id="IM184"><mml:mrow><mml:msubsup><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mrow><mml:mi>n</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>ℓ</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:mo>·</mml:mo><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula><italic>and</italic><inline-formula id="IE185"><mml:math id="IM185"><mml:mrow><mml:msubsup><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mrow><mml:mi>n</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>ℓ</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:mo>·</mml:mo><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula><italic>such that OMH is</italic><inline-formula id="IE186"><mml:math id="IM186"><mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mrow><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msubsup><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mrow><mml:mi>n</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>ℓ</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>,</mml:mo><mml:msubsup><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mrow><mml:mi>n</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>ℓ</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:mrow></mml:math></inline-formula><italic>-sensitive for the edit distance.</italic></p><p><sc>Proof</sc>. It is a direct consequence of Lemma 1 and Lemma 2. □</p></statement></p></sec><sec><title>4 Discussion</title><sec><title>4.1 Parameters <inline-formula id="IE187"><mml:math id="IM187"><mml:mrow><mml:msub><mml:mrow><mml:mi mathvariant="normal">s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi mathvariant="normal">p</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi mathvariant="normal">s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi mathvariant="normal">p</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:math></inline-formula></title><p>To have a proper LSH method, the conditions <inline-formula id="IE188"><mml:math id="IM188"><mml:mrow><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>≥</mml:mo><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:math></inline-formula> must hold. This condition means that the method is able to distinguish with some probability between dissimilar (<inline-formula id="IE189"><mml:math id="IM189"><mml:mrow><mml:mo>≤</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:math></inline-formula>) and similar (<inline-formula id="IE190"><mml:math id="IM190"><mml:mrow><mml:mo>≥</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub></mml:mrow></mml:math></inline-formula>) sequences. <xref ref-type="fig" rid="btz354-F3">Figure 3</xref> shows the functions <italic>p</italic><sup>1</sup> (blue lines) and <italic>p</italic><sup>2</sup> (red lines) from Theorem 2 for varying values of <inline-formula id="IE191"><mml:math id="IM191"><mml:mi>ℓ</mml:mi></mml:math></inline-formula>.
</p><fig id="btz354-F3" orientation="portrait" position="float"><label>Fig. 3.</label><caption><p>The relationships between the similarity thresholds <italic>s</italic><sub>1</sub> and <italic>s</italic><sub>2</sub>, and the probabilities <italic>p</italic><sub>1</sub> and <italic>p</italic><sub>2</sub>, for <italic>n </italic>=<italic> </italic>100, <italic>k </italic>=<italic> </italic>5. Given a probability, e.g. <inline-formula id="IE192"><mml:math id="IM192"><mml:mrow><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mn>0.25</mml:mn></mml:mrow></mml:math></inline-formula> shown by the horizontal gray line, the OMH method can distinguish between similarities below <italic>s</italic><sub>2</sub> (below left vertical gray line) and from similarities above <italic>s</italic><sub>1</sub> (above the right vertical gray line). The functions are defined at discrete points, when <italic>ns</italic> is integral, represented by the circles and squares</p></caption><graphic xlink:href="btz354f3"></graphic></fig><p>At the limit, taking <inline-formula id="IE193"><mml:math id="IM193"><mml:mrow><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mi>p</mml:mi></mml:mrow></mml:math></inline-formula>, the method can distinguish between any <italic>s</italic><sub>1</sub> and <italic>s</italic><sub>2</sub> such that <inline-formula id="IE194"><mml:math id="IM194"><mml:mrow><mml:msup><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>≥</mml:mo><mml:mi>p</mml:mi></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE195"><mml:math id="IM195"><mml:mrow><mml:msup><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>≤</mml:mo><mml:mi>p</mml:mi></mml:mrow></mml:math></inline-formula> (gray lines on <xref ref-type="fig" rid="btz354-F3">Fig. 3</xref>). For larger values of <inline-formula id="IE196"><mml:math id="IM196"><mml:mi>ℓ</mml:mi></mml:math></inline-formula>, the gap between distinguishable values is reduced, although at the cost of having high values for <italic>s</italic><sub>1</sub>.</p></sec><sec><title>4.2 Choice of parameter <inline-formula id="IE197"><mml:math id="IM197"><mml:mi>ℓ</mml:mi></mml:math></inline-formula></title><p>The main difference between OMH and the minHash methods is the choice of <inline-formula id="IE198"><mml:math id="IM198"><mml:mi>ℓ</mml:mi></mml:math></inline-formula><italic>k</italic>-mers, where minHash corresponds to the case of <inline-formula id="IE199"><mml:math id="IM199"><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula> (ignoring the slight difference between Jaccard and weighted Jaccard). It might seem surprising at first that OMH is an LSH for edit dissimilarity for any values of <inline-formula id="IE200"><mml:math id="IM200"><mml:mi>ℓ</mml:mi></mml:math></inline-formula>, except for the extremes of <inline-formula id="IE201"><mml:math id="IM201"><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula> and <inline-formula id="IE202"><mml:math id="IM202"><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>=</mml:mo><mml:mi>n</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>.</p><p>The proof of Theorem 2 is consistent with this analysis. For both these extreme values of <inline-formula id="IE203"><mml:math id="IM203"><mml:mi>ℓ</mml:mi></mml:math></inline-formula>, <xref ref-type="disp-formula" rid="E15">Equation (13)</xref>, which relates the probability <italic>p</italic><sub>2</sub> to the similarity <italic>s</italic><sub>2</sub>, becomes trivially true (<inline-formula id="IE204"><mml:math id="IM204"><mml:mrow><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo><</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula>). This means that even a certain hash collision (probability of 1) provides no guarantee on the relative order of common <italic>k</italic>-mers between the two sequences (i.e. the length of the longest subsequence <italic>L </italic>=<italic> </italic>1: only one <italic>k</italic>-mer is guaranteed to align). On the other hand, any other value of <inline-formula id="IE205"><mml:math id="IM205"><mml:mi>ℓ</mml:mi></mml:math></inline-formula> leads to an actual bound in <xref ref-type="disp-formula" rid="E15">Equation (13)</xref>.</p><p>For example, when <inline-formula id="IE206"><mml:math id="IM206"><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>=</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math></inline-formula>, the minimum number of <italic>k</italic>-mers that must align in proper order as a function of the collision probability <italic>p</italic><sub>2</sub> is
<disp-formula id="E22"><label>(16)</label><mml:math id="M21"><mml:mrow><mml:mi>L</mml:mi><mml:mo>=</mml:mo><mml:mfrac><mml:mrow><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mrow><mml:mo stretchy="true">(</mml:mo><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:mfrac><mml:mo>.</mml:mo></mml:mrow></mml:math></disp-formula></p><p>Even in the case where <italic>n</italic> is very large, then <inline-formula id="IE207"><mml:math id="IM207"><mml:mrow><mml:mi>L</mml:mi><mml:mo>≈</mml:mo><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msub><mml:mrow><mml:mi>p</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>, the number of properly aligning <italic>k</italic>-mers becomes large when the probability of collision <italic>p</italic><sub>2</sub> is close to 1. This is in contrast to the minHash, where a probability of collision of 1 (i.e. a Jaccard similarity of 1) does not guarantee that more than two <italic>k</italic>-mers properly align (see example in Section 2.2).</p><p>In practice, the parameter <inline-formula id="IE208"><mml:math id="IM208"><mml:mi>ℓ</mml:mi></mml:math></inline-formula> should be relatively small, say <inline-formula id="IE209"><mml:math id="IM209"><mml:mrow><mml:mn>2</mml:mn><mml:mo>≤</mml:mo><mml:mi>ℓ</mml:mi><mml:mo>≤</mml:mo><mml:mn>5</mml:mn></mml:mrow></mml:math></inline-formula>. Increasing the value of <inline-formula id="IE210"><mml:math id="IM210"><mml:mi>ℓ</mml:mi></mml:math></inline-formula> has two effects on the OMH method. First, it increases the minimum edit similarity that is detectable by the method, as there must be at least <inline-formula id="IE211"><mml:math id="IM211"><mml:mrow><mml:mi>ℓ</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> bases in the alignment of the two sequences for OMH to have a non-zero probability of hash collision. Second, a larger value of <inline-formula id="IE212"><mml:math id="IM212"><mml:mi>ℓ</mml:mi></mml:math></inline-formula> implies that the probability of hash collision is small, which requires storing a higher number of vectors in a sketch to obtain a low variance. There is a trade-off between how sensitive the scheme is to relative order (high value of <inline-formula id="IE213"><mml:math id="IM213"><mml:mi>ℓ</mml:mi></mml:math></inline-formula>) and the smaller size for the sketch (low value of <inline-formula id="IE214"><mml:math id="IM214"><mml:mi>ℓ</mml:mi></mml:math></inline-formula>).</p></sec><sec><title>4.3 Practical sketches for OMH</title><p>In our implementation, the OMH sketch for a sequence <italic>S</italic> contains more than just the list of vectors <inline-formula id="IE215"><mml:math id="IM215"><mml:mrow><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>S</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>. In practice, we store
<list list-type="bullet"><list-item><p>the length of the sequence <inline-formula id="IE216"><mml:math id="IM216"><mml:mrow><mml:mo> | </mml:mo><mml:mi>S</mml:mi><mml:mo> | </mml:mo></mml:mrow></mml:math></inline-formula>,</p></list-item><list-item><p>a list of <italic>m</italic> vectors <inline-formula id="IE217"><mml:math id="IM217"><mml:mrow><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>S</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> and associated order vector <inline-formula id="IE218"><mml:math id="IM218"><mml:mrow><mml:msub><mml:mrow><mml:mi>r</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></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 stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>r</mml:mi></mml:mrow><mml:mn>0</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>r</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</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>.</p></list-item></list></p><p>Recall that the <italic>k</italic>-mers in the vector <inline-formula id="IE219"><mml:math id="IM219"><mml:mrow><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>S</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> are listed in the order in which they appear in <italic>S</italic>. The order vector <inline-formula id="IE220"><mml:math id="IM220"><mml:mrow><mml:msub><mml:mrow><mml:mi>r</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> is a permutation of the indices <inline-formula id="IE221"><mml:math id="IM221"><mml:mrow><mml:mo stretchy="true">[</mml:mo><mml:mi>ℓ</mml:mi><mml:mo stretchy="true">]</mml:mo></mml:mrow></mml:math></inline-formula> that can reorder the <italic>k</italic>-mers according to <italic>π</italic>. That is, <inline-formula id="IE222"><mml:math id="IM222"><mml:mrow><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></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 stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>m</mml:mi></mml:mrow><mml:mn>0</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>m</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</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 <italic>i </italic><<italic> j</italic> imply that <inline-formula id="IE223"><mml:math id="IM223"><mml:mrow><mml:mo>π</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>m</mml:mi></mml:mrow><mml:mrow><mml:msub><mml:mrow><mml:mi>r</mml:mi></mml:mrow><mml:mi>i</mml:mi></mml:msub></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>o</mml:mi></mml:mrow><mml:mrow><mml:msub><mml:mrow><mml:mi>r</mml:mi></mml:mrow><mml:mi>i</mml:mi></mml:msub></mml:mrow></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo><</mml:mo><mml:mo>π</mml:mo><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>m</mml:mi></mml:mrow><mml:mrow><mml:msub><mml:mrow><mml:mi>r</mml:mi></mml:mrow><mml:mi>j</mml:mi></mml:msub></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>o</mml:mi></mml:mrow><mml:mrow><mml:msub><mml:mrow><mml:mi>r</mml:mi></mml:mrow><mml:mi>j</mml:mi></mml:msub></mml:mrow></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> (where, as in the definition, <italic>o<sub>i</sub></italic> is the occurrence number of the <italic>k</italic>-mer <italic>m<sub>i</sub></italic>). The total space usage of a sketch is <inline-formula id="IE224"><mml:math id="IM224"><mml:mrow><mml:mi>O</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mtext>log</mml:mtext><mml:mo> </mml:mo><mml:mo> | </mml:mo><mml:mi>S</mml:mi><mml:mo> | </mml:mo><mml:mo>+</mml:mo><mml:mi>m</mml:mi><mml:mi>ℓ</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi>k</mml:mi><mml:mo> </mml:mo><mml:mtext>log</mml:mtext><mml:mo> </mml:mo><mml:mo>σ</mml:mo><mml:mo>+</mml:mo><mml:mtext>log</mml:mtext><mml:mo> </mml:mo><mml:mi>ℓ</mml:mi><mml:mo stretchy="true">)</mml:mo><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>.</p><p>The reason for the order vector in the sketch is to recover both an estimate of the weighted Jaccard between the two sequences and how well these common <italic>k</italic>-mers properly align. More precisely, given two sketches for <italic>S</italic><sub>1</sub> and <italic>S</italic><sub>2</sub>, the number of collisions <inline-formula id="IE225"><mml:math id="IM225"><mml:mrow><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> and the number of collisions in the reordered <italic>k</italic>-mers according to the order vector <inline-formula id="IE226"><mml:math id="IM226"><mml:mrow><mml:msub><mml:mrow><mml:mi>o</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub></mml:mrow></mml:math></inline-formula> give an estimate of the weighted Jaccard <inline-formula id="IE227"><mml:math id="IM227"><mml:mrow><mml:msup><mml:mrow><mml:mi mathvariant="normal">J</mml:mi></mml:mrow><mml:mi mathvariant="normal">w</mml:mi></mml:msup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>. Using this estimate, the sizes of <italic>S</italic><sub>1</sub> and <italic>S</italic><sub>2</sub> from the sketches, and the formula <inline-formula id="IE228"><mml:math id="IM228"><mml:mrow><mml:mo> | </mml:mo><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><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:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo> | </mml:mo><mml:mo>=</mml:mo><mml:mo> | </mml:mo><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>∪</mml:mo><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo> | </mml:mo><mml:mo>+</mml:mo><mml:mo> | </mml:mo><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>∩</mml:mo><mml:msubsup><mml:mrow><mml:mi mathvariant="script">M</mml:mi></mml:mrow><mml:mi>k</mml:mi><mml:mi>w</mml:mi></mml:msubsup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo> | </mml:mo></mml:mrow></mml:math></inline-formula>, we can recover estimates for the size of the intersection and union of the weighted <italic>k</italic>-mer sets. Finally, formulas (10) and (11) give the probability for <inline-formula id="IE229"><mml:math id="IM229"><mml:mi>ℓ</mml:mi></mml:math></inline-formula><italic>k</italic>-mers from the intersection to be in the same alignment order between the two sequences. The case where the Jaccard similarity is not sufficient to assess that the sequences have a high edit similarity is precisely the case when this last probability is low.</p><p>In other words, the extra <inline-formula id="IE230"><mml:math id="IM230"><mml:mrow><mml:mi>O</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mtext>log</mml:mtext><mml:mo> </mml:mo><mml:mi>ℓ</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula> bits of information per <italic>k</italic>-mer in the OMH sketch compared with a weighted minHash sketch corresponds to the supplemental information given by OMH compared with minHash. Given that <inline-formula id="IE231"><mml:math id="IM231"><mml:mi>ℓ</mml:mi></mml:math></inline-formula> is small in practice, the cost for this extra information is also very small.</p><p>For genomics sequences, it is traditional to compute the minHash using ‘canonical’ <italic>k</italic>-mers (defined as a <italic>k</italic>-mer or its reverse complement, whichever comes first lexicographically). In the OMH sketches, it is not possible to use canonical <italic>k</italic>-mers as this in incompatible with the order information encoded in the vector <inline-formula id="IE232"><mml:math id="IM232"><mml:mrow><mml:msub><mml:mrow><mml:mi>h</mml:mi></mml:mrow><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>,</mml:mo><mml:mo>π</mml:mo></mml:mrow></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:mi>S</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>. Rather, two sketches, one for the forward strand and one for the reverse are stored. Comparing two sequences requires doing two sketches comparisons.</p><p>The size of an OMH sketch is <inline-formula id="IE233"><mml:math id="IM233"><mml:mrow><mml:mi>O</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:mi mathvariant="italic">km</mml:mi><mml:mi>ℓ</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>.</p></sec><sec><title>4.4 Weighted Jaccard and OMH</title><p>Even though the Jaccard and minHash sketches are regularly used as a measure of the <italic>k</italic>-mer content similarity in computational biology software, the weighted Jaccard similarity has been heavily studied and used in other contexts, such as large database document classification and retrieval (e.g. <xref rid="btz354-B30" ref-type="bibr">Shrivastava, 2016</xref>; <xref rid="btz354-B32" ref-type="bibr">Wu <italic>et al.</italic>, 2017</xref>), near duplicate image detection (<xref rid="btz354-B7" ref-type="bibr">Chum <italic>et al.</italic>, 2008</xref>), duplicate news story detection (<xref rid="btz354-B2" ref-type="bibr">Alonso <italic>et al.</italic>, 2013</xref>), source code deduplication, time series indexing (<xref rid="btz354-B22" ref-type="bibr">Luo and Shrivastava, 2017</xref>), hierarchical topic extraction (<xref rid="btz354-B10" ref-type="bibr">Gollapudi and Panigrahy, 2006</xref>), or malware classification (<xref rid="btz354-B8" ref-type="bibr">Drew <italic>et al.</italic>, 2017</xref>) and detection (<xref rid="btz354-B29" ref-type="bibr">Raff and Nicholas, 2017</xref>).</p><p>The weighted Jaccard, compared with the unweighted Jaccard, gives a more complete measure of the similarity between two sets or sequences. Obviously, when no elements are repeated, the two similarities are equal. On the other hand, in the case of many repeated elements, the difference can be significant.</p><p>For example, returning to the example from Section 2.2 where <inline-formula id="IE234"><mml:math id="IM234"><mml:mrow><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mn>0</mml:mn><mml:mo>…</mml:mo><mml:mn>01</mml:mn><mml:mo>…</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula> with <italic>n</italic> – <italic>k</italic> 0s followed by <italic>k</italic> 1s and <italic>S</italic><sub>2</sub> with <italic>k</italic> 0s followed by <italic>n</italic> – <italic>k</italic> 1s, the edit similarity is very low: <inline-formula id="IE235"><mml:math id="IM235"><mml:mrow><mml:msub><mml:mrow><mml:mi mathvariant="normal">E</mml:mi></mml:mrow><mml:mi mathvariant="normal">s</mml:mi></mml:msub><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>≤</mml:mo><mml:mn>2</mml:mn><mml:mi>k</mml:mi><mml:mo>/</mml:mo><mml:mi>n</mml:mi></mml:mrow></mml:math></inline-formula>. The Jaccard similarity is <inline-formula id="IE236"><mml:math id="IM236"><mml:mrow><mml:mi mathvariant="normal">J</mml:mi><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><mml:mo stretchy="true">)</mml:mo><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></inline-formula>, in other words, these two sequences are indistinguishable according to the Jaccard similarity. On the other hand, the weighted Jaccard is also very low: <inline-formula id="IE237"><mml:math id="IM237"><mml:mrow><mml:msup><mml:mrow><mml:mi mathvariant="normal">J</mml:mi></mml:mrow><mml:mi mathvariant="normal">w</mml:mi></mml:msup><mml:mo stretchy="true">(</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>S</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msub><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:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="true">)</mml:mo></mml:mrow></mml:math></inline-formula>, much more similar to the edit similarity.</p><p>In the case of two de Bruijn sequences that might have very low edit similarity, the Jaccard and weighted Jaccard are both equal to 1, as every <italic>k</italic>-mer occurs exactly once. Therefore, in this case the weighted Jaccard provides no extra information. The OMH sketching method, being also sensitive to the relative orders of the <italic>k</italic>-mers (see <xref ref-type="disp-formula" rid="E11">Equation 10</xref>), would have a probability of hash collision much lower than 1.</p><p>In <xref ref-type="fig" rid="btz354-F4">Figure 4</xref>, we generated 1 million random binary sequences (<italic>σ</italic> = 2) of length <italic>n </italic>=<italic> </italic>100. Each string is then randomly mutated a random number of times (up to 100 times) to obtain a pair of sequences with a random edit dissimilarity. Then, for each pair, we compute the actual edit dissimilarity, Hamming dissimilarity, the exact—i.e. not estimated by minHash—Jaccard and weighted Jaccard similarities. Additionally, the OMH sketch (with <inline-formula id="IE238"><mml:math id="IM238"><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>=</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math></inline-formula> and <italic>m </italic>=<italic> </italic>500) is also computed for each pair. The graph shows the median and first quartiles computed over the million pairs of sequences. Even for sequences with high edit dissimilarity (>0.4), the Jaccard similarity remains very high. However, the weighted Jaccard and OMH are more sensitive to the edit dissimilarity.
</p><fig id="btz354-F4" orientation="portrait" position="float"><label>Fig. 4.</label><caption><p>Evolution of the Jaccard, weighted Jaccard, Hamming and OMH against the edit dissimilarity on randomly generated binary sequences. In average, the Jaccard similarity stays high, even for sequences with high edit dissimilarity, unlike the weighted Jaccard, Hamming or OMH which are much more sensitive to the edit dissimilarity</p></caption><graphic xlink:href="btz354f4"></graphic></fig></sec><sec><title>4.5 Using sketches for phylogeny reconstruction</title><p>Genomic rearrangement in bacteria often involves mobile genomic elements known as ‘insertion sequences’ (IS). <xref rid="btz354-B18" ref-type="bibr">Lee <italic>et al.</italic> (2016)</xref> studied the frequencies and locations of these insertions and found that the positions are largely driven by the locations of existing copies. Although the locations of these inserts may vary across the genome, there are only a small number of inserted sequences that occur regularly. Consequently, the <italic>k</italic>-mer content of the genomes remains almost unchanged through these insertion events.</p><p>To test the effectiveness of OMH to recover the history of these insertion events, we simulated a family of <italic>Escherichia coli</italic> genomes by inserting these IS elements. We randomized the order of the four most common sequences (IS<italic>1</italic>, IS<italic>5</italic>, IS<italic>2</italic>, and IS<italic>186</italic>) and insert one into the genome at each of four generations of produced genomes. The location of the insertion was randomly chosen from the list of locations where the same sequence had been previously identified. Starting with <italic>E.coli</italic> K-12 MG1655 (NC_000913.2) we created two children by inserting the first element in the randomized order at two separate locations. For the next generation, we created two children for each of the individuals by choosing two random locations at which to insert the next sequence. For all the children in a generation, the same IS is inserted. We then measured all pairwise dissimilarities and created a phylogeny using the distances computed by OMH and weighted Jaccard.</p><p><xref ref-type="fig" rid="btz354-F5">Figure 5</xref> shows two phylogenies of the 16 final sequences with <inline-formula id="IE239"><mml:math id="IM239"><mml:mrow><mml:mi>m</mml:mi><mml:mo>=</mml:mo><mml:mn>10</mml:mn><mml:mo> </mml:mo><mml:mn>000</mml:mn></mml:mrow></mml:math></inline-formula>, <italic>k </italic>=<italic> </italic>22, <inline-formula id="IE240"><mml:math id="IM240"><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>=</mml:mo><mml:mn>3</mml:mn></mml:mrow></mml:math></inline-formula>. We chose <inline-formula id="IE241"><mml:math id="IM241"><mml:mi>ℓ</mml:mi></mml:math></inline-formula> to provide high differentiation between OMH and Jaccard, and <italic>m</italic> to provide high sensitivity to sequence perturbation. The binary sequences are the path used to create the child, i.e. siblings in the last generation would have the same three-digit prefix. OMH recovered the structure of the tree except for the four nodes at the top of the tree. Weighted Jaccard on the other hand cannot resolve most of the lineages as the sequences are very similar at the level of <italic>k</italic>-mer content. The experiment was repeated 10 times, and in each a similar tree was recovered (see <xref ref-type="supplementary-material" rid="sup1">Supplementary Fig. S1</xref>).
</p><fig id="btz354-F5" orientation="portrait" position="float"><label>Fig. 5.</label><caption><p>Phylogenies of the 16 child sequences produced by inserting IS elements into the <italic>Escherichia coli</italic> genome when distance is measured by both (<bold>a</bold>) OMH and (<bold>b</bold>) weighted Jaccard with <inline-formula id="IE242"><mml:math id="IM242"><mml:mrow><mml:mi>m</mml:mi><mml:mo>=</mml:mo><mml:mn>10</mml:mn><mml:mo> </mml:mo><mml:mo> </mml:mo><mml:mn>000</mml:mn></mml:mrow></mml:math></inline-formula>, <italic>k </italic>=<italic> </italic>22, <inline-formula id="IE243"><mml:math id="IM243"><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>=</mml:mo><mml:mn>3</mml:mn></mml:mrow></mml:math></inline-formula>. In general, OMH is able to recover more of the lineage structure than Jaccard because the <italic>k</italic>-mer content is very similar even though the sequences are inserted at different locations</p></caption><graphic xlink:href="btz354f5"></graphic></fig><p>To test the robustness of OMH to lower values of <italic>m</italic>, and in turn the necessary computational resources, we reconstructed the tree above with <inline-formula id="IE244"><mml:math id="IM244"><mml:mrow><mml:mi>m</mml:mi><mml:mo>=</mml:mo><mml:mn>1000</mml:mn><mml:mo>,</mml:mo><mml:mn>500</mml:mn><mml:mo>,</mml:mo></mml:mrow></mml:math></inline-formula> and 100 (see <xref ref-type="fig" rid="btz354-F6">Fig. 6</xref>). Even for low values of <italic>m</italic>, OMH is able to recover most of the tree structure, which is not recovered by weighted Jaccard even with a much larger <italic>m</italic>.
</p><fig id="btz354-F6" orientation="portrait" position="float"><label>Fig. 6.</label><caption><p>Phylogenies of the 16 child sequences produced by inserting IS elements into the <italic>Escherichia coli</italic> genome when distance is measured by OMH <italic>k </italic>=<italic> </italic>22, <inline-formula id="IE245"><mml:math id="IM245"><mml:mrow><mml:mi>ℓ</mml:mi><mml:mo>=</mml:mo><mml:mn>3</mml:mn></mml:mrow></mml:math></inline-formula> and <italic>m</italic> equals to (<bold>a</bold>) 1000, (<bold>b</bold>) 500 and (<bold>c</bold>) 100. As <italic>m</italic> increases, OMH recovers more accurately the general structure of the tree</p></caption><graphic xlink:href="btz354f6"></graphic></fig></sec></sec><sec><title>5 Conclusion</title><p>We presented the OMH method that is an LSH for the edit dissimilarity. Unlike the Jaccard similarity, which is only sensitive to the <italic>k</italic>-mer content of a sequence, OMH additionally takes into account the relative order of the <italic>k</italic>-mers in a sequence.</p><p>The OMH method is a refinement of the weighted Jaccard similarity that is used extensively in many related fields, such as document classification and duplicate detection. However, despite the advantages of the weighted Jaccard similarity, it has not yet been widely adopted by the bioinformatics community. Using weighted Jaccard and OMH for estimating edit similarity in bioinformatics applications can help reduce the number of false-positive matches which can in turn avoid unnecessary computations.</p></sec><sec sec-type="supplementary-material"><title>Supplementary Material</title><supplementary-material content-type="local-data" id="sup1"><label>btz354_Supplementary_Data</label><media xlink:href="btz354_supplementary_data.pdf"><caption><p>Click here for additional data file.</p></caption></media></supplementary-material></sec></body><back><ack id="ack1"><title>Acknowledgements</title><p>The authors would like to thank Mohsen Ferdosi and Heewook Lee for valuable discussion, and Natalie Sauerwald for comments on the manuscript.</p><sec><title>Funding</title><p>This work was supported in part by the Gordon and Betty Moore Foundation’s Data-Driven Discovery Initiative [GBMF4554 to C.K.]; the US National Institutes of Health [R01GM122935]; The Shurl and Kay Curci Foundation; and the generosity of Eric and Wendy Schmidt by recommendation of the Schmidt Futures program.</p><p><italic>Conflict of Interest</italic>: C.K. is a co-founder of Ocean Genomics, Inc.</p></sec></ack><ref-list id="ref1"><title>References</title><ref id="btz354-B1"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Aldous</surname><given-names>D.</given-names></name>, <name name-style="western"><surname>Diaconis</surname><given-names>P.</given-names></name></person-group> (<year>1999</year>)
<article-title>Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem</article-title>. <source>Bull. Am. Math. Soc</source>., <volume>36</volume>, <fpage>413</fpage>–<lpage>432</lpage>.</mixed-citation></ref><ref id="btz354-B2"><mixed-citation publication-type="book"><person-group person-group-type="author"><name name-style="western"><surname>Alonso</surname><given-names>O.</given-names></name></person-group><etal>et al</etal> (<year>2013</year>) <chapter-title>Duplicate news story detection revisited</chapter-title> In: <source>Asia Information Retrieval Symposium</source>.
<publisher-name>Springer</publisher-name>, pp. <fpage>203</fpage>–<lpage>214</lpage>.</mixed-citation></ref><ref id="btz354-B3"><mixed-citation publication-type="book"><person-group person-group-type="author"><name name-style="western"><surname>Backurs</surname><given-names>A.</given-names></name>, <name name-style="western"><surname>Indyk</surname><given-names>P.</given-names></name></person-group> (<year>2015</year>) <chapter-title>Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)</chapter-title> In: <source>Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’15</source>.
<publisher-name>ACM</publisher-name>,
<publisher-loc>New York, NY, USA</publisher-loc>, pp. <fpage>51</fpage>–<lpage>58</lpage>.</mixed-citation></ref><ref id="btz354-B4"><mixed-citation publication-type="other"><person-group person-group-type="author"><name name-style="western"><surname>Bar-Yossef</surname><given-names>Z.</given-names></name></person-group><etal>et al</etal> (<year>2004</year>) Approximating edit distance efficiently. In: <italic>45th Annual IEEE Symposium on Foundations of Computer Science</italic>, pp. <fpage>550</fpage>–<lpage>559</lpage>.</mixed-citation></ref><ref id="btz354-B5"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Berlin</surname><given-names>K.</given-names></name></person-group><etal>et al</etal> (<year>2015</year>)
<article-title>Assembling large genomes with single-molecule sequencing and locality-sensitive hashing</article-title>. <source>Nat. Biotechnol</source>., <volume>33</volume>, <fpage>623</fpage>–<lpage>630</lpage>.<pub-id pub-id-type="pmid">26006009</pub-id></mixed-citation></ref><ref id="btz354-B6"><mixed-citation publication-type="other"><person-group person-group-type="author"><name name-style="western"><surname>Broder</surname><given-names>A.Z.</given-names></name></person-group> (<year>1997</year>) On the resemblance and containment of documents. In: <italic>Proceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No.97TB100171)</italic>, pp. <fpage>21</fpage>–<lpage>29</lpage>.</mixed-citation></ref><ref id="btz354-B7"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Chum</surname><given-names>O.</given-names></name></person-group><etal>et al</etal> (<year>2008</year>)
<article-title>Near duplicate image detection: min-Hash and tf-idf weighting</article-title>. In: <source>BMVC</source>, Vol. 810, pp. <fpage>812</fpage>–<lpage>815</lpage>.</mixed-citation></ref><ref id="btz354-B8"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Drew</surname><given-names>J.</given-names></name></person-group><etal>et al</etal> (<year>2017</year>)
<article-title>Polymorphic malware detection using sequence classification methods and ensembles</article-title>. <source>EURASIP J. Inf. Secur</source>., <volume>2017</volume>, <fpage>2</fpage>.</mixed-citation></ref><ref id="btz354-B9"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Fredman</surname><given-names>M.L.</given-names></name></person-group> (<year>1975</year>)
<article-title>On computing the length of longest increasing subsequences</article-title>. <source>Discrete Math</source>., <volume>11</volume>, <fpage>29</fpage>–<lpage>35</lpage>.</mixed-citation></ref><ref id="btz354-B10"><mixed-citation publication-type="other"><person-group person-group-type="author"><name name-style="western"><surname>Gollapudi</surname><given-names>S.</given-names></name>, <name name-style="western"><surname>Panigrahy</surname><given-names>R.</given-names></name></person-group> (<year>2006</year>) Exploiting asymmetry in hierarchical topic extraction. In: <italic>Proceedings of the 15th ACM International Conference on Information and Knowledge Management</italic> ACM, pp. <fpage>475</fpage>–<lpage>482</lpage>.</mixed-citation></ref><ref id="btz354-B11"><mixed-citation publication-type="other"><person-group person-group-type="author"><name name-style="western"><surname>Harris</surname><given-names>R.S.</given-names></name></person-group> (<year>2007</year>) Improved pairwise alignment of genomic DNA. PhD Thesis, The Pennsylvania State University, PA, USA.</mixed-citation></ref><ref id="btz354-B12"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Hunt</surname><given-names>J.W.</given-names></name>, <name name-style="western"><surname>Szymanski</surname><given-names>T.G.</given-names></name></person-group> (<year>1977</year>)
<article-title>A fast algorithm for computing longest common subsequences</article-title>. <source>Commun. ACM</source>, <volume>20</volume>, <fpage>350</fpage>–<lpage>353</lpage>.</mixed-citation></ref><ref id="btz354-B13"><mixed-citation publication-type="book"><person-group person-group-type="author"><name name-style="western"><surname>Indyk</surname><given-names>P.</given-names></name>, <name name-style="western"><surname>Motwani</surname><given-names>R.</given-names></name></person-group> (<year>1998</year>) <chapter-title>Approximate nearest neighbors: towards removing the curse of dimensionality</chapter-title> In: <source>Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC ’98</source>.
<publisher-name>ACM</publisher-name>,
<publisher-loc>New York, NY, USA</publisher-loc>, pp. <fpage>604</fpage>–<lpage>613</lpage>.</mixed-citation></ref><ref id="btz354-B14"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Jaffe</surname><given-names>D.B.</given-names></name></person-group><etal>et al</etal> (<year>2003</year>)
<article-title>Whole-genome sequence assembly for mammalian genomes: Arachne 2</article-title>. <source>Genome Res</source>., <volume>13</volume>, <fpage>91</fpage>–<lpage>96</lpage>.<pub-id pub-id-type="pmid">12529310</pub-id></mixed-citation></ref><ref id="btz354-B15"><mixed-citation publication-type="book"><person-group person-group-type="author"><name name-style="western"><surname>Jain</surname><given-names>C.</given-names></name></person-group><etal>et al</etal> (<year>2017</year>) <chapter-title>A fast approximate algorithm for mapping long reads to large reference databases</chapter-title> In: <person-group person-group-type="editor"><name name-style="western"><surname>Sahinalp</surname><given-names>S.C.</given-names></name></person-group> (ed.) <source>Research in Computational Molecular Biology</source>.
<publisher-name>Springer International Publishing, Cham</publisher-name>, pp. <fpage>66</fpage>–<lpage>81</lpage>.</mixed-citation></ref><ref id="btz354-B16"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Kushilevitz</surname><given-names>E.</given-names></name></person-group><etal>et al</etal> (<year>2000</year>)
<article-title>Efficient search for approximate nearest neighbor in high dimensional spaces</article-title>. <source>SIAM J. Comput</source>., <volume>30</volume>, <fpage>457</fpage>–<lpage>474</lpage>.</mixed-citation></ref><ref id="btz354-B17"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Langmead</surname><given-names>B.</given-names></name>, <name name-style="western"><surname>Salzberg</surname><given-names>S.L.</given-names></name></person-group> (<year>2012</year>)
<article-title>Fast gapped-read alignment with Bowtie 2</article-title>. <source>Nat. Methods</source>, <volume>9</volume>, <fpage>357</fpage>–<lpage>359</lpage>.<pub-id pub-id-type="pmid">22388286</pub-id></mixed-citation></ref><ref id="btz354-B18"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Lee</surname><given-names>H.</given-names></name></person-group><etal>et al</etal> (<year>2016</year>)
<article-title>Insertion sequence-caused large-scale rearrangements in the genome of <italic>Escherichia coli</italic></article-title>. <source>Nucleic Acids Res</source>., <volume>44</volume>, <fpage>7109</fpage>–<lpage>7119</lpage>.<pub-id pub-id-type="pmid">27431326</pub-id></mixed-citation></ref><ref id="btz354-B19"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Levenshtein</surname><given-names>V.I.</given-names></name></person-group> (<year>1966</year>)
<article-title>Binary codes capable of correcting deletions, insertions, and reversals</article-title>. In: <source>Soviet Physics Doklady</source>, Vol. 10, pp. <fpage>707</fpage>–<lpage>710</lpage>.</mixed-citation></ref><ref id="btz354-B20"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Li</surname><given-names>H.</given-names></name>, <name name-style="western"><surname>Durbin</surname><given-names>R.</given-names></name></person-group> (<year>2010</year>)
<article-title>Fast and accurate long-read alignment with Burrows–Wheeler transform</article-title>. <source>Bioinformatics</source>, <volume>26</volume>, <fpage>589</fpage>–<lpage>595</lpage>.<pub-id pub-id-type="pmid">20080505</pub-id></mixed-citation></ref><ref id="btz354-B21"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Liu</surname><given-names>C.-M.</given-names></name></person-group><etal>et al</etal> (<year>2012</year>)
<article-title>SOAP3: ultra-fast GPU-based parallel alignment tool for short reads</article-title>. <source>Bioinformatics (Oxford, England)</source>, <volume>28</volume>, <fpage>878</fpage>–<lpage>879</lpage>.</mixed-citation></ref><ref id="btz354-B22"><mixed-citation publication-type="other"><person-group person-group-type="author"><name name-style="western"><surname>Luo</surname><given-names>C.</given-names></name>, <name name-style="western"><surname>Shrivastava</surname><given-names>A.</given-names></name></person-group> (<year>2017</year>) SSH (sketch, shingle, & hash) for indexing massive-scale time series. In: <italic>NIPS 2016 Time Series Workshop</italic>, pp. <fpage>38</fpage>–<lpage>58</lpage>.</mixed-citation></ref><ref id="btz354-B24"><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>2018</year>)
<article-title>MUMmer4: a fast and versatile genome alignment system</article-title>. <source>PLOS Comput. Biol</source>., <volume>14</volume>, e1005944.</mixed-citation></ref><ref id="btz354-B26"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Myers</surname><given-names>E.W.</given-names></name></person-group><etal>et al</etal> (<year>2000</year>)
<article-title>A whole-genome assembly of <italic>Drosophila</italic></article-title>. <source>Science</source>, <volume>287</volume>, <fpage>2196</fpage>–<lpage>2204</lpage>.<pub-id pub-id-type="pmid">10731133</pub-id></mixed-citation></ref><ref id="btz354-B27"><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="btz354-B28"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Ostrovsky</surname><given-names>R.</given-names></name>, <name name-style="western"><surname>Rabani</surname><given-names>Y.</given-names></name></person-group> (<year>2007</year>)
<article-title>Low distortion embeddings for edit distance</article-title>. <source>J. ACM</source>, <volume>54</volume>, <fpage>218</fpage>–<lpage>224</lpage>.</mixed-citation></ref><ref id="btz354-B29"><mixed-citation publication-type="other"><person-group person-group-type="author"><name name-style="western"><surname>Raff</surname><given-names>E.</given-names></name>, <name name-style="western"><surname>Nicholas</surname><given-names>C.</given-names></name></person-group> (<year>2017</year>) Malware classification and class imbalance via stochastic hashed LZJD. In: <italic>Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security</italic> ACM, pp. <fpage>111</fpage>–<lpage>120</lpage>.</mixed-citation></ref><ref id="btz354-B30"><mixed-citation publication-type="other"><person-group person-group-type="author"><name name-style="western"><surname>Shrivastava</surname><given-names>A.</given-names></name></person-group> (<year>2016</year>) Simple and efficient weighted minwise hashing. In: <italic>Advances in Neural Information Processing Systems</italic>, pp. <fpage>1498</fpage>–<lpage>1506</lpage>.</mixed-citation></ref><ref id="btz354-B31"><mixed-citation publication-type="journal">van Aardenne-Ehrenfest and de Bruijn (<year>1951</year>)
<article-title>Circuits and trees in oriented linear graphs. Simon Stevin : Wis-en Natuurkundig Tijdschrift</article-title>. <source>Tschr</source>., <volume>28</volume>, <fpage>203</fpage>–<lpage>217</lpage>.</mixed-citation></ref><ref id="btz354-B32"><mixed-citation publication-type="other"><person-group person-group-type="author"><name name-style="western"><surname>Wu</surname><given-names>W.</given-names></name></person-group><etal>et al</etal> (<year>2017</year>) Consistent weighted sampling made more practical. In: <italic>Proceedings of the 26th International Conference on World Wide Web, WWW ’17</italic>. Republic and Canton of Geneva, Switzerland, pp. 1035–1043. International World Wide Web Conferences Steering Committee.</mixed-citation></ref><ref id="btz354-B33"><mixed-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Zhao</surname><given-names>M.</given-names></name></person-group><etal>et al</etal> (<year>2013</year>)
<article-title>SSW Library: an SIMD Smith-Waterman C/C++ library for use in genomic applications</article-title>. <source>PLoS One</source>, <volume>8</volume>, <fpage>e82138</fpage>.<pub-id pub-id-type="pmid">24324759</pub-id></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 000B23 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Pmc/Corpus/biblio.hfd -nk 000B23 | 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:6612865
|texte= Locality-sensitive hashing for the edit distance
}}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Pmc/Corpus/RBID.i -Sk "pubmed:31510667" \
| HfdSelect -Kh $EXPLOR_AREA/Data/Pmc/Corpus/biblio.hfd \
| NlmPubMed2Wicri -a MersV1
| This area was generated with Dilib version V0.6.33. |  |