--- title: "Mining Complex Patterns across Sequences with Gap Requirements" authors: - "Xingquan Zhu" - "Xindong Wu" doi: "" url: "https://ijcai.org/proceedings/2007/472" pdf: "https://ijcai.org/proceedings/2007/0472.pdf" venue: "Proceedings of the Twentieth International Joint Conference on Artificial Intelligence" year: 2007 pages: "2934-2940" track: "" keywords: --- # Mining Complex Patterns across Sequences with Gap Requirements Xingquan Zhu, Xindong Wu *Proceedings of the Twentieth International Joint Conference on Artificial Intelligence*, pages 2934-2940. ## Abstract The recurring appearance of sequential patterns, when confined by the predefined gap requirements, often implies strong temporal correlations or trends among pattern elements. In this paper, we study the problem of mining a set of gap constrained sequen-tial patterns across multiple sequences. Given a set of sequences S1, S2,., SK constituting a single hyper-sequence S, we aim to find recurring patterns in S, say P, which may cross multiple sequences with all their matching characters in S bounded by the user specified gap constraints. Because of the combina-torial candidate explosion, traditional Apriori-based algorithms are computationally infeasible. Our research proposes a new mechanism to ensure pattern growing and pruning. When combining the pruning technique with our Gap Constrained Search (GCS) and map-based support prediction approaches, our method achieves a speed about 40 times faster than its other peers ## Full text ## 1 Introduction Many real-world applications involve data characterized by continuous sequences and streams. Examples include data flows in medical ICU (Intensive Care Units), network traffic data, stock exchange rates, and DNA and protein sequences. Since real-world events rarely happen independently but rather associate with each other, to some degree, discovering structures of interest in multiple sequences provides us an effective means to explore patterns trivial in a single data stream but significant when unifying all observed data into one view. For example, the information from multiple data streams in ICU (such as the oxygen saturation, chest volume and hear rate) may indicate or predicate the state of a patient's situation, and an intelligent agent with the ability to discover knowledge from multiple sensors can automatically acquire and update its environment models [Oats & Cohen 96]. In microbiology, it is now well known that the genomes of most plants and animals contain a large quantity of repetitive DNA fragments. Examples include recurring short base pairs (BP) in protein coding DNA and repetitive DNA/RNA motifs in genomes, where recurring patterns of different lengths and types are commonly found, at both genomic and proteomic levels, to have significant biological/medical values. For example, the 10-11 BP periodicities in complete genomes reflect protein structure and DNA folding [Herzel et al. 99] and some tandem repeats are now discovered to be influential to the bacterial virulence to human [Belkum et al. 97]. Studying correlations among multiple gene sequences, their associations with environments and disease phenotypes, thus provides a means of predicting and preventing fatal diseases [Rigoutsos & Floratos 98]. ∗ This material is based upon work supported by the US National Science Foundation under Grant No. 0514819. The support of NSF of China under Grant No. 60674109 is also acknowledged. Although recurring patterns convey important and useful knowledge, in reality, they rarely just reproduce and repeat themselves, but rather appear with a slight shift in the pattern letters. For example, the tandem repeats in DNA or protein sequences often involve a phase shift incurred by the insertion or deletion of a short sequence [Belkum et al. 97]. A practical solution is to allow the mining or search process to bear a certain degree of flexibility. Consider sequences in Fig. 1(a), where a pattern across three sequences repeats three times but with each appearance slightly different from the others. If we can allow that each time the pattern appears, any two of its successive pattern letters' appearances are within a range, rather than a fixed value, we may then be able to find the pattern in Fig. 1(a). The introduction of a variable period (gap) thus provides a flexible way to capture interesting patterns hidden in sequences. Mining recurring patterns from sequences essentially relies on a counting mechanism to check patterns' occurrences. This, however, is inherently complicated by the sequential order of the underlying sequences. Considering sequence "AAAGGGTTTTCCCTTTTCCCTTTTCCCC", to find the number of complete occurrences of pattern P=AGTC (we ignore gap constraints at this stage), there are 3 × 3 combinations for "A" and "G", and 4×10+4×7+4×4 combinations for "T" and "C". So in total, there are 9×84 occurrences for AGTC. Although this number does not sound scary, considering complete occurrences, however, brings one of the most difficult challenges to our problem: the deterministic Apriori theory (the support of a pattern cannot exceed the support of any of its sub-patterns) does not hold. Considering S="AGCTTT", pattern P=AGCT appears three times in S, but P's subpattern AGC appears once only. Therefore, traditional Apriori-based algorithms are computationally infeasible to handle our problem. Motivated by the above observations, we propose MCPaS to Mine Complex Patterns across Sequences with gap requirements. We will review related work in the next section, and state our research problem in Section 3. In Section 4, we will study pattern frequencies and propose a deterministic pruning technique for pattern mining. In Section 5, we discuss our unique Gap Constrained Search and Map-based Support Prediction processes to accelerate the pattern mining process. Based on the proposed pruning and searching techniques, we elaborate, in Section 6, the mining algorithm details. Comparative studies are reported in Section 7, followed by the concluding remarks in Section 8. Figure 1. (a) Patterns across three sequences; (b) The hybrid sequence generalized from the sequences in (a) ![Image](https://ijcai.org/proceedings/2007/fulltext/472/image_000000_86c92df1084979f1f3ff7073645cf3a72ea91e2929821d8b41b689f823b4e8dd.png) ## 2 Related Work Existing research in mining patterns from data sequences can be distinguished into two categories. (1) Mining patterns frequently appearing in a certain number of (relatively short) sequences with a Boolean count, i.e., whether a pattern occurs in the sequence or not. Traditional pattern mining in market baskets [Srikant & Agrawal 96, Pei et al. 01, Zaki 98] and Gene Motif search [Murray et al. 02] fall into this category. (2) Mining recurring patterns from long sequences such as episode mining [Yang et al. 00, Méger & Rigotti 04, Das et al. 98] and tandem repeats and base pair oscillation detection in DNA sequences [Herzel et al. 99]. Any mining process will have to rely on a counting mechanism to check patterns' frequency information, from which frequent patterns can be found. It is worth noting that the selected counting mechanism crucially impacts on the mining approach. For research efforts relying on a Boolean count, because a pattern's appearances are counted for only once w.r.t. each sequence, the deterministic Apriori theory well holds, and is therefore commonly adopted in the mining process. On the other hand, when one has to determine a pattern's actual number of occurrences in the sequences, the situation becomes complicated, simply because the mining process won't follow Apriori theory at all. Existing efforts in the field have therefore proposed confined occurrence counting, such as minimal occurrences [Mannila et al. 97], one-off occurrences [Chen et al. 05], and windowing occurrences [Mannila et al. 97]. The objective is to confine patterns' occurrences such that Apriori theory can apply. When considering complex patterns across multiple sequences, the work relevant to our problem here comes from Oates et al. [96] and Mannila et al. [97]. Both efforts tried to search frequent episodes across sequences, as well as the prediction rules in the form of x indicating y, where x and y are the frequent episodes in the sequences. For example, after event A happens, exactly two time points later event B happens, and then exactly three time points later event C happens. Notice that this is a very restrictive constraint, and we are trying to find episodes like: after event A happens, within two time points event B happen, and within three time points later event C happens. This loose constraint leaves a great flexibility to explore useful patterns. The problem of complex pattern mining across multiple sequences is similar to multi-dimensional sequential pattern mining [Pino et al. 01], where a normal practice is to aggregate values from all sequences to form a single sequence, as shown in Figure 1(b), so traditional sequential pattern mining methods can apply. In the domain of DNA or protein sequences, BLAST [Altschul 90] is one of the most famous algorithms. Given a query sequence (pattern), it searches for a matching sequence from the databases, while what we are pursuing here is on mining the patterns. To find patterns, the TEIRESIAS algorithm [Rigoutsos & Floratos 98] is designed for pattern discovery from biological sequences with the number of wild-cards that can be present in the extracted patterns restricted and fixed by the users. Similar approaches such as Pratt [Jonassen 97] is also proposed to mine restricted patterns (in terms of the maximum numbers of characters and wild-cards in each pattern) from a single sequence. ## 3 Problem Statement The sequences S 1 ,.., S i , .., S K from which we extract patterns are called a hyper-sequence, denoted by S, with each single sequence S i called an element sequence. We use S[i] to represent the characters at the i th time point of S. Without losing the generality, we assume all element sequences share the same alphabet size, denoted by ·, and |·| represents the size of ·. For simplicity, we assume that all element sequences have the same lengths, denoted by L. A wild-card (denoted by a single dot ".") is a special symbol that matches any character in ·. A gap g is a sequence of wild-cards, bounded by the maximal and minimal values. The size of the gap refers to the number of wildcards in it. We use M N g to represent a gap whose size is within the range [N, M]. We also call W=M-N+1, the gap flexibility. A pattern, P=p 1 g 1 p 2 g 2 ,…,g l-1 p l , is a set of characters from different element sequences and gaps that begin and end with characters, where p j is an element pattern which consists of letters from element sequences. An element pattern should consist of at least one character. g j is the gap requirement between element patterns p j-1 and p j . Figure 2 pictorially shows a pattern P with three element patterns. The number of element patterns in P, denoted by |P|, is called the length of P, i.e., the wild-card symbols are not counted towards a pattern's length. The problem of mining complex patterns across multiple sequences is to find patterns of the following form: which means that gaps between any two successive element patterns are the same, i.e., g 1 =g 2 =…=g 1 = M N g . An occurrence of a pattern P in S is defined as a match between the characters of the element patterns and the element sequences, under the gap constraints. The occurrences are considered different, as long as the locations of one pair of the matched characters are different. For example, we consider P=ATG appears 2 times in S="ATTG", w.r.t. 2 0 g , i.e., S[1]S[2]S[4] and S[1]S[3]S[4]. The support of P in S (denoted by sup(P)) is the number of times P occurring in S. Given a length-l pattern P and a length-L hybrid-sequence S, we first calculate the total number of possible occurrences of a length-l pattern in S, L l , then we count the actual appearances of P, sup(P). We consider P a frequent pattern, iff sup(P)/L l is larger than the user-specified threshold value . Figure 2. A pattern denotation ![Image](https://ijcai.org/proceedings/2007/fulltext/472/image_000001_f1c5e72d6e71056f45d16137372ac7d4728dc9b162074ebb3e4a23e4a43d781a.png) ## 4 Pattern Frequency & Deterministic Pruning ## 4.1 Pattern Frequency Given pattern P=p 1 p 2 …p l and its support in a length-L hyper-sequence S (with L >> l), sup(P), to assess P's frequency, we need to find L l , the possible number of occurrences of P in S. Considering pattern P with gap M N g , each time P appears in S, its actual spans in S vary from l+(l-1)N to l+(l-1)M, which correspond to the cases that whenever P appears in S, the gap between any two successive element patterns exactly equal to N and M respectively. Assuming the first element pattern p 1 matches S at S[δ], then for element pattern p 2 , its valid occurrences may possibly appear in the range from S[δ+N] to S[δ+M], i.e., with W=M-N+1 possibilities. The same situation holds for all other element patterns p 3 ,…p l . So in total, a length-l pattern P starting at S[δ] may have W l-1 possible occurrences in S. Assuming p 1 has possible appearances in S, the total number of possible appearances of P in S is L l = ·W l-1 . Because the average span between successive element patterns is (N+M)/2+1, the average span of P in S is (l-1)·((N+M)/2+1). Then, the possible number of occurrences of p 1 equals to [L-(l1)·((N+M)/2+1)], where [♦] means the maximal integer no larger than ♦. So the value of L l is defined by Eq. (2). Eq (2) holds only if (l+(l-1) ·M) · L, i.e., the maximal span of the pattern is less than the length of the hyper-sequence. ## 4.2 Deterministic Pruning In this subsection, we derive one theorem and two lemmas for the deterministic pruning of our mining process. THEOREM 1. Gien a length-l pattern P and its length l-3 subpatterns Q, we have the supports of Q and P satisfy the inequality 2 ) ( ) sup( ) sup( 2 3 W W Q P + ⋅ ≤ Proof: Because Q is a length l-3 subpattern of P, denoting Q by q 1 q 2 …q l-3 , there are four possible relationships between them: (1) P=p 1 Qp l-1 p l ; (2) P=p 1 p 2 Qp l ; (3) P=Qp l-2 p l-1 p l ; and (4) P=p 1 p 2 p 3 Q. Let's first prove that Theorem 1 is true for (1). The same proof applies to all other possibilities. Assuming N=0 and the gap flexibility is W, the first element pattern of Q, q 1 , appears at time slot S[ ]. It is easy to know that p 1 has W possibilities to appear between S[ -W] and S[ -1]. So the maximal support of p 1 Q is sup(p 1 Q)=W· sup(Q). Now assuming further that the last element pattern of Q, q l-3 , appears at S[ + ], it is clear that p l-1 has W possibilities to appear at the range between S[ + +1] and S[ + +W], as shown in Figure 3. If p l-1 indeed appears at S[ + +W], the element pattern p 1 will have W possibilities to appear between S[ + +W+1] and S[ + +2W]. Denoting this region by ] 2 , 1 [ 1 1 W W l + + + + + ⊂ - β α β α ϕ , if p l-1 appears at S[ + +W-1], we know that p l may possibly appear between S[ + +W] and S[ + +2W-1]. Notice that S[ + +W] has been reserved for the possible appearance of p l-1 , so the number of possible appearances of p l (w.r.t. to p l-1 at S[ + +W-1]) is W-1, unless p l-1 and p l are the same, which is not a generic case in reality. Similarly, the number of possible appearances of p l (w.r.t. to p l-1 at S[ + +W-2]) is W-2. As a result, for all possible W appearances of p l-1 between S[ + +1] and S[ + +W], the sum of their possible matching p l 's occurrences is 1 - ϕ =W+W-1+W-2…+0=W(W+1)/2. l So the maximal support for length-l pattern P=p 1 Qp l-1 p l is W·sup(Q)· 1 - l ϕ = 2 ) ( ) sup( 2 3 W W Q + ⋅ , that is, sup(P) · 2 ) ( ) sup( 2 3 W W Q + ⋅ . ![Image](https://ijcai.org/proceedings/2007/fulltext/472/image_000002_2c089c0eb4585c1a029ec7c4af606e3739494781971241fb1b858c314d892e47.png) LEMMA 1. Given a threshold , we say that a length-l pattern P is frequent iff sup(P)/L l · . If P's any length l-3 subpattern Q's frequency, Freq(Q), is less than ρ ω ω ⋅ + ⋅ - - + ⋅ - - ) 1 ( ) 4 ( ) 1 ( ) 1 ( l L l L , where ω=(N+M)/2, then P cannot be a frequent pattern. Proof: Because Freq(Q)=Sup(Q)/L l-3 , we know ρ ω ω ⋅ + ⋅ - - + ⋅ - - ≤ - ) 1 ( ) 4 ( ) 1 ( ) 1 ( ) ( 3 l L l L L Q Sup l , since 4 3 )) 1 ( ) 4 ( ( - - ⋅ + ⋅ - - = l l W l L L ω , We have ρ ω ⋅ ⋅ + ⋅ - - < -4 )) 1 ( ) 1 ( ( ) ( l W L L Q Sup Because Q is a length l-3 subpattern of P, according to Theorem 1, we know that 2 ) ( ) sup( ) ( 2 3 W W Q P Sup + ⋅ ≤ So Sup ( P ) ( L ( L ) 1 ω ( )) 1 W ρ ( W W ) 2 Because the gap flexibility W ·1, we know 1 2 ) 1 ( ≤ + W W , i.e., ρ < L P Sup ) ( . Therefore, P is not frequent. l LEMMA 2: If the average span of the longest pattern in S is less than W L W 2 ) 1 ( ⋅ - , i.e., about a half of a length-L hypersequence S, given a length-l pattern P, for any length l-3 subpattern of P, Q, if Freq(Q) is less than ρ ω ω ⋅ + ⋅ - - + ⋅ - - ) 1 ( ) 4 ( ) 1 ( ) 1 ( l L l L , where ω=(N+M)/2, then patterns, with P as their subpatterns, are not frequent. ## Justification: According to Lemma 1, we know that given the conditions in Lemm2, a length-l pattern P will not be frequent. Now assume pattern P is a subpattern of a length-l+k pattern F. According to Eq. (2), we know + ⋅ ⋅ , W W L P Sup l 2 ) 1 ( ) ( < ρ for any length-l+k pattern F, with P as its subpattern, the maximal support of F is less than W k times of Sup(P). average span of the length-l+k pattern. Given that the longest pattern is less than W L W 2 ) 1 ( ⋅ - , we have So pattern F is not frequent. In reality, we may not know in apriori that whether the average span of the longest pattern in S is less than W L W 2 ) 1 ( ⋅ - or not (since the longest patterns are yet to be found), so Lemma 2 does not seem to be useful in the mining process. Nevertheless, because we are dealing with a long hyper-sequence S, it is almost certain that the average span (even the maximal span) of the longest pattern in S is less than a half of |S|. For the DNA sequences we are using (in Section 7), the average span of the longest pattern is less than 10 percent of the sampled length-1000 sequence S. So we can safely assume that this prerequisite always holds. - 4 3 2 < - - ⋅ + ⋅ l ⋅ ⋅ + ## 5 Pattern Search with Gap Requirements Consider a length-l pattern P with a gap flexibility W, an exhaustive search will start from the first pattern letter p 1 to find its first match in S. Denoting this matching location by x, the search process then starts from x to match p 2 within the range [x+1, x+W]. Such a process iteratively repeats until all possible locations starting from x have been checked, then it moves one step forward (x+1). The time complexity is O(L·W l-1 ), which is linear w.r.t. L, but exponential w.r.t. W and l. In the case that S consists of K element sequences, this complexity increases to O(K·L·W l-1 ). ## 5.1 Gap Constrained Search (GCS) In this subsection, we propose a Dynamic Programming [Bellman 57] oriented search mechanism, which is able to achieve a linear time complexity in gap constrained pattern search. The algorithm consists of three steps. Given a length-l pattern P= p 1 p 2 …p l , we first build a length L list for each of the element patterns p l , denoted by P O . We initiate l the value of l P O to 0 before the search process (For easy understanding, we pictorially show a simple example in Figure 4 with P=AGTC and gap 2 0 g ). 1. GCS sequentially scans S from the left to right. For any current position x, if S[x] matches the first element pattern p 1 , set the value of 1 P O [x] to 1. 2. At any location x, if S[x] matches any element pattern p j, j>l (i.e., excluding the first element pattern), we update the value of j P O to - = - = - ) , 1 max( 1 ] [ 1 W x v p p v x O O j j . As shown in Figure 4, when x=3, S[3] matches p 2 (which is G), then the value of O G [3] is updated to the sum of O A [1] and O A [2]. The above process indicates that for any matches of the element pattern letter, p j j>1, at location x, we backtrack W steps to find the number of times p j 's last successive pattern letter p j-1 has ever appeared. If all element patterns (p j , j>1) were able to iteratively regulate and update their lists P O in such a j way, then the value in j P O [x] will indicate the number of times that pattern p 1 p 2 …p j ever ends at position x. 3. We iteratively repeat the above process, until we finish the whole sequence S. Then we sum up all elements in l P O , which is the number of times P=p 1 p 2 …p l appears in S. In addition, the values in l P O [x] will indicate the number of times P ending at position x. The time complexity of GCS consists of two parts: (1) scanning the whole sequence L, and (2) at each location x, comparing S[x] with all element patterns, and backtracking W steps if necessary. Because each backtracking can be achieved through a sum operation, so the total time complexity is O(KL(l-1)), which is linear w.r.t. L, l, and K, and much more efficient than the exhaustive search O(KLW l-1 ). ![Image](https://ijcai.org/proceedings/2007/fulltext/472/image_000003_bc5e0a85a1af7c7bb8f11fda845bd40aa1ce5576bc2de077cebd000fe3f8d12d.png) ## 5.2 Map-based Support Prediction Notice that each time we grow a length-l pattern P to a length l+1 pattern F, we will have to check F's frequency by searching its occurrences in S again. This reexamination mechanism costs a considerable amount of system runtime, as there are possibly millions of candidates. Nevertheless, if we can reuse P's occurrence information, we may be able to speed up the search process dramatically. For this purpose, after we find pattern P's occurrences, we generate a rearmap (RM) for P which records the number of times P appears in S and all its ending positions (this RM is actually the O list in the above section). As shown in Figure 4, if P P l ever ends at position x, the value of RM[x] will indicate the number of times P ends at x; otherwise, RM[x] equals to 0. With the RM of pattern P=p l p 2 …p l , denoted by the ] [ ... 1 x RM l p p , we may just search P's RM, instead of scanning the whole sequence S, to find the number of times F appearing in S. This can be achieved by a simple production and sum procedure. More specifically, for pattern F= p l p 2 …p l p l+1 , if we can build a head-map (HP) which records locations and times of the length-2 pattern p l p l+1 's starting information, where ] [ 1 x HP l l p p + indicates the number of times p l p l+1 starts at position x, then, the support of pattern F is determined by Eq. (4) As shown in Figure 5, when predicting the support of AGTC, we first find RM AGT and HM TC , the production and sum of the corresponding elements of these two lists will exactly equal to AGTC's support. Figure 5. Map-based support prediction (gap constraint 2 0 g ) | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | |--------|-----|-----|-----|-----|-----|-----|-----|-----|-----|------|------|------|------|------|------|------|------|------| | S | A | A | A | G | C | G | T | C | T | C | A | G | G | T | C | T | T | C | | RMAGT | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 0 | 1 | 0 | 0 | 0 | 0 | 2 | 0 | 1 | 0 | 0 | | HM TC | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | | RMAGTC | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 0 | 5 | 0 | 0 | 0 | 0 | 2 | 0 | 0 | 1 | ## 6 Algorithm The system framework of MCPaS is shown in Figure 6. MCPaS first generates all length-2 patterns, denoted by C 2 . After the first step, MCPaS begins pattern growing and pruning. Assuming now at a certain step, we have generated a set of length-l candidates from length-l-1 patterns (on line 5 in Figure 6), then a length-l candidate's support can be easily predicted by plugging its length-l-1 patterns' RM and the corresponding length-2 patterns' HM into Eq. (4), without rescanning S. For all generated length-l candidates in C l , we calculate a value l′ =l+3 and a threshold, ρ All length-l candidates with their frequencies larger than ρ are forwarded to a frequent set F l . If any length-l candidate's frequency is less than ρ′, we mark it as "suspicious", which means that this pattern is unlikely to grow further, so we will keep an eye on it. Meanwhile, for any length-l candidate P in C l , if any of P's length-l-2 subpattern is suspicious, we will remove P from the candidate set C l (on lines 11 to 12 in Figure 6). According to Lemmas 1 and 2, if a pattern Q is suspicious, then any length-l patterns with Q as their length l-3 patterns are not going to be frequent. Therefore, if P's length-l-2 subpattern is suspicious, then any length l+1 (and beyond) patterns containing such subpatterns are not going to be frequent. So there is no need to put them into the candidate set C l for growing. As a result, we may safely remove P from the candidate set C l . After MCPaS prunes out candidates from C l , it builds RM for all remaining length-l patterns in C l by rescanning S (on line 13 in Figure 6). MCPaS grows length-l+1 candidates by using all patterns in C l (on line 5 in Figure 6). This can be achieved through the following two techniques: (1) trying all combinations by attaching any possible element pattern to the patterns in C l , or (2) using the popular Apriori candidate generation procedure. Input: (1) Hyper-sequence S and gap M N g , (2) # of element sequences K; (3) alphabet ·; and (4) frequency threshold Output: Frequent pattern set 1. W M-N+1 2. Build length-2 pattern set C 2 , build BM and HM maps for all patterns in C 2 . 3. l 3 4. While (C l-1 · φ ) 5. C l PatternGen(C l-1 ); 6. Predict support values for all candidates in C l (Eq. (4)) 7. l′=l+3 AND calculate threshold ρ′ 8. For any pattern y in C l 9. If Freq(y) · Then F l F l ∪ y 10. If Freq(y) < ρ′ Then y suspicious 11. If any length l-2 subset of y is suspicious 12. Then C l C l \ y 13. Rescan S and build RM for all patterns in C l 14. l l +1; 15. Return (F 3 ∪F 4 …∪F l-1 ) Figure 6. MCPaS Algorithm ## 7 Experimental Results The data used in our experiments are nucleotide DNA sequences downloaded from the National Center for Biotechnology Information website [NCBI], we choose four DNA sequences as our test bed (AX829168, AX829170, AX829174, and AX829178). When using multiple sequences to form a hyper-sequence, we truncate sequences into equal length ones. Because we use DNA sequences, the alphabet for all element sequences is Σ={A, C, T, G}. For comparisons, we implement the MPPm method in [Zhang et al. 05] in finding frequent patterns with gap constraints. This MPPm is the most relevant (and most recent as well) method we can find from all other peers. Table 1 Candidate numbers scanned by different methods | Pattern | Enumerate All | MPP m | MCPaS Pruning | MCPaS | |-----------|-----------------|---------|-----------------|---------| | C 3 | 64 | 64 | 64 | 64 | | C 4 | 256 | 256 | 256 | 256 | | C 5 | 1024 | 1024 | 1024 | 1018 | | C 6 | 4096 | 4096 | 4088 | 3997 | | C 7 | 16384 | 16381 | 15535 | 11461 | | C 8 | 65536 | 54072 | 39728 | 7138 | | C 9 | 262144 | 19675 | 16108 | 1581 | | C 10 | 1048576 | 3459 | 2653 | 273 | | C 11 | 4194304 | 414 | 350 | 41 | | C 12 | 16777216 | 42 | 38 | 13 | | C 13 | 4 13 | 3 | 3 | 2 | ## 7.1 Pruning Efficiency Comparison We provide in this subsection a pruning efficiency comparison with MPP m by using a single DNA sequence AX829174 (by randomly sampling a L=1000 subsequence). In Table 1, we report the experimental results (by the average results of 10 executions), where the first column means the candidate pattern set with different lengths. The second column indicates the number of candidates one has to evaluate, if enumerating all combinations. The third column means the number of candidates evaluated by MPP m . Because MCPaS uses two approaches, map-based support prediction and Lemma 2, for pruning, we'd like to assess their efficiency separately. We first discard the map-based support prediction in the algorithm by replacing line 6 with line 13 in Figure 6. The results are denoted by MCPaS Prunning . After that, we use both map-based support prediction and Lemma 2 for pruning, with results denoted by MCPaS. When comparing MCPaS Prunning and MPP m , we find that MCPaS Prunning has about 20% or fewer candidates than MPP m . A further study on MCPaS Prunning and MMP m reveals that they have opposite pruning mechanisms. In MCPaS Prunning , patterns are growing and pruned orderly, which means that we generate length-l candidates, prune out unlikely ones, grow candidates and repeat the algorithm until the candidate set is empty. On the other hand, MPP m uses reverse pruning mechanisms. It first determines the maximal length of the frequent pattern n, and based on this value, works out the minimal support values for different lengths of patterns. Not only the value n might be determined inaccurately (an inaccurate n will therefore reduce the pruning efficiency), even if n is perfectly determined, it will leave the selected threshold (for length n-1, n-2, …, 3) to be relatively small, because it has to consider the worst scenarios. When combined with the map-based frequent prediction mechanism, MCPaS makes dramatic improvement in reducing the number of candidates in C l . For example, the number of patterns needs to be scanned in C 8 is 7138, which is about 86.8% less than the number of patterns scanned by MMP m . ## 7.2 Pattern Search Efficiency Comparison Figure 7. Pattern search efficiency (W=4, L=1000, AX829174) ![Image](https://ijcai.org/proceedings/2007/fulltext/472/image_000004_314cf86c9ef837a7c54b2638fbab5c4be721cbfd68a0dcb4761a0139b3f5632e.png) Figure 8. Pattern mining performance from single sequence ![Image](https://ijcai.org/proceedings/2007/fulltext/472/image_000005_ab7c1f9dcc78e6931d81fb413d1a1b141d12e7cf91021c742b93bae863f95394.png) To assess the performances of the proposed GCS mechanism in comparison with exhaustive search, we sample a length L=1000 subsequence from AX829174, then use two search mechanisms and record their average search time (in seconds) for every 1000 patterns, and report the results in Figure 7 (the average results of 10 executions). In Figure 7, the x-axis denotes the length of the patterns, the dash line indicates the results of exhaustive search (corresponding to the y-axis on the left side of the figure), and the solid line with crosses represents the results from GCS (corresponding to the y-axis on the right side of the figure). Comparing to exhaustive search, GCS is normally 5 to 10 times faster in searching (depending on the actual length of the patterns). Because exhaustive search's time complexity exponentially increases along with the pattern length and the gap flexibility, GCS can possibly achieve more improvements for longer patterns or larger gap constraints. ## 7.3 Pattern Mining Performance Comparison To assess overall pattern mining performances, we first use a single sequence AX829174 with a fixed value W=4. We randomly sample a length L=1000 subsequence from AX829174, then use MPP m and MCPaS to mine the results by specifying different threshold values ρ. We report the average runtime (from 10 executions) in Figure 8, where the x-axis means the value of ρ, the dash line indicates the results from MPP m and the solid line with crosses denotes the results from MCPaS (corresponding to the y-axis on the left and right side of Fig. 8 respectively). Both MPP m and MCPaS nonlinearly respond to the threshold ρ with pretty similar shapes. This is because the value of ρ nonlinearly determines the number of candidates of the system. On average, MCPaS is about 40 times faster than MPP m , with its improvement mainly comes from three aspects: (1) an ordinal pruning from Lemma 2; (2) mapbased support prediction; and (3) GCS based search. GCS alone can enhance the search speed for about 8 times (comparing to exhaustive search), and the other two aspects will generally contribute a speed improvement of about 5 times. In Figure 9, we report the results from the hyper-sequence consisting of one to up to four sequences (due to the intensive time consumption, we were only able to run the programs for only one time for 3 or 4 sequences). The x-axis in Figure 9 represents the number of element sequences, and the y-axis denotes the average runtime of MCPaS. Because MPP m and MCPaS have huge runtime differences, we report MPPm's runtime in a small table in Figure 9. Meanwhile, for a hyper-sequence with K=4 element sequences, MPP m 's runtime is too big, so we omit the value at this point. 12 x 10 4 Figure 9. Pattern mining performance from multiple sequences ![Image](https://ijcai.org/proceedings/2007/fulltext/472/image_000006_a6394486b94c3cacc48dad8db7634f24e6a968b92759d50b6ae9d4a18b3ee437.png) The results in Figure 9 show that MCPaS's runtime exponentially increases by the number of element sequences K. Although this sounds disappointing, to understand the challenge of our problem, let's assume that S merely consists of two DNA element sequences, then each element pattern p i has (|Σ|+1) 2 -1=(4+1) 2 -1=24 possibilities (excluding the one consisting of wildcards only). So the number of length-5 candidate patterns is 24 5 =7962624, if no pruning techniques are involved. Although we can transform element sequences to form a hybrid sequence and apply MPP m to solve the problem, because of the large alphabet size and the less effective reverse pruning technique, most of the length-5 candidates are going to be treated as frequent and used to grow next level candidates. MCPaS on the other hand, will start to prune candidates from length-4 candidates, and for length-5 patterns it will reduce about 80% of candidates (if S consists of 2 element sequences). The above observations make us believe that although MCPaS is nonlinear w.r.t. the number of element sequences K, when mining complex patterns from hyper-sequences, it is much more practical in reality. ## 8 Conclusions We have studied in this paper the problem of mining complex patterns across multiple sequences with gap requirements, where patterns repetitively appear in multiple sequences and their matching appearances are flexibly confined by users' gap requirements. Because of the exponential candidate explosion, traditional Apriori-based solutions are technically infeasible to solve the problem. We have proposed MCPas with three unique features to fulfill the task: (1) an Apriori-like mining framework which allows pattern generation and growing to be conducted step by step; (2) map-based support predication to predict candidates' frequency without rescanning; and (3) a gap constrained linear-time pattern search. Experimental comparisons have shown that each of the above techniques has made a contribution, and the overall performances of MCPas have been about 40 times faster than its other peers. ## References 1. S. Altschul, W. Gish, W. Miller, E. Myers, & D. Lipman, Basic local alignment search tool. Journal of Molecular Biology, 215:403-410, 1990. 2. R. E. Bellman. Dynamic Programming, Princeton University Press, 1957. 3. Belkum et al. 97 4. A. van Belkum, S. Scherer amd W. van Leeu- wen, D. Willemse, L. van Alphen, & H. Verbrugh. Variable num- ber of tandem repeats in clinical strains of haemophilus influenzae. Infection and Immunity, 65(12):5017-5027, 1997. 5. Chen et al. 05 6. G. Chen, X. Wu, & X. Zhu, Sequential pattern mining in multiple data streams, Proc. of ICDM, TX, 2005. 7. Das et al. 98 8. G. Das, K. Lin, H. Mannila, G. Renganathan, & P. Smyth, Rule discovery from time series, Proc. of KDD, 1998. 9. Herzel et al. 99 10. H. Herzel, O. Weiss, & E. Trifonov, 10-11 BP periodicities in complete genomes reflect protein structure and DNA folding, Bioinformatics, 15(3):187-193, 1999. 11. I. Jonassen, Efficient discovery of conserved pat- terns using a pattern graph, Computer Applications in the Biosci- ences, 13:509-522, 1997. 12. Mannila et al. 97 13. H. Mannila, H. Toivonen, and A.I. Verkamo. Discovery of frequent episodes in event sequences. Data Mining & Knowledge Discovery, 1(3), 1997. 14. & Rigotti 04 15. N. Méger, C. Rigotti: Constraint-based min- ing of episode rules and optimal window. Proc. of PKDD, 2004. 16. Murray et al. 02 17. K. Murray, D. Gorse, & J. Thornton, Wavelet transforms for the characterization and detection of repeating mo- tifs, Journal of Molecular Biology, 316:341-363, 2002. [NCBI] NCBI: http://www.ncbi.nlm.nih.gov 18. & Cohen 96 19. T. Oates & P. Cohen, Searching for structure in multiple streams of data, Proc. of ICML, 1996. 20. Pei et al. 01 21. J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal, & M. Hsu. PrefixSpan: Mining Sequential Patterns Effi- ciently by Prefix-Projected Pattern Growth, Proc. of ICDE, 2001. 22. Pino et al. 01 23. H. Pinto, J. Han, J. Pei, K. Wang, Q. Chen, & U. Dayal, Multi-dimensional sequential pattern mining, Proc. of CIKM, 2001. 24. Rigoutsos & Floratos 98] 25. I. Rigoutsos & A. Floratos. Combinato- rial pattern discovery in biological sequences: the teiresias algo- rithm. Bioinformatics, 14(1), 1998. 26. Srikant & Agrawal 96] 27. R. Srikant & R. Agrawal, Mining Sequen- tial Patterns: Generalizations and Performance Improvements, Proc. of the International Conf. on Extending DB Tech., 1996. 28. Yang et al. 00 29. J. Yang, W. Wang, & P. Yu, Mining asynchronous periodic patterns in time series data, Proc. of KDD, MA, 2000. 30. M. Zaki, Efficient enumeration of frequent sequences, Proc. of CIKM, November 2-7, 1998, Bethesda, Maryland. 31. Zhang et al. 05 32. M. Zhang, B. Kao, D. Cheung, & K. Yip, Mining periodic patterns with gap requirement from sequences, Proc. of ACM SIGMOD, Baltimore Maryland, 2005.