Optimal bounds for computing α-gapped repeats

Max Crochemore; Roman Kolpakov; Gregory Kucherov

doi:10.1007/978-3-319-30000-9_19

Optimal bounds for computing α-gapped repeats

Max Crochemore, Roman Kolpakov, Gregory Kucherov^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

17 Citations (Scopus)

Abstract

Following (Kolpakov et al., 2013; Gawrychowski and Manea, 2015), we continue the study of α-gapped repeats in strings, defined as factors uvu with |uv| ≤ α|u|. Our main result is the O(αn) bound on the number of maximal α-gapped repeats in a string of length n, previously proved to be O(α²n) in (Kolpakov et al., 2013). For a closely related notion of maximal δ-subrepetition (maximal factors of exponent between 1 + δ and 2), our result implies the O(n/δ) bound on their number, which improves the bound of (Kolpakov et al., 2010) by a log n factor. We also prove an algorithmic time bound O(αn+S) (S size of the output) for computing all maximal α-gapped repeats. Our solution, inspired by (Gawrychowski and Manea, 2015), is different from the recently published proof by (Tanimura et al., 2015) of the same bound. Together with our bound on S, this implies an O(αn)-time algorithm for computing all maximal α-gapped repeats.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer‐Verlag Berlin Heidelberg
Pages	245-255
Number of pages	11
Volume	9618
ISBN (Print)	9783319299990
DOIs	https://doi.org/10.1007/978-3-319-30000-9_19
Publication status	Published - 26 Feb 2016
Event	10th International Conference on Language and Automata Theory and Applications, LATA 2016 - Prague, Czech Republic Duration: 14 Mar 2016 → 18 Mar 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9618
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	10th International Conference on Language and Automata Theory and Applications, LATA 2016
Country/Territory	Czech Republic
City	Prague
Period	14/03/2016 → 18/03/2016

Access to Document

10.1007/978-3-319-30000-9_19

Cite this

Crochemore, M., Kolpakov, R., & Kucherov, G. (2016). Optimal bounds for computing α-gapped repeats. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 9618, pp. 245-255). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9618). Springer‐Verlag Berlin Heidelberg. https://doi.org/10.1007/978-3-319-30000-9_19

Crochemore, Max ; Kolpakov, Roman ; Kucherov, Gregory. / Optimal bounds for computing α-gapped repeats. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 9618 Springer‐Verlag Berlin Heidelberg, 2016. pp. 245-255 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{db83e802beee4bf892d8d72b93b610b6,

title = "Optimal bounds for computing α-gapped repeats",

abstract = "Following (Kolpakov et al., 2013; Gawrychowski and Manea, 2015), we continue the study of α-gapped repeats in strings, defined as factors uvu with |uv| ≤ α|u|. Our main result is the O(αn) bound on the number of maximal α-gapped repeats in a string of length n, previously proved to be O(α2n) in (Kolpakov et al., 2013). For a closely related notion of maximal δ-subrepetition (maximal factors of exponent between 1 + δ and 2), our result implies the O(n/δ) bound on their number, which improves the bound of (Kolpakov et al., 2010) by a log n factor. We also prove an algorithmic time bound O(αn+S) (S size of the output) for computing all maximal α-gapped repeats. Our solution, inspired by (Gawrychowski and Manea, 2015), is different from the recently published proof by (Tanimura et al., 2015) of the same bound. Together with our bound on S, this implies an O(αn)-time algorithm for computing all maximal α-gapped repeats.",

author = "Max Crochemore and Roman Kolpakov and Gregory Kucherov",

year = "2016",

month = feb,

day = "26",

doi = "10.1007/978-3-319-30000-9_19",

language = "English",

isbn = "9783319299990",

volume = "9618",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer‐Verlag Berlin Heidelberg",

pages = "245--255",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

note = "10th International Conference on Language and Automata Theory and Applications, LATA 2016 ; Conference date: 14-03-2016 Through 18-03-2016",

}

Crochemore, M, Kolpakov, R & Kucherov, G 2016, Optimal bounds for computing α-gapped repeats. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). vol. 9618, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9618, Springer‐Verlag Berlin Heidelberg, pp. 245-255, 10th International Conference on Language and Automata Theory and Applications, LATA 2016, Prague, Czech Republic, 14/03/2016. https://doi.org/10.1007/978-3-319-30000-9_19

Optimal bounds for computing α-gapped repeats. / Crochemore, Max; Kolpakov, Roman; Kucherov, Gregory.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 9618 Springer‐Verlag Berlin Heidelberg, 2016. p. 245-255 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9618).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

TY - CHAP

T1 - Optimal bounds for computing α-gapped repeats

AU - Crochemore, Max

AU - Kolpakov, Roman

AU - Kucherov, Gregory

PY - 2016/2/26

Y1 - 2016/2/26

N2 - Following (Kolpakov et al., 2013; Gawrychowski and Manea, 2015), we continue the study of α-gapped repeats in strings, defined as factors uvu with |uv| ≤ α|u|. Our main result is the O(αn) bound on the number of maximal α-gapped repeats in a string of length n, previously proved to be O(α2n) in (Kolpakov et al., 2013). For a closely related notion of maximal δ-subrepetition (maximal factors of exponent between 1 + δ and 2), our result implies the O(n/δ) bound on their number, which improves the bound of (Kolpakov et al., 2010) by a log n factor. We also prove an algorithmic time bound O(αn+S) (S size of the output) for computing all maximal α-gapped repeats. Our solution, inspired by (Gawrychowski and Manea, 2015), is different from the recently published proof by (Tanimura et al., 2015) of the same bound. Together with our bound on S, this implies an O(αn)-time algorithm for computing all maximal α-gapped repeats.

AB - Following (Kolpakov et al., 2013; Gawrychowski and Manea, 2015), we continue the study of α-gapped repeats in strings, defined as factors uvu with |uv| ≤ α|u|. Our main result is the O(αn) bound on the number of maximal α-gapped repeats in a string of length n, previously proved to be O(α2n) in (Kolpakov et al., 2013). For a closely related notion of maximal δ-subrepetition (maximal factors of exponent between 1 + δ and 2), our result implies the O(n/δ) bound on their number, which improves the bound of (Kolpakov et al., 2010) by a log n factor. We also prove an algorithmic time bound O(αn+S) (S size of the output) for computing all maximal α-gapped repeats. Our solution, inspired by (Gawrychowski and Manea, 2015), is different from the recently published proof by (Tanimura et al., 2015) of the same bound. Together with our bound on S, this implies an O(αn)-time algorithm for computing all maximal α-gapped repeats.

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

U2 - 10.1007/978-3-319-30000-9_19

DO - 10.1007/978-3-319-30000-9_19

M3 - Chapter

AN - SCOPUS:84960422686

SN - 9783319299990

VL - 9618

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 245

EP - 255

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

PB - Springer‐Verlag Berlin Heidelberg

T2 - 10th International Conference on Language and Automata Theory and Applications, LATA 2016

Y2 - 14 March 2016 through 18 March 2016

ER -

Crochemore M, Kolpakov R, Kucherov G. Optimal bounds for computing α-gapped repeats. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 9618. Springer‐Verlag Berlin Heidelberg. 2016. p. 245-255. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-30000-9_19

Optimal bounds for computing α-gapped repeats

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Succinct and compressed data structures for string indexing and processing

Succinct Structures for Parametric sequence Alignment

Cite this

Optimal bounds for computing α-gapped repeats

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Projects

Succinct and compressed data structures for string indexing and processing

Succinct Structures for Parametric sequence Alignment

Cite this