Journal article
Approximate periodicity in strings
Utilitas Mathematica, Vol.51, pp.125-135
1997
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.
Details
- Title
- Approximate periodicity in strings
- Authors/Creators
- W.F. Smyth (Author/Creator)
- Publication Details
- Utilitas Mathematica, Vol.51, pp.125-135
- Publisher
- Utilitas Mathematica Publishing Inc
- Identifiers
- 991005541344907891
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
- Publisher URL
- http://bkocay.cs.umanitoba.ca/utilitas/index.html
Metrics
81 File views/ downloads
64 Record Views