ACM Transactions on Knowledge Discovery from Data · 2007 · 100 citations · 21 references
ComputingBioinformaticsAlgorithmsData MiningSequence AnalysisFrequent Pattern MiningGap PenaltiesPattern RecognitionSequence MiningFrequent Subsequence MiningGap-constrained Pattern MiningPattern Matching AlgorithmsPattern Mining In SequencesPatternsPeriodic Pattern Mining
We study a problem of mining frequently occurring periodic patterns with a gap requirement from sequences. Given a character sequence S of length L and a pattern P of length l , we consider P a frequently occurring pattern in S if the probability of observing P given a randomly picked length- l subsequence of S exceeds a certain threshold. In many applications, particularly those related to bioinformatics, interesting patterns are periodic with a gap requirement . That is to say, the characters in P should match subsequences of S in such a way that the matching characters in S are 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.
21
Basic local alignment search tool
Stephen F. Altschul, Warren Gish, Webb Miller et al. · Journal of Molecular Biology · 1990 · 94.5K citations
Mining association rules between sets of items in large databases
Rakesh Agrawal, Tomasz Imieliński, Arun Swami · 1993 · 14.8K citations · Full text
The National Center for Biotechnology Information
D. A. Benson, Mark S. Boguski, David J. Lipman et al. · Genomics · 1990 · 5.2K citations · Full text
The Mosaic Genome of Warm-Blooded Vertebrates
Giorgio Bernardi, Birgitta Olofsson, Jan Filipski et al. · Science · 1985 · 888 citations