Streaming K-Mismatch with Error Correcting and Applications

We present a new streaming algorithm for the k-Mismatch problem, one of the most basic problems in pattern matching. Given a pattern and a text, the task is to find all substrings of the text that are at the Hamming distance at most k from the pattern. Our algorithm is enhanced with an important new feature called Error Correcting, and its complexities for k = 1 and for a general k match those of the best known solutions for the k-Mismatch problem from FOCS 2009 and SODA 2016. As a corollary we develop a series of streaming algorithms for pattern matching on weighted strings, which are a commonly used representation of uncertain sequences in molecular biology.