Efficient algorithms for shortest partial seeds in words

Tomasz Kociumaka; Solon P. Pissis; Jakub Radoszewski; Wojciech Rytter; Tomasz Waleń

doi:10.1016/j.tcs.2016.11.035

Efficient algorithms for shortest partial seeds in words

Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski^*, Wojciech Rytter, Tomasz Waleń

^*Corresponding author for this work

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

Abstract

A factor u of a word w is a cover of w if every position in w lies within some occurrence of u in w. A factor u is a seed of w if it is a cover of a superstring of w. Covers and seeds extend the classical notions of periodicity. We introduce a new notion of α-partial seed, that is, a factor covering as a seed at least α positions in a given word. We use the Cover Suffix Tree, recently introduced in the context of α-partial covers (Kociumaka et al., 2015, [13]); an O(nlog⁡n)-time algorithm constructing such a tree is known. However, it appears that partial seeds are more complicated than partial covers—our algorithms require algebraic manipulations of special functions related to edges of the modified Cover Suffix Tree and the border array. We present a procedure for computing shortest α-partial seeds that works in O(n) time if the Cover Suffix Tree is already given. This is a full version, which includes all the proofs, of a paper that appeared at CPM 2014 [1].

Original language	English
Pages (from-to)	139-147
Number of pages	9
Journal	Theoretical Computer Science
Volume	710
DOIs	https://doi.org/10.1016/j.tcs.2016.11.035
Publication status	Published - 1 Feb 2018
Externally published	Yes

Funding

Tomasz Kociumaka is supported by Polish budget funds for science in 2013–2017 as a research project under the ‘Diamond Grant’ program ( Ministry of Science and Higher Education , Republic of Poland, grant No. 0179/DIA/2013/42 ). Jakub Radoszewski receives financial support of Foundation for Polish Science and is supported by the Polish Ministry of Science and Higher Education under the ‘Iuventus Plus’ program in 2015–2016 grant No. 0392/IP3/2015/73 . Wojciech Rytter is supported by grant No. NCN2014/13/B/ST6/00770 of the National Science Centre .

Funders	Funder number
Polish Ministry of Science and Higher Education	NCN2014/13/B/ST6/00770, 0392/IP3/2015/73
Narodowe Centrum Nauki
Ministerstwo Nauki i Szkolnictwa WyÅ¼szego	0179/DIA/2013/42

Keywords

Algorithms on strings
Cover
Quasiperiodicity
Seed
Suffix tree

Access to Document

10.1016/j.tcs.2016.11.035

Persistent URL (handle)

Persistent link

Cite this

@article{e273e3d120044ac688966b567062d488,

title = "Efficient algorithms for shortest partial seeds in words",

abstract = "A factor u of a word w is a cover of w if every position in w lies within some occurrence of u in w. A factor u is a seed of w if it is a cover of a superstring of w. Covers and seeds extend the classical notions of periodicity. We introduce a new notion of α-partial seed, that is, a factor covering as a seed at least α positions in a given word. We use the Cover Suffix Tree, recently introduced in the context of α-partial covers (Kociumaka et al., 2015, [13]); an O(nlog⁡n)-time algorithm constructing such a tree is known. However, it appears that partial seeds are more complicated than partial covers—our algorithms require algebraic manipulations of special functions related to edges of the modified Cover Suffix Tree and the border array. We present a procedure for computing shortest α-partial seeds that works in O(n) time if the Cover Suffix Tree is already given. This is a full version, which includes all the proofs, of a paper that appeared at CPM 2014 [1].",

keywords = "Algorithms on strings, Cover, Quasiperiodicity, Seed, Suffix tree",

author = "Tomasz Kociumaka and Pissis, {Solon P.} and Jakub Radoszewski and Wojciech Rytter and Tomasz Wale{\'n}",

year = "2018",

month = feb,

day = "1",

doi = "10.1016/j.tcs.2016.11.035",

language = "English",

volume = "710",

pages = "139--147",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - Efficient algorithms for shortest partial seeds in words

AU - Kociumaka, Tomasz

AU - Pissis, Solon P.

AU - Radoszewski, Jakub

AU - Rytter, Wojciech

AU - Waleń, Tomasz

PY - 2018/2/1

Y1 - 2018/2/1

N2 - A factor u of a word w is a cover of w if every position in w lies within some occurrence of u in w. A factor u is a seed of w if it is a cover of a superstring of w. Covers and seeds extend the classical notions of periodicity. We introduce a new notion of α-partial seed, that is, a factor covering as a seed at least α positions in a given word. We use the Cover Suffix Tree, recently introduced in the context of α-partial covers (Kociumaka et al., 2015, [13]); an O(nlog⁡n)-time algorithm constructing such a tree is known. However, it appears that partial seeds are more complicated than partial covers—our algorithms require algebraic manipulations of special functions related to edges of the modified Cover Suffix Tree and the border array. We present a procedure for computing shortest α-partial seeds that works in O(n) time if the Cover Suffix Tree is already given. This is a full version, which includes all the proofs, of a paper that appeared at CPM 2014 [1].

AB - A factor u of a word w is a cover of w if every position in w lies within some occurrence of u in w. A factor u is a seed of w if it is a cover of a superstring of w. Covers and seeds extend the classical notions of periodicity. We introduce a new notion of α-partial seed, that is, a factor covering as a seed at least α positions in a given word. We use the Cover Suffix Tree, recently introduced in the context of α-partial covers (Kociumaka et al., 2015, [13]); an O(nlog⁡n)-time algorithm constructing such a tree is known. However, it appears that partial seeds are more complicated than partial covers—our algorithms require algebraic manipulations of special functions related to edges of the modified Cover Suffix Tree and the border array. We present a procedure for computing shortest α-partial seeds that works in O(n) time if the Cover Suffix Tree is already given. This is a full version, which includes all the proofs, of a paper that appeared at CPM 2014 [1].

KW - Algorithms on strings

KW - Cover

KW - Quasiperiodicity

KW - Seed

KW - Suffix tree

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

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

U2 - 10.1016/j.tcs.2016.11.035

DO - 10.1016/j.tcs.2016.11.035

M3 - Article

AN - SCOPUS:85007471205

SN - 0304-3975

VL - 710

SP - 139

EP - 147

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Efficient algorithms for shortest partial seeds in words

Abstract

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this