Longest common substrings with k mismatches

Research output: Contribution to journalArticleScientificpeer-review

Standard

Longest common substrings with k mismatches. / Flouri, Tomas; Giaquinta, Emanuele; Kobert, Kassian; Ukkonen, Esko.

In: Information Processing Letters, Vol. 115, No. 6-8, 2015, p. 643-647.

Research output: Contribution to journalArticleScientificpeer-review

Harvard

Flouri, T, Giaquinta, E, Kobert, K & Ukkonen, E 2015, 'Longest common substrings with k mismatches' Information Processing Letters, vol. 115, no. 6-8, pp. 643-647. https://doi.org/10.1016/j.ipl.2015.03.006

APA

Flouri, T., Giaquinta, E., Kobert, K., & Ukkonen, E. (2015). Longest common substrings with k mismatches. Information Processing Letters, 115(6-8), 643-647. https://doi.org/10.1016/j.ipl.2015.03.006

Vancouver

Author

Flouri, Tomas ; Giaquinta, Emanuele ; Kobert, Kassian ; Ukkonen, Esko. / Longest common substrings with k mismatches. In: Information Processing Letters. 2015 ; Vol. 115, No. 6-8. pp. 643-647.

Bibtex - Download

@article{5914df4c361e479ba4ab73abfe13c0fe,
title = "Longest common substrings with k mismatches",
abstract = "The longest common substring with k -mismatches problem is to find, given two strings S1S1 and S2S2, a longest substring A1A1 of S1S1 and A2A2 of S2S2 such that the Hamming distance between A1A1 and A2A2 is ≤k . We introduce a practical O(nm)O(nm) time and O(1)O(1) space solution for this problem, where n and m are the lengths of S1S1 and S2S2, respectively. This algorithm can also be used to compute the matching statistics with k -mismatches of S1S1 and S2S2 in O(nm)O(nm) time and O(m)O(m) space. Moreover, we also present a theoretical solution for the k=1k=1 case which runs in O(nlog⁡m)O(nlog⁡m) time, assuming m≤nm≤n, and uses O(m)O(m) space, improving over the existing O(nm)O(nm) time and O(m)O(m) space bound of Babenko and Starikovskaya.",
keywords = "Combinatorial problems, Hamming distance, Longest common substring, String algorithms, Combinatorial problems, Hamming distance, Longest common substring, String algorithms, Combinatorial problems, Hamming distance, Longest common substring, String algorithms",
author = "Tomas Flouri and Emanuele Giaquinta and Kassian Kobert and Esko Ukkonen",
note = "VK: Tarhio, J.",
year = "2015",
doi = "10.1016/j.ipl.2015.03.006",
language = "English",
volume = "115",
pages = "643--647",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",
number = "6-8",

}

RIS - Download

TY - JOUR

T1 - Longest common substrings with k mismatches

AU - Flouri, Tomas

AU - Giaquinta, Emanuele

AU - Kobert, Kassian

AU - Ukkonen, Esko

N1 - VK: Tarhio, J.

PY - 2015

Y1 - 2015

N2 - The longest common substring with k -mismatches problem is to find, given two strings S1S1 and S2S2, a longest substring A1A1 of S1S1 and A2A2 of S2S2 such that the Hamming distance between A1A1 and A2A2 is ≤k . We introduce a practical O(nm)O(nm) time and O(1)O(1) space solution for this problem, where n and m are the lengths of S1S1 and S2S2, respectively. This algorithm can also be used to compute the matching statistics with k -mismatches of S1S1 and S2S2 in O(nm)O(nm) time and O(m)O(m) space. Moreover, we also present a theoretical solution for the k=1k=1 case which runs in O(nlog⁡m)O(nlog⁡m) time, assuming m≤nm≤n, and uses O(m)O(m) space, improving over the existing O(nm)O(nm) time and O(m)O(m) space bound of Babenko and Starikovskaya.

AB - The longest common substring with k -mismatches problem is to find, given two strings S1S1 and S2S2, a longest substring A1A1 of S1S1 and A2A2 of S2S2 such that the Hamming distance between A1A1 and A2A2 is ≤k . We introduce a practical O(nm)O(nm) time and O(1)O(1) space solution for this problem, where n and m are the lengths of S1S1 and S2S2, respectively. This algorithm can also be used to compute the matching statistics with k -mismatches of S1S1 and S2S2 in O(nm)O(nm) time and O(m)O(m) space. Moreover, we also present a theoretical solution for the k=1k=1 case which runs in O(nlog⁡m)O(nlog⁡m) time, assuming m≤nm≤n, and uses O(m)O(m) space, improving over the existing O(nm)O(nm) time and O(m)O(m) space bound of Babenko and Starikovskaya.

KW - Combinatorial problems

KW - Hamming distance

KW - Longest common substring

KW - String algorithms

KW - Combinatorial problems

KW - Hamming distance

KW - Longest common substring

KW - String algorithms

KW - Combinatorial problems

KW - Hamming distance

KW - Longest common substring

KW - String algorithms

UR - http://dx.doi.org/10.1016/j.ipl.2015.03.006

U2 - 10.1016/j.ipl.2015.03.006

DO - 10.1016/j.ipl.2015.03.006

M3 - Article

VL - 115

SP - 643

EP - 647

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 6-8

ER -

ID: 2010307