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.

[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.

Item 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