The k-mismatch problem revisited

DOI10.1137/1.9781611974331.CH142MaRDI QIDQ4575727zbMATH OpenOpenAlexFDO

Authors Raphaël Clifford, Ely Porat, Benjamin Sach, Tatiana Starikovskaya, A. Fontaine

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.00731

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Abstract: We revisit the complexity of one of the most basic problems in pattern matching. In the k-mismatch problem we must compute the Hamming distance between a pattern of length m and every m-length substring of a text of length n, as long as that Hamming distance is at most k. Where the Hamming distance is greater than k at some alignment of the pattern and text, we simply output "No". We study this problem in both the standard offline setting and also as a streaming problem. In the streaming k-mismatch problem the text arrives one symbol at a time and we must give an output before processing any future symbols. Our main results are as follows: 1) Our first result is a deterministic $O(n{k}^{2}logk/m+nextpolylogm)$ time offline algorithm for k-mismatch on a text of length n. This is a factor of k improvement over the fastest previous result of this form from SODA 2000 by Amihood Amir et al. 2) We then give a randomised and online algorithm which runs in the same time complexity but requires only $O(k^{2}extpolylogm)$ space in total. 3) Next we give a randomised $(1+epsilon)$-approximation algorithm for the streaming k-mismatch problem which uses $O(k^{2}extpolylogm/epsilo{n}^2)$ space and runs in $O(extpolylogm/epsilo{n}^2)$ worst-case time per arriving symbol. 4) Finally we combine our new results to derive a randomised $O(k^{2}extpolylogm)$ space algorithm for the streaming k-mismatch problem which runs in $O(sqrtklogk+extpolylogm)$ worst-case time per arriving symbol. This improves the best previous space complexity for streaming k-mismatch from FOCS 2009 by Benny Porat and Ely Porat by a factor of k. We also improve the time complexity of this previous result by an even greater factor to match the fastest known offline algorithm (up to logarithmic factors).

Recommendations

• The streaming \(k\)-mismatch problem
• Streaming \(k\)-mismatch with error correcting and applications
• scientific article; zbMATH DE number 1445379
• Fast algorithms for approximately counting mismatches
• Faster algorithms for string matching with k mismatches

Cited in

(37)

• Fast algorithms for approximately counting mismatches
• Longest common extension
• Streaming pattern matching with \(d\) wildcards
• Recent advances in text-to-pattern distance algorithms
• Streaming dictionary matching with mismatches
• Streaming \(k\)-mismatch with error correcting and applications
• Tight tradeoffs for real-time approximation of longest palindromes in streams
• Pattern matching in multiple streams
• Hashing and indexing: succinct data structures and smoothed analysis
• Automata theory on sliding windows
• On pattern matching with \(k\) mismatches and few don't cares
• A Black Box for Online Approximate Pattern Matching
• k-Mismatch with Don’t Cares
• Pseudo-realtime pattern matching: closing the gap
• Streaming periodicity with mismatches
• Towards unified approximate pattern matching for Hamming and \(L_1\) distance
• Approximating Approximate Pattern Matching
• Streaming Dictionary Matching with Mismatches
• Searching Long Repeats in Streams
• Visibly pushdown languages over sliding windows
• Real-Time Streaming Multi-Pattern Search for Constant Alphabet
• Streaming for aibohphobes: longest palindrome with mismatches
• The streaming \(k\)-mismatch problem
• Faster algorithms for 1-mappability of a sequence
• Circular pattern matching with \(k\) mismatches
• Circular pattern matching with k mismatches
• Faster algorithms for 1-mappability of a sequence
• scientific article; zbMATH DE number 7758337 (Why is no real title available?)
• scientific article; zbMATH DE number 7758348 (Why is no real title available?)
• Approximate circular pattern matching under edit distance
• Substring complexity in sublinear space
• Approximate circular pattern matching
• Regular languages in the sliding window model
• String searching with mismatches using AVX2 and AVX-512 instructions
• Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching
• A black box for online approximate pattern matching
• Pattern matching with mismatches and wildcards

This page was built for publication: The \(k\)-mismatch problem revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575727)