Home
Scholarly Works
Approximate periodicity in strings
Journal article

Approximate periodicity in strings

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.

Authors

Smyth WF

Journal

Utilitas Mathematica, Vol. 51, , pp. 125–135

Publication Date

June 1, 1997

ISSN

0315-3681

Labels

Contact the Experts team