Abstract

The rapid development of bioinformatics has resulted in the explosion of DNA sequence data which is characterized by large number of items. Studies have shown that biological functions are dictated by contagious portions of the DNA sequence. Finding contiguous frequent patterns from long data sequences such as DNA sequences is a particularly challenging task and can pave the way towards new breakthroughs. Apriori based techniques were among the first to be used in frequent contagious pattern mining. Later improved approaches like GSP, Prefix Span were also applied but the approaches required either large number of sequence scans, generated large number of candidates or required higher number of intermediate sequential patterns. In this paper an improvement of the positional based approach for contagious frequent pattern mining is DNA sequences is proposed. The proposed algorithm improves the existing positional based approach by introducing a new amalgamated sorting and joining technique which helps to reduce time and space complexity. The proposed approach outperforms traditional existing contiguous frequent mining approaches.

References

• Shuang Bai, Si-Xue Bai, "The Maximal Frequent Pattern Mining of DNA Sequence", GrC, pp 23-26, 2009.
• T. H Kang, J. S Yoo and H, Y Kim, "Mining frequent contiguous sequence patterns in biological sequences", in proceeding of the 7th IEEE International Conference on Bioinformatics and Bioengineering, pp 723-8, 2007.
• R. Wanger and M. Fischer "The string-to-string Correction Problem" J. of the ACM (JACM), Vol 21, No 1, pp. 168-173, 1974.
• D. Hirschberg "Algorithms for the longest common subsequence problem" J. of the ACM (JACM). Vol 24, No 4, pp. 664-675, 1977.
• M. Garofalakis, R. Rastogi, and K. Shim, "Spirit: Sequential pattern mining with regular expression constraints. " In Proc. 1999 Int. Conf. Very Large Data Bases (VLDB'99), pages 223–234, Edinburgh, UK, Sept. 1999.
• R. Srikant and R. Agrawal, "Mining sequential patterns: Generalizations and performance improvements. " In Proc. 5th Int. Conf. Extending Database Technology (EDBT'96), pages 3–17, Avignon, France, Mar. 1996.
• R. Agrawal and R. Srikant, "Fast algorithms for mining association rules. " In Proc. 1994 Int. Conf. Very Large Databases (VLDB'94), pages 487–499, Santiago, Chile, Sept. 1994.
• J. Pei, J. Han, B. Mortazavi-Asl, Q. Chen, U. Dayal, and M. C. Hsu, "PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth. " InICDE'01, Germany, April 2001.
• J. Pan, p. Wang, W. Wang, B. Shi and G. Yang, "Efficient algorithms for mining maximal frequent concatenate sequences in biological datasets", in proceeding of the fifth International Conference on Computer and Information Technology (CIT), , pp 98-104, 2005.
• . Zerin SF, Ahmed CF, Tanbeer SK, Jeong BS, "A fast in-dexed-based contiguous sequential pattern mining tech-nique in biological data sequences. " In: Proceeding of 2nd International Conference on Emerging Databases (EBD'10), 2010 Aug 30-31, Jeju.
• Rashid MM, Karim MR, Hossain MA, Jeong BS, "An ef-ficient approach for mining significant contiguous fre-quent patterns in biological sequences. " In: Proceeding of 3rd International Conference on Emerging Databases (EBD'11), 2011 Aug 25-27, Incheon
• Rashid MM, Karim MR, Hossain MA, Jeong BS and -Jin Choi, "Efficient Mining of Interesting Patterns in Large Biological Sequences. " Genomics & Informatics Vol. 10(1) 44-50, March 2012
• Jiawei Han & Micheline Kamber , "Data Mining Concepts and Techniques", Elsevier, 2006.
• Pan-Ning Tan, Vipin Kumar, Michael Steinbach , " Introduction to Data Mining", Pearson Education Inc, 2006