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
Journal Article | Published | English
Author
;
Abstract
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.
Publishing Year
ISSN
PUB-ID

Cite this

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.
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.
Main File(s)
Access Level
OA Open Access

This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Search this title in

Google Scholar