Simple and flexible detection of contiguous repeats using a suffix tree

Stoye J, Gusfield D (2002)
Theoretical Computer Science 270(1-2): 843-856.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
OA
Autor/in
;
Abstract / Bemerkung
We study the problem of detecting all occurrences of (primitive) tandem repeats and tandem arrays in a string. We first give a simple time- and space-optimal algorithm to find all tandem repeats, and then modify it to become a time and space-optimal algorithm for finding only the primitive tandem repeats. Both of these algorithms are then extended to handle tandem arrays. The contribution of this paper is both pedagogical and practical, giving simple algorithms and implementations based on a suffix tree, using only standard tree traversal techniques.
Stichworte
Sequence analysis; Tandem repeats; Suffix tree; Tandem arrays; Repeats
Erscheinungsjahr
2002
Zeitschriftentitel
Theoretical Computer Science
Band
270
Ausgabe
1-2
Seite(n)
843-856
ISSN
0304-3975
Page URI
https://pub.uni-bielefeld.de/record/1773332

Zitieren

Stoye J, Gusfield D. Simple and flexible detection of contiguous repeats using a suffix tree. Theoretical Computer Science. 2002;270(1-2):843-856.
Stoye, J., & Gusfield, D. (2002). Simple and flexible detection of contiguous repeats using a suffix tree. Theoretical Computer Science, 270(1-2), 843-856. doi:10.1016/S0304-3975(01)00121-9
Stoye, J., and Gusfield, D. (2002). Simple and flexible detection of contiguous repeats using a suffix tree. Theoretical Computer Science 270, 843-856.
Stoye, J., & Gusfield, D., 2002. Simple and flexible detection of contiguous repeats using a suffix tree. Theoretical Computer Science, 270(1-2), p 843-856.
J. Stoye and D. Gusfield, “Simple and flexible detection of contiguous repeats using a suffix tree”, Theoretical Computer Science, vol. 270, 2002, pp. 843-856.
Stoye, J., Gusfield, D.: Simple and flexible detection of contiguous repeats using a suffix tree. Theoretical Computer Science. 270, 843-856 (2002).
Stoye, Jens, and Gusfield, Dan. “Simple and flexible detection of contiguous repeats using a suffix tree”. Theoretical Computer Science 270.1-2 (2002): 843-856.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Volltext(e)
Access Level
OA Open Access
Zuletzt Hochgeladen
2019-09-06T08:48:07Z
MD5 Prüfsumme
d738b4fa0ae8ffa6e7ec1967261ac910