Linear time algorithms for finding and representing all the tandem repeats in a string

Gusfield D, Stoye J (2004)
Journal of computer and system sciences 69(4): 525-546.

Download
OA
Zeitschriftenaufsatz | Veröffentlicht | Englisch
Autor
;
Abstract / Bemerkung
A tandem repeat (or square) is a string [alpha][alpha], where [alpha] is a non-empty string. We present an O(|S|)-time algorithm that operates on the suffix tree T(S) for a string S, finding and marking the endpoint in T(S) of every tandem repeat that occurs in S. This decorated suffix tree implicitly represents all occurrences of tandem repeats in S, and can be used to efficiently solve many questions concerning tandem repeats and tandem arrays in S. This improves and generalizes several prior efforts to efficiently capture large subsets of tandem repeats.
Erscheinungsjahr
Zeitschriftentitel
Journal of computer and system sciences
Band
69
Zeitschriftennummer
4
Seite
525-546
ISSN
PUB-ID

Zitieren

Gusfield D, Stoye J. Linear time algorithms for finding and representing all the tandem repeats in a string. Journal of computer and system sciences. 2004;69(4):525-546.
Gusfield, D., & Stoye, J. (2004). Linear time algorithms for finding and representing all the tandem repeats in a string. Journal of computer and system sciences, 69(4), 525-546. doi:10.1016/j.jcss.2004.03.004
Gusfield, D., and Stoye, J. (2004). Linear time algorithms for finding and representing all the tandem repeats in a string. Journal of computer and system sciences 69, 525-546.
Gusfield, D., & Stoye, J., 2004. Linear time algorithms for finding and representing all the tandem repeats in a string. Journal of computer and system sciences, 69(4), p 525-546.
D. Gusfield and J. Stoye, “Linear time algorithms for finding and representing all the tandem repeats in a string”, Journal of computer and system sciences, vol. 69, 2004, pp. 525-546.
Gusfield, D., Stoye, J.: Linear time algorithms for finding and representing all the tandem repeats in a string. Journal of computer and system sciences. 69, 525-546 (2004).
Gusfield, Dan, and Stoye, Jens. “Linear time algorithms for finding and representing all the tandem repeats in a string”. Journal of computer and system sciences 69.4 (2004): 525-546.
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
1970-01-01T00:00:00Z