Mining periodic patterns with gap requirement from sequences
Minghua Zhang, Ben Kao, David Wing-Shing Cheung, Kevin Yuk-Lap Yip · ACM Transactions on Knowledge Discovery from Data · 2007
We study a problem of mining frequently occurring periodic patterns with a gap requirement from sequences. Given a character sequenceSof lengthLand a patternPof lengthl, we considerPa frequently occurring pattern inSif the probability ofobservingPgiven a randomly picked length-lsubsequence ofSexceeds a certain threshold. In many applications, particularly those related to bioinformatics, interesting patterns areperiodicwith agap requirement. That is to say, the characters inPshould match subsequences ofSin such a way that the matching characters inSare separated by gaps of more or less the same size. We show the complexity of the mining problem and discuss why traditional mining algorithms are computationally infeasible. We propose practical algorithms for solving the problem and study their characteristics. We also present a case study in which we apply our algorithms on some DNA sequences. We discuss some interesting patterns obtained from the case study.