License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-22442
URL: http://drops.dagstuhl.de/opus/volltexte/2009/2244/
Go to the corresponding Portal |
Clifford, Raphael ;
Efremo, Klim ;
Porat, Ely ;
Rotschild, Amir
Pattern matching with don't cares and few errors
Abstract
We present solutions 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 \Theta(n(k + logmlog k) log n) time randomised algorithm which finds
the correct answer with high probability. We then present a new deter-
ministic \Theta(nk^2 log^m)time solution that uses tools originally developed
for group testing. Taking our derandomisation approach further we de-
velop an approach based on k-selectors that runs in \Theta(nk polylogm) time.
Further, in each case the location of the mismatches at each alignment is
also given at no extra cost.
BibTeX - Entry
@InProceedings{clifford_et_al:DSP:2009:2244,
author = {Raphael Clifford and Klim Efremo and Ely Porat and Amir Rotschild},
title = {Pattern matching with don't cares and few errors},
booktitle = {Search Methodologies },
year = {2009},
editor = {Rudolf Ahlswede and Ferdinando Cicalese and Ugo Vaccaro},
number = {09281},
series = {Dagstuhl Seminar Proceedings},
ISSN = {1862-4405},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/2244},
annote = {Keywords: Prime Numbers, Group Testing, Streaming, Pattern Matching}
}
Keywords: |
|
Prime Numbers, Group Testing, Streaming, Pattern Matching |
Seminar: |
|
09281 - Search Methodologies |
Issue Date: |
|
2009 |
Date of publication: |
|
10.11.2009 |