Minghua Zhang
Abstract
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.
- Agarwal, R., Imielinski, T., and Swami, A. 1993. Mining association rules between sets of items in large databases. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. ACM, New York, 207--216. Google Scholar
Digital Library
- Altschul, S. F., Gish, W., Miller, W., Myers, E. W., and Lipman, D. J. 1990. Basic local alignment search tool. J. Molec. Biol. 215, 403--410.Google ScholarCross Ref
- Bairoch, A. and Boeckmann, B. 1992. The swiss-prot protein sequence data bank. Nucleic Acids Res. 20, Suppl, 2019--2022.Google ScholarCross Ref
- Bernardi, G., Olofsson, B., Filipski, J., Zerial, M., Salinas, J., Cuny, G., Meunier-Rotival, M., and Rodier, F. 1985. The mosaic genome of warm-blooded vertebrates. Science 228, 4702, 953--958.Google Scholar
- Coward, E. and Drablos, F. 1998. Detecting periodic patterns in biological sequences. Bioinformatics 14, 6, 498--507.Google ScholarCross Ref
- Fickett, J. W. and Tung, C. S. 1992. Assessment of protein coding measures. Nucleuic Acids Res. 20, 6441--6450.Google ScholarCross Ref
- Han, J., Dong, G., and Yin, Y. 1999. Efficient mining of partial periodic patterns in time series database. In Proceedings of the 15th International Conference on Data Engineering, (ICDE99). 106--115. Google ScholarDigital Library
- Herzel, H., Weiss, O., and Trifonov, E. N. 1999. 10-11 bp periodicities in complete genomes reflect protein structure and DNA folding. Bioinformatics 15, 3, 187--193.Google ScholarCross Ref
- Jonassen, I. 1996. Efficient discovery of conserved patterns using a pattern graph. Tech. Rep. Report No. 118, University of Bergen.Google Scholar
- Kurtz, S., Ohlebusch, E., Schleiermacher, C., Stoye, J., and Giegerich, R. 2000. Computation and visualization of degenerate repeats in complete genomes. In Proceedings of the 8th International Conference on Intelligent Systems for Molecular (ISMB-00). Google ScholarDigital Library
- Mannila, H., Toivonen, H., and Verkamo, A. I. 1997. Discovery of frequent episodes in event sequences. Data Mining and Knowledge Discovery 1, 3 (Nov.), 259--289. Google ScholarDigital Library
- NCBI. The National Center for Biotechnology Information web site. http://www.ncbi.nlm.nih.gov.Google Scholar
- Pei, J., Han, J., Mortazavi-Asl, B., Pinto, H., Chen, Q., Dayal, U., and Hsu, M.-C. 2001. Prefixspan: Mining sequential patterns by prefix-projected growth. In Proceedings of the 17th IEEE International Conference on Data Engineering (ICDE) (Heidelberg, Germany). IEEE Computer Society Press, Los Alamitos, CA. Google ScholarDigital Library
- Reddy, P. and Housman, D. 1997. The complex pathology of trinucleotide repeats. Current Opinion in Cell Biology 9, 3, 364--372.Google ScholarCross Ref
- Rigoutsos, I. and Floratos, A. 1998. Combinatorial pattern discovery in biological sequences: the teiresias algorithm. Bioinformatics 14, 1.Google Scholar
- Srikant, R. and Agrawal, R. 1996. Mining sequential patterns: Generalizations and performance improvements. In Proceedings of the 5th Conference on Extending Database Technology (EDBT) (Avignion, France). Google ScholarDigital Library
- Tomita, M., Wada, M., and Kawashima, Y. 1999. ApA dinucleotide periodicity in prokaryote, eukaryote, and organelle genomes. J. Molec. Evolut. 49, 182--192.Google ScholarCross Ref
- Trifonov, E. N. 1998. 3-, 10.5-, 200- and 400-base periodicities in genome sequences. Physica A 249, 511--516.Google ScholarCross Ref
- van Belkum, A., W. van Leeuwen, S. S., Willemse, D., van Alphen, L., and Verbrugh, H. 1997. Variable number of tandem repeats in clinical strains of haemophilus influenzae. Infect. Immun. 65, 12, 5017--5027.Google ScholarCross Ref
- Widom, J. 1996. Short-range order in two eukaryotic genomes: Relation to chromosome structure. J. Molec. Biol. 259, 579--588.Google ScholarCross Ref
- Yang, J., Wang, W., and Yu, P. S. 2000. Mining asynchronous periodic patterns in time series data. In Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (Boston, MA). ACM, New York, 275--279. Google ScholarDigital Library
- Zaki, M. J. 1998. Efficient enumeration of frequent sequences. In Proceedings of the ACM 7th International Conference on Information and Knowledge Management (CIKM'98) (Washington). ACM, New York. Google ScholarDigital Library
- Zhang, M., Kao, B., Cheung, D. W., and Yip, K. Y. 2005. Mining periodic patterns with gap requirement from sequences. In Proceedings of the ACM SIGMOD Conference on Management of Data. ACM, New York. Google ScholarDigital Library
- Zhang, M., Kao, B., Yip, C., and Cheung, D. 2001. A GSP-based efficient algorithm for mining frequent sequences. In Proceedings of IC-AI'2001 (Las Vegas, NV).Google Scholar
Index Terms
- Mining periodic patterns with gap requirement from sequences
Recommendations
Mining periodic patterns with gap requirement from sequences
SIGMOD '05: Proceedings of the 2005 ACM SIGMOD international conference on Management of dataWe 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 ...
Efficient algorithms to identify periodic patterns in multiple sequences
AbstractPeriodic pattern mining is a popular data mining task, which consists of identifying patterns that periodically appear in data. Traditional periodic pattern mining algorithms are designed to find patterns in a single sequence. However, ...
Discovering Periodic Patterns Common to Multiple Sequences
Big Data Analytics and Knowledge DiscoveryAbstractDiscovering periodic itemsets in transaction databases is an emerging data mining task. However, current algorithms are designed to discover periodic itemsets in a single sequence. But in real-life, it is desirable to find periodic patterns that ...
Comments