Linear time algorithms for finding and representing all the tandem repeats in a string
Linear time algorithms for finding and representing all the tandem repeats in a string
复制标题
DOI：
10.1016/j.jcss.2004.03.004
复制
发表时间：
2004-12-01
影响因子：
1.1
通讯作者：
Stoye, J
中科院分区：
文献类型：
--
作者：
Gusfield, D;Stoye, J
串联重复（或正方形）是字符串αAlpha，其中alpha是一个非空字符串。我们提出了一个O（\ s \） - 时间算法，该算法在字符串s的后缀树上操作，找到并标记了S.在S中发生的每个串联重复的t（s）中的端点。隐式表示s中串联重复的所有出现，可用于有效地解决有关串联重复序列和串联阵列的许多问题。有效地捕获大量串联重复的大量努力。 （c）2004 Elsevier Inc.保留所有权利。
A tandem repeat (or square) is a string alphaalpha, 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. (C) 2004 Elsevier Inc. All rights reserved.