Approximate periods
Sim et al. [7] introduced a notion of approximation periods (approximate period) using edit distance or relative edit distance. The problem in general is defined as follows: given a string x, find a repeated pattern p such that x can be partitioned as x = p1p2...pk and  is minimized. Here d(p, pl) is the relative edit distance which is  the edit distance, where L = (|p| + |pl|)/2 is the average length of the two strings p and pl. Note that, the normalization of the edit distance is important for finding repeated patterns since otherwise, one can give a partition in which each pattern has one letter and the edit distance is at most 1 (small). The problem in general is NP-hard [7]. When the repeated pattern p is assumed to be a substring of x, The problem can be solved in O(|x|4) time. Note that the second measure is more general than the first since it allows insertions and deletions. Both measures in [7] and [6] use the bottleneck function that finds the repeated pattern p and assumes that each copy pi in the long string is close to the repeated pattern p, i.e., d(pi, p) ≤ δ and δ is minimized. However, in biological sequences, copies of the repeated patterns may change gradually so that some repeats in the region may have very little in common. For example, it is well-known that the N-terminal non-globular region of Thermus thermophilus seryl-tRNA synthetase (PDB:1SRY) [1,8] has weak 7-residue repeats. See Table 1. The similarity score between two consecutive patterns is calculated using Blosum62 matrix and the gap penalty is set to be -4. The repeated patterns gradually changes from the 4-th unit LDLEALLA to the 13-th unit KEARLE. The average similarity score for the nine pairs of consecutive patterns is 4.56. But the similarity score between the 4-th unit and the 8-th unit is -11. In this case, the algorithms based on the bottleneck function may fail to find the multiple repeats.
Table 1  Pseudo periodic repeats of 1SRY (matrix:blosum62, gap penalty: -4)
Unit  Pseudo-periodic unit  Length  Similarity with previous unit
1  MVDLKRLR  8
2  QEPEVFHR  8  -5
3  AIREKGVA  8  -10
4  LDLEALLA  8  -1
5  LDREVQEL  8  7
6  KKRLQEVQ  8  6
7  TERNQVA  7  6
8  KRVPKAP  7  -4
9  PEEKEAL  7  -2
10  IARGKAL  7  3
11  GEEAKRL  7  3
12  EEALRE  6  10
13  KEARLE  6  12
14  ALLLQV  6  -6
15  PLPP  4  -8