Journal article
Faster algorithms for computing maximal multirepeats in multiple sequences
Fundamenta Informaticae, Vol.97(3), pp.311-320
2009
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.
Details
- Title
- Faster algorithms for computing maximal multirepeats in multiple sequences
- Authors/Creators
- C.S. Ilopoulos (Author/Creator)W.F. Smyth (Author/Creator)M. Yusufu (Author/Creator)
- Publication Details
- Fundamenta Informaticae, Vol.97(3), pp.311-320
- Publisher
- IOS Press
- Number of pages
- 10
- Identifiers
- 991005544901407891
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
Metrics
185 File views/ downloads
74 Record Views
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- International collaboration
- Citation topics
- 4 Electrical Engineering, Electronics & Computer Science
- 4.182 Data Structures, Algorithms & Complexity
- 4.182.1103 Efficient Algorithms
- Web Of Science research areas
- Computer Science, Software Engineering
- Mathematics, Applied
- ESI research areas
- Computer Science