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.
*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.
|Publication Type:||Journal Article|
|Item Control Page|
Downloads per month over past year