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.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
OA
Autor/in
;
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
2004
Zeitschriftentitel
Journal of computer and system sciences
Band
69
Ausgabe
4
Seite(n)
525-546
ISSN
0022-0000
Page URI
https://pub.uni-bielefeld.de/record/1773569

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
2019-09-06T08:48:08Z
MD5 Prüfsumme
3ef31f40be5434e3cd28cb2f60da2d79