Catalog Home Page

Approximate periodicity in strings

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

[img]
Preview
PDF - Authors' Version
Download (196kB)

Abstract

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.

Publication Type: Journal Article
Publisher: Utilitas Mathematica Publishing Inc
Publishers Website: http://bkocay.cs.umanitoba.ca/utilitas/index.html
URI: http://researchrepository.murdoch.edu.au/id/eprint/27543
Item Control Page Item Control Page

Downloads

Downloads per month over past year