Circular pattern matching with k mismatches

Panagiotis Charalampopoulos; Tomasz Kociumaka; Solon P. Pissis; Jakub Radoszewski; Wojciech Rytter; Juliusz Straszyński; Tomasz Waleń; Wiktor Zuba

doi:10.1016/j.jcss.2020.07.003

Circular pattern matching with k mismatches

Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis^*, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, Wiktor Zuba

^*Corresponding author for this work

Research output: Contribution to Journal › Article › Academic › peer-review

Abstract

We consider the circular pattern matching with k mismatches (k-CPM) problem in which one is to compute the minimal Hamming distance of every length-m substring of T and any cyclic rotation of P, if this distance is no more than k. It is a variation of the well-studied k-mismatch problem. A multitude of papers has been devoted to solving the k-CPM problem, but only average-case upper bounds are known. In this paper, we present the first non-trivial worst-case upper bounds for this problem. Specifically, we show an O(nk)-time algorithm and an [Formula presented]-time algorithm. The latter algorithm applies in an extended way a technique that was very recently developed for the k-mismatch problem Bringmann et al. (2019) [10]. A preliminary version of this work appeared at FCT 2019 [35]. In this version we improve the time complexity of the second algorithm from [Formula presented] to [Formula presented].

Original language	English
Pages (from-to)	73-85
Number of pages	13
Journal	Journal of Computer and System Sciences
Volume	115
Early online date	29 Jul 2020
DOIs	https://doi.org/10.1016/j.jcss.2020.07.003
Publication status	Published - Feb 2021

Funding

Supported by the ERC grant TOTAL agreement no. 677651, a Studentship from the Faculty of Natural and Mathematical Sciences at King's College London and an A.G. Leventis Foundation Educational Grant.Supported by ISF grants no. 1278/16 and 1926/19, a BSF grant no. 2018364, and an ERC grant MPM (no. 683064) under the EU's Horizon 2020 Research and Innovation Programme.Supported by the ?Algorithms for text processing with errors and uncertainties? project carried out within the HOMING program of the Foundation for Polish Science co-financed by the European Union under the European Regional Development Fund, project no. POIR.04.04.00-00-24BA/16.Supported by the Polish National Science Center, grant no. 2018/31/D/ST6/03991.

Funders	Funder number
EU's Horizon 2020
Faculty of Natural and Mathematical Sciences at King's College London
Horizon 2020 Framework Programme	677651, 683064
European Commission
European Research Council
United States-Israel Binational Science Foundation	2018364
Fundacja na rzecz Nauki Polskiej
Israel Science Foundation	1926/19, 1278/16
A.G. Leventis Foundation
Narodowe Centrum Nauki	2018/31/D/ST6/03991
European Regional Development Fund	POIR.04.04.00-00-24BA/16

Keywords

Approximate pattern matching
Circular pattern matching
k-mismatch problem

Access to Document

10.1016/j.jcss.2020.07.003

Persistent URL (handle)

Copy link address

Cite this

@article{ad9aa4971c9f4f84a13d8715443fb2f2,

title = "Circular pattern matching with k mismatches",

abstract = "We consider the circular pattern matching with k mismatches (k-CPM) problem in which one is to compute the minimal Hamming distance of every length-m substring of T and any cyclic rotation of P, if this distance is no more than k. It is a variation of the well-studied k-mismatch problem. A multitude of papers has been devoted to solving the k-CPM problem, but only average-case upper bounds are known. In this paper, we present the first non-trivial worst-case upper bounds for this problem. Specifically, we show an O(nk)-time algorithm and an [Formula presented]-time algorithm. The latter algorithm applies in an extended way a technique that was very recently developed for the k-mismatch problem Bringmann et al. (2019) [10]. A preliminary version of this work appeared at FCT 2019 [35]. In this version we improve the time complexity of the second algorithm from [Formula presented] to [Formula presented].",

keywords = "Approximate pattern matching, Circular pattern matching, k-mismatch problem",

author = "Panagiotis Charalampopoulos and Tomasz Kociumaka and Pissis, {Solon P.} and Jakub Radoszewski and Wojciech Rytter and Juliusz Straszy{\'n}ski and Tomasz Wale{\'n} and Wiktor Zuba",

year = "2021",

month = feb,

doi = "10.1016/j.jcss.2020.07.003",

language = "English",

volume = "115",

pages = "73--85",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Elsevier",

}

TY - JOUR

T1 - Circular pattern matching with k mismatches

AU - Charalampopoulos, Panagiotis

AU - Kociumaka, Tomasz

AU - Pissis, Solon P.

AU - Radoszewski, Jakub

AU - Rytter, Wojciech

AU - Straszyński, Juliusz

AU - Waleń, Tomasz

AU - Zuba, Wiktor

PY - 2021/2

Y1 - 2021/2

N2 - We consider the circular pattern matching with k mismatches (k-CPM) problem in which one is to compute the minimal Hamming distance of every length-m substring of T and any cyclic rotation of P, if this distance is no more than k. It is a variation of the well-studied k-mismatch problem. A multitude of papers has been devoted to solving the k-CPM problem, but only average-case upper bounds are known. In this paper, we present the first non-trivial worst-case upper bounds for this problem. Specifically, we show an O(nk)-time algorithm and an [Formula presented]-time algorithm. The latter algorithm applies in an extended way a technique that was very recently developed for the k-mismatch problem Bringmann et al. (2019) [10]. A preliminary version of this work appeared at FCT 2019 [35]. In this version we improve the time complexity of the second algorithm from [Formula presented] to [Formula presented].

AB - We consider the circular pattern matching with k mismatches (k-CPM) problem in which one is to compute the minimal Hamming distance of every length-m substring of T and any cyclic rotation of P, if this distance is no more than k. It is a variation of the well-studied k-mismatch problem. A multitude of papers has been devoted to solving the k-CPM problem, but only average-case upper bounds are known. In this paper, we present the first non-trivial worst-case upper bounds for this problem. Specifically, we show an O(nk)-time algorithm and an [Formula presented]-time algorithm. The latter algorithm applies in an extended way a technique that was very recently developed for the k-mismatch problem Bringmann et al. (2019) [10]. A preliminary version of this work appeared at FCT 2019 [35]. In this version we improve the time complexity of the second algorithm from [Formula presented] to [Formula presented].

KW - Approximate pattern matching

KW - Circular pattern matching

KW - k-mismatch problem

UR - http://www.scopus.com/inward/record.url?scp=85088923630&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85088923630&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2020.07.003

DO - 10.1016/j.jcss.2020.07.003

M3 - Article

AN - SCOPUS:85088923630

SN - 0022-0000

VL - 115

SP - 73

EP - 85

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

ER -

Circular pattern matching with k mismatches

Abstract

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this