Catalog Home Page

Faster algorithms for computing maximal multirepeats in multiple sequences

Ilopoulos, C.S., Smyth, W.F. and Yusufu, M. (2009) Faster algorithms for computing maximal multirepeats in multiple sequences. Fundamenta Informaticae, 97 (3). pp. 311-320.

[img]
Preview
PDF - Published Version
Download (109kB)
Link to Published Version: http://dx.doi.org/10.3233/FI-2009-203
*Subscription may be required

Abstract

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 _ 2) in each of at least q (greater than or 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 space-efficient 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.

Publication Type: Journal Article
Publisher: IOS Press
URI: http://researchrepository.murdoch.edu.au/id/eprint/27952
Item Control Page Item Control Page

Downloads

Downloads per month over past year