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

pdf-format:
09281.PoratEly.Paper.2244.pdf (0.3 MB)

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

DROPS-Home | Fulltext Search | Imprint Published by LZI