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

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.

PDF - Published Version
Download (109kB)
Link to Published Version:
*Subscription may be required


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.

Item Type: Journal Article
Publisher: IOS Press
Item Control Page Item Control Page


Downloads per month over past year