Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

Approximate periodicity in strings

Smyth, W.F. (1997) Approximate periodicity in strings. Utilitas Mathematica, 51 . pp. 125-135.

PDF - Authors' Version
Download (196kB)


In many application areas (for instance, DNA sequence analysis) it becomes important to compute various kinds of “approximate period” of a given string y. Here we discuss three such approximate periods and the algorithms which compute them: an Abelian generator, a cover, and a seed. Let u be a substring of y. Then u is an Abelian generator of y iff y is a concatenation of substrings which are permutations of u: u is a cover of y iff every letter of y is contained in an occurrence of u in y and u is a seed of y iff y is a substring of a string y with cover u. Observe that, according to these definitions, y is an Abelian generator, a cover, and a seed of itself.

Item Type: Journal Article
Publisher: Utilitas Mathematica Publishing Inc
Publisher's Website:
Item Control Page Item Control Page


Downloads per month over past year