Loading...
Please wait, while we are loading the content...
Similar Documents
Streaming k-mismatch with error correcting and applications
| Content Provider | arXiv |
|---|---|
| Author | Radoszewski, Jakub Starikovskaya, Tatiana |
| Date of Submission | 2019-04-23 |
| Abstract | 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$ are comparable to those of the solutions for the $k$-Mismatch problem by Porat and Porat (FOCS 2009) and Clifford et al. (SODA 2016). In parallel to our research, a yet more efficient algorithm for the $k$-Mismatch problem with the Error Correcting feature was developed by Clifford et al. (SODA 2019). Using the new feature and recent work on streaming Multiple Pattern Matching 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. We also show that these algorithms are space-optimal up to polylog factors. A preliminary version of this work was published at DCC 2017 conference. |
| Related Links | https://arxiv.org/pdf/1607.05626.pdf |
| arXiv | 1607.05626 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Computer Science - Data Structures and Algorithms Computer Science |
| Content Type | Text |
| Resource Type | Article |
| Subject | Computer Science |
