## Abstract

We give the first non-trivial algorithms for the $k$-mismatch pattern matching problem with don't cares. Given a text $t$ of length $n$ and a pattern $p$ of length $m$ with don't care symbols and a bound $k$, our algorithms find all the places that the pattern matches the text with at most $k$ mismatches. We first give an $O(n(k+\log{m}\log\log{m})\log{m})$ time randomised solution which finds the correct answer with high probability. We then present a new deterministic $O(nk^2\log^3{m})$ time solution that uses tools developed for group testing and an approach based on $k$-selectors that runs in $O(nk polylog(m))$ time. Further, the location of the mismatches at each alignment is also given at no extra cost.

Translated title of the contribution | k-mismatch with don't cares |
---|---|

Original language | English |

Pages (from-to) | 151 - 162 |

Number of pages | 12 |

Journal | Lecture Notes in Computer Science |

DOIs | |

Publication status | Published - Oct 2007 |

### Bibliographical note

ISBN: 9783540755197Publisher: Springer

Name and Venue of Conference: 15th Annual European Symposium on Algorithms (ESA 2007), Eilat, Israel, 8-10 October

## Fingerprint

Dive into the research topics of '*k*-mismatch with don't cares'. Together they form a unique fingerprint.