TY - GEN

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 - 2014/1/1

Y1 - 2014/1/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, introduced recently in the context of α-partial covers (Kociumaka et al, CPM 2013); an O(n log 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 an algorithm for computing shortest α-partial seeds that works in O(n) time if the Cover Suffix Tree is already given.

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, introduced recently in the context of α-partial covers (Kociumaka et al, CPM 2013); an O(n log 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 an algorithm for computing shortest α-partial seeds that works in O(n) time if the Cover Suffix Tree is already given.

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

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

U2 - 10.1007/978-3-319-07566-2_20

DO - 10.1007/978-3-319-07566-2_20

M3 - Conference contribution

AN - SCOPUS:84958542977

SN - 9783319075655

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

SP - 192

EP - 201

BT - Combinatorial Pattern Matching - 25th Annual Symposium, CPM 2014, Proceedings

PB - Springer Verlag

T2 - 25th Annual Symposium on Combinatorial Pattern Matching, CPM 2014

Y2 - 16 June 2014 through 18 June 2014

ER -