Pseudo-periodic repeats
Li et al. [1] gave the first measure that allows gradual changes of patterns and changes of pattern lengths in the region. The repeats they defined are called the pseudo-periodic repeats. Given a repeated region (a string) x and a partition X = s1s2...sk, the pseudo periodic score is
where d(·) is the edit distance, |si| is the length of si, and c is a factor that control the penalty of the two ends of the partition. Li et al. [1] gave a O(|x|2) algorithm to compute an optimal partition of a given repeated region x. It was shown that the pseudo-periodic score can accurately give partitions for tandem repeated regions, where the repeated patterns are weakly similar.
Example: The example is from [1]. The sequence of the LbH domain of members of the LpxA family consists of the imperfect tandem repetition of hexapeptide units [9-11]. These imperfect tandem repeats (partitions) have been accurately detected by the algorithm using the pseudo periodic score [1]. (See Table 2).
Table 2  Pseudo periodic repeats of LPXA_ECOLI (matrix:blosum62, gap penalty: -4)
Unit  Pseudo-periodic unit  Length  Similarity with previous unit
1  MIDKSAFVHPTAIVEEGA  18
2  SIGANAHIGPFCIVGPHV  18  14
3  EIGEGTVLKSHVVVNGHT  18  16
4  KIGRDNEIYQFASI  14  -7
5  GEVNQDLKYAGEPTR  15  -3
6  VEIGDRNRIRESVTI  15  2
7  HRGTVQGGGL  10  -14
8  TKVGSDNLLMINAHIAHD  18  -24
9  CTVGNRCILANNATLAGH  18  20
10  VSVDDFAIIGGMTAVHQF  18  4
11  CIIGAHVMVGGCSGV  15  4 In sequence analysis, we may have a long sequence s and only a substring t (or a few substrings) of s contains the consecutive repeats. The problem here is to find out the substring t and give an optimal pseudo-periodic partition. We call this problem the local pseudo-periodic problem. In this paper, we define the maximization version of the pseudo-periodic partition and develop an algorithm that solves the local pseudo-periodic problem in O(n2) time, where n is the length of the input sequence s.