Skip to content

The streaming k-mismatch problem

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Original languageEnglish
Title of host publication30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)
Publisher or commissioning bodySociety for Industrial and Applied Mathematics
Pages1106-1125
Number of pages21
ISBN (Electronic)9781611975482
DOIs
DateAccepted/In press - 27 Sep 2018
DateE-pub ahead of print - 6 Jan 2019
DatePublished (current) - 2019

Abstract

We consider the streaming complexity of a fundamental task in approximate pattern matching: the k-mismatch problem. In this problem, we must compute Hamming distances between a pattern of length n and all length-n substrings of a text for which the Hamming distance does not exceed a given threshold k. In our problem formulation, we report not only the Hamming distance but also, on demand, the full mismatch information, that is the list of mismatched pairs of symbols and their indices. The twin challenges of streaming pattern matching derive from the need both to achieve small working space and also to guarantee that every arriving input symbol is processed quickly. We present a streaming algorithm for the k-mismatch problem which uses O(k log n log n/k) bits of space and spends O (log n/k ( √ (k log k) +log^3 n)) time on each symbol of the input stream. In our formulation, the pattern is also in the stream,arriving directly before the text. The running time almost matches the classic offline solution [5] and the space usage is within a logarithmic factor of optimal. Our new algorithm therefore effectively resolves and also extends a problem first introduced in FOCS’09 [38]. En route to this solution, we also give a deterministic O(k(log nk + log |Σ|))-bit encoding of all the alignments with Hamming distance at most k of a length-n pattern within a text of length O(n). This secondary result provides an optimal solution to a natural encoding problem which may be of independent interest.

Download statistics

No data available

Documents

Documents

  • Full-text PDF (accepted author manuscript)

    Rights statement: This is the author accepted manuscript (AAM). The final published version (version of record) is available online via SIAM at https://epubs.siam.org/doi/10.1137/1.9781611975482.68 . Please refer to any applicable terms of use of the publisher.

    Accepted author manuscript, 518 KB, PDF-document

DOI

View research connections

Related faculties, schools or groups