Faster algorithms for computing maximal multirepeats in multiple sequences
Access Status
Authors
Date
2009Type
Metadata
Show full item recordAbstract
A repeat in a string is a substring that occurs more than once. A repeat is extendible if every occurrence of the repeat has an identical letter either on the left or on the right; otherwise, it is maximal. A multirepeat is a repeat that occurs at least mmin times (mmin greater than/equal to 2) in each of at least q greater than/equal to 1 strings in a given set of strings. In this paper, we describe a family of efficient algorithms based on suffix arrays to compute maximal multirepeats under various constraints. Our algorithms are faster, more flexible and much more spaceefficient than algorithms recently proposed for this problem. The results extend recent work by two of the authors computing all maximal repeats in a single string.
Citation
Source Title
Faculty
Department
Collections
Related items
Showing items related by title, author, creator and subject.

Puglisi, Simon; Smyth, William; Yusufu, M. (2010)Given a string x = x[1..n] on an alphabet of size α, and a threshold p min ≥ 1, we describe four variants of an algorithm PSY1 that, using a suffix array, computes all the complete nonextendible repeats in x of length p ...

Crochemore, M.; Iliopoulos, Costas; Pissis, S.; Tischler, G. (2010)A proper fact or u of a string y is a cover of y if every letter of y is within some occurrence of u in y. The concept generalises the notion of periods of a string. An integer array C is the minimalcover (resp. ...

Puglisi, Simon; Smyth, Bill; Yusufu, M. (2008)Given a string x = x[1..n] on an alphabet of size a, and a threshold pmin = 1, we first describe a new algorithm PSY1 that, based on suffix array construction, computes all the complete nonextendible repeats in x of length ...