k-mismatch with don't cares

R Clifford, K Efremenko, E Porat, A Rothschild

Research output: Contribution to journalArticle (Academic Journal)peer-review

21 Citations (Scopus)

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 contributionk-mismatch with don't cares
Original languageEnglish
Pages (from-to)151 - 162
Number of pages12
JournalLecture Notes in Computer Science
DOIs
Publication statusPublished - Oct 2007

Bibliographical note

ISBN: 9783540755197
Publisher: 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 '<i>k</i>-mismatch with don't cares'. Together they form a unique fingerprint.

Cite this