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.
- Stephen F. Altschul, Warren Gish, Webb Miller, Eugene W. Myers, and David J. Lipman. Basic local alignment search tool. Journal of Molecular Biology, 215:403--410, 1990.Google Scholar
Cross Ref
- A. Bairoch and B. Boeckmann. The swiss-prot protein sequence data bank. Nucleic Acids Research, 20(Suppl):2019--2022, 1992.Google Scholar
- Giorgio Bernardi, Birgitta Olofsson, Jan Filipski, Marino Zerial, Julio Salinas, Gerard Cuny, Michele Meunier-Rotival, and Francis Rodier. The mosaic genome of warm-blooded vertebrates. Science, 228(4702):953--958, 1985.Google ScholarCross Ref
- Eivind Coward and Finn Drablos. Detecting periodic patterns in biological sequences. Bioinformatics, 14(6):498--507, 1998.Google ScholarCross Ref
- J. W. Fickett and C. S. Tung. Assessment of protein coding measures. Nucleuic Acids Research, 20:6441--6450, 1992.Google ScholarCross Ref
- Jiawei Han, Guozhu Dong, and YiWen Yin. Efficient mining of partial periodic patterns in time series database. In Proc. of 15th International Conference on Data Engineering, ICDE99, pages 106--115, 1999. Google ScholarDigital Library
- H. Herzel, O. Weiss, and E. N. Trifonov. 10--11 bp periodicities in complete genomes reflect protein structure and DNA folding. Bioinformatics, 15(3):187--193, 1999.Google ScholarCross Ref
- Inge Jonassen. Efficient discovery of conserved patterns using a pattern graph. Technical Report Report No. 118, University of Bergen, 1996.Google Scholar
- Stefan Kurtz, Enno Ohlebusch, Chris Schleiermacher, Jens Stoye, and Robert Giegerich. Computation and visualization of degenerate repeats in complete genomes. In Proceedings of the 8th International Conference on Intelligent Systems for Molecular (ISMB-00), 2000. Google ScholarDigital Library
- H. Mannila, H. Toivonen, and A. I. Verkamo. Discovery of frequent episodes in event sequences. Data Mining and Knowledge Discovery, 1(3):259--289, Nov 1997. Google ScholarDigital Library
- http://www.ncbi.nlm.nih.gov.Google Scholar
- Jian Pei, Jiawei Han, Behzad Mortazavi-Asl, Helen Pinto, Qiming Chen, Umeshwar Dayal, and Mei-Chun Hsu. Prefixspan: Mining sequential patterns by prefix-projected growth. In Proc. 17th IEEE International Conference on Data Engineering (ICDE), Heidelberg, Germany, April 2001. Google ScholarDigital Library
- T. Imielinski R. Agrawal and A. Swami. Mining association rules between sets of items in large databases. In Proc. ACM SIGMOD International Conference on Management of Data, page 207, Washington, D.C., May 1993. Google ScholarDigital Library
- P. S. Reddy and D. E. Housman. The complex pathology of trinucleotide repeats. Current Opinion in Cell Biology, 9(3):364--372, 1997.Google ScholarCross Ref
- Isidore Rigoutsos and Aris Floratos. Combinatorial pattern discovery in biological sequences: the teiresias algorithm. Bioinformatics, 14(1), 1998.Google Scholar
- Ramakrishnan Srikant and Rakesh Agrawal. Mining sequential patterns: Generalizations and performance improvements. In Proc. of the 5th Conference on Extending Database Technology (EDBT), Avignion, France, March 1996. Google ScholarDigital Library
- Masaru Tomita, Masahiko Wada, and Yukihiro Kawashima. ApA dinucleotide periodicity in prokaryote, eukaryote, and organelle genomes. Journal of Molecular Evolution, 49:182--192, 1999.Google ScholarCross Ref
- E. N. Trifonov. 3-, 10.5-, 200- and 400-base periodicities in genome sequences. Physica A, 249:511--516, 1998.Google ScholarCross Ref
- A. van Belkum, S. Scherer amd W. van Leeuwen, D. Willemse, L. van Alphen, and H. Verbrugh. Variable number of tandem repeats in clinical strains of haemophilus influenzae. Infection and Immunity, 65(12):5017--5027, 1997.Google ScholarCross Ref
- J. Widom. Short-range order in two eukaryotic genomes: Relation to chromosome structure. Journal of Moleular Biology, 259:579--588, 1996.Google ScholarCross Ref
- Jiong Yang, Wei Wang, and Philip S. Yu. Mining asynchronous periodic patterns in time series data. In Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 275--279, Boston, MA USA, 2000. Google ScholarDigital Library
- Mohammed J. Zaki. Efficient enumeration of frequent sequences. In Proceedings of the 1998 ACM 7th International Conference on Information and Knowledge Management(CIKM'98), Washington, United States, November 1998. Google ScholarDigital Library
- Minghua Zhang, Ben Kao, David W. Cheung, and Kevin Y. Yip. Mining periodic patterns with gap requirement from sequences. Technical Report TR-2005-04, Department of Computer Science, The University of Hong Kong, 2005.Google ScholarDigital Library
- Minghua Zhang, Ben Kao, C. L. Yip, and David Cheung. A GSP-based efficient algorithm for mining frequent sequences. In Proc. of IC-AI'2001, Las Vegas, Nevada, USA, June 2001.Google Scholar
- Mining periodic patterns with gap requirement from sequences
Recommendations
Mining periodic patterns with gap requirement from sequences
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 ...
Discovering Skyline Periodic Itemset Patterns in Transaction Sequences
Advanced Data Mining and ApplicationsAbstractAs an extended version of frequent itemset patterns, periodic itemset patterns concern both the frequency and periodicity of itemsets at the same time, so they contain more information than frequent itemset patterns, which only concern the ...
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, ...
Comments