TY - GEN
T1 - Efficient seeds computation revisited
AU - Christou, Michalis
AU - Crochemore, Maxime
AU - Iliopoulos, Costas S.
AU - Kubica, Marcin
AU - Pissis, Solon P.
AU - Radoszewski, Jakub
AU - Rytter, Wojciech
AU - Szreder, Bartosz
AU - Waleń, Tomasz
PY - 2011/7/13
Y1 - 2011/7/13
N2 - The notion of the cover is a generalization of a period of a string, and there are linear time algorithms for finding the shortest cover. The seed is a more complicated generalization of periodicity, it is a cover of a superstring of a given string, and the shortest seed problem is of much higher algorithmic difficulty. The problem is not well understood, no linear time algorithm is known. In the paper we give linear time algorithms for some of its versions - computing shortest left-seed array, longest left-seed array and checking for seeds of a given length. The algorithm for the last problem is used to compute the seed array of a string (i.e., the shortest seeds for all the prefixes of the string) in O(n 2) time. We describe also a simpler alternative algorithm computing efficiently the shortest seeds. As a by-product we obtain an O(nlog(n/m)) time algorithm checking if the shortest seed has length at least m and finding the corresponding seed. We also correct some important details missing in the previously known shortest-seed algorithm (Iliopoulos et al., 1996).
AB - The notion of the cover is a generalization of a period of a string, and there are linear time algorithms for finding the shortest cover. The seed is a more complicated generalization of periodicity, it is a cover of a superstring of a given string, and the shortest seed problem is of much higher algorithmic difficulty. The problem is not well understood, no linear time algorithm is known. In the paper we give linear time algorithms for some of its versions - computing shortest left-seed array, longest left-seed array and checking for seeds of a given length. The algorithm for the last problem is used to compute the seed array of a string (i.e., the shortest seeds for all the prefixes of the string) in O(n 2) time. We describe also a simpler alternative algorithm computing efficiently the shortest seeds. As a by-product we obtain an O(nlog(n/m)) time algorithm checking if the shortest seed has length at least m and finding the corresponding seed. We also correct some important details missing in the previously known shortest-seed algorithm (Iliopoulos et al., 1996).
UR - http://www.scopus.com/inward/record.url?scp=79960103156&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79960103156&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-21458-5_30
DO - 10.1007/978-3-642-21458-5_30
M3 - Conference contribution
AN - SCOPUS:79960103156
SN - 9783642214578
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 350
EP - 363
BT - Combinatorial Pattern Matching - 22nd Annual Symposium, CPM 2011, Proceedings
T2 - 22nd Annual Symposium on Combinatorial Pattern Matching, CPM 2011
Y2 - 27 June 2011 through 29 June 2011
ER -