License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2020.18
URN: urn:nbn:de:0030-drops-121437
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12143/
Kędzierski, Aleksander ;
Radoszewski, Jakub
k-Approximate Quasiperiodicity under Hamming and Edit Distance
Abstract
Quasiperiodicity in strings was introduced almost 30 years ago as an extension of string periodicity. The basic notions of quasiperiodicity are cover and seed. A cover of a text T is a string whose occurrences in T cover all positions of T. A seed of text T is a cover of a superstring of T. In various applications exact quasiperiodicity is still not sufficient due to the presence of errors. We consider approximate notions of quasiperiodicity, for which we allow approximate occurrences in T with a small Hamming, Levenshtein or weighted edit distance.
In previous work Sip et al. (2002) and Christodoulakis et al. (2005) showed that computing approximate covers and seeds, respectively, under weighted edit distance is NP-hard. They, therefore, considered restricted approximate covers and seeds which need to be factors of the original string T and presented polynomial-time algorithms for computing them. Further algorithms, considering approximate occurrences with Hamming distance bounded by k, were given in several contributions by Guth et al. They also studied relaxed approximate quasiperiods that do not need to cover all positions of T.
In case of large data the exponents in polynomial time complexity play a crucial role. We present more efficient algorithms for computing restricted approximate covers and seeds. In particular, we improve upon the complexities of many of the aforementioned algorithms, also for relaxed quasiperiods. Our solutions are especially efficient if the number (or total cost) of allowed errors is bounded. We also show NP-hardness of computing non-restricted approximate covers and seeds under Hamming distance.
Approximate covers were studied in three recent contributions at CPM over the last three years. However, these works consider a different definition of an approximate cover of T, that is, the shortest exact cover of a string T' with the smallest Hamming distance from T.
BibTeX - Entry
@InProceedings{kdzierski_et_al:LIPIcs:2020:12143,
author = {Aleksander Kędzierski and Jakub Radoszewski},
title = {{k-Approximate Quasiperiodicity under Hamming and Edit Distance}},
booktitle = {31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)},
pages = {18:1--18:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-149-8},
ISSN = {1868-8969},
year = {2020},
volume = {161},
editor = {Inge Li G{\o}rtz and Oren Weimann},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12143},
URN = {urn:nbn:de:0030-drops-121437},
doi = {10.4230/LIPIcs.CPM.2020.18},
annote = {Keywords: approximate cover, approximate seed, enhanced cover, Hamming distance, edit distance}
}
|
Keywords: |
|
approximate cover, approximate seed, enhanced cover, Hamming distance, edit distance |
|
Collection: |
|
31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
09.06.2020 |
