next up previous
Next: Genome List Up: Home Previous:Distance Constrained Pattern Mining

1.2 Algorithm for set pattern mining



twinPatternMining($ R^{T_p}, T_p, T_s, G = \{G_1,\dots,G_n\}$)  
// Check if there is $ P_{set}$ with support $ T_s$ for a given $ P_{dset}(R^{T_p})$ 

1)	$ {\mathcal W}_{j_1,\dots,j_m}$ = twinOccurrence($ R^{T_p}, \{G_1,\dots,G_n\}$) 
2)	if ($ m \ge T_s$) return $ {\mathcal W}_{j_1,\dots,j_m}$;
// Since there are no $ T_s$ genomes where each genome has all occurrences of $ P_{dset}$, 
// we need to shrink $ R^{T_p}$ as long as $ \vert P_{dset}(R^{T_p})\vert \ge T_z$.
3)	while ( $ \vert P_{dset}(R^{T_p})\vert > T_z$) 
4)		$ R^{T_p}$ = shrinkPDSETbyOne($ P_{dset}, T_p$); 
5)		if ($ P_{dset} = \emptyset$) return $ \emptyset$
6)		$ {\mathcal W}_{j_1,\dots,j_m}$ = twinOccurrence($ R^{T_p}, \{G_1,\dots,G_n\}$);
7)		if ($ m \ge T_s$) 
8)			print $ P_{dset}$ and $ {\mathcal W}_{j_1,\dots,j_m}$;
		endif 
	endwhile 




shrinkPDSETbyOne($ R, T_p$) 
1)	Let $ R = (r_1,\dots,r_k)$ 
2)	for $ i = 1 $to $ k$do 
3)		Let $ r_i = (G_{i_1}, j_b, j_e)$; 
4)		Locate $ j$ from $ j_b$ with incrementing by one such that $ P_{dset}((G_{i_1}, j, j_e)) + 1 == P_{dset}(R) $; 
5)		$ T$ = ComputeMdsetMatch($ T_z,(r_1,\dots,r_{i-1}, r_{i+1}, \dots, r_{k}), (G_{i_1}, j, j_e)$);  
6)		if ( $ \vert P_{dset}(T)\vert +1 == \vert P_{dset}\vert$) return $ T$;

7)		Locate $ j$ from $ j_e$ with decrementing by one such that $ P_{dset}((G_{i_1}, j_b, j)) + 1 == P_{dset}(R) $; 
8)		$ T$ = ComputeMdsetMatch($ T_z,(r_1,\dots,r_{i-1}, r_{i+1}, \dots, r_{k}), (G_{i_1}, j_b, j)$);  
9)		if ( $ \vert P_{dset}(T)\vert +1 == \vert P_{dset}\vert$) return $ T$;
	endfor 
10)	return $ \emptyset$; 



twinOccurrence($ R, \{G_1,\dots,G_n\}$) 
1)	for $ i = 1 $to $ k$do 
2)		if ($ G_i \in GENOME(R)$) continue ; 
3)		if ($ P_{dset}(R)$ occurs in its entirety in $ G_i$)  
4)			Let $ W_i$ be the occurrence of $ R$ in $ G_i$; 
5)			$ {\mathcal W}_{j_1,\dots,j_m,i} = {\mathcal W}_{j_1,\dots,j_m} \bigcup \{W_i\}$; 
		endif 
	endfor

next up previous
Next: Genome List Up: Home Previous:Distance Constrained Pattern Mining