Computer Science ›› 2018, Vol. 45 ›› Issue (4): 252-256.doi: 10.11896/j.issn.1002-137X.2018.04.042

Previous Articles     Next Articles

Distinguishing Sequence Patterns Mining Based on Density and Gap Constraints

WEI Qin-shuang, WU You-xi, LIU Jing-yu and ZHU Huai-zhong   

  • Online:2018-04-15 Published:2018-05-11

Abstract: Distinguishing patterns mining is an important branch of sequence patterns mining,and distinguishing patterns with density constraint can help biologists to find the distribution of special factors on biological sequences.This paper proposed an algorithm,named MPDG(Mining distinguishing sequence Patterns based on Density and Gap constraint),which employs Nettree data structure to mine the distinguishing patterns satisfying the density and gap constraints.The algorithm is efficient since it calculates all super-patterns’ supports of current pattern with one-way scanning the sequence database.Experimental results on real protein datasets verify the effectiveness of MPDG.

Key words: Pattern mining,Distinguishing pattern,Density constraint,Nettree

[1] AGRAWAL R,SRIKANT R.Mining sequential patterns [C]∥11th International Conference on Data Engineering.1995:3-14.
[2] ZHANG L,LUO P,TANG L,et al.Occupancy-based frequentpattern mining [J].ACM Transactions on Knowledge Discovery from Data(ACM TKDD),2015,10(2):1-33.
[3] MIN F,WU Y,WU X.The Apriori property of sequence pattern mining with wildcard gaps [J].International Journal Functional Informatics and Personalised Medicine,2010,4(1):138-143.
[4] DING B,LO D,HAN J,et al.Efficient mining of closed repetitive gapped subsequences from a sequence database[C]∥International Conference on Data Engineering.IEEE Computer Society,2009:1024-1035.
[5] FANG W W,XIE W,HUANG H B,et al.Sequential pattern mining based on privacy preserving [J].Computer Science,2016,43(12):195-199.(in Chinese) 方炜炜,谢伟,黄宏博,等.基于隐私保护的序列模式挖掘[J].计算机科学,2016,43(12):195-199.
[6] DONG G,LI J.Efficient mining of emerging patterns:Discovering trends and differences[C]∥Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,1999:43-52.
[7] GHOSH S,FENG M,NGUYEN H,et al.Risk prediction foracute hypotensive patients by using gap constrained sequential contrast patterns [C]∥AMIA Annual Symposium Proceedings American Medical Informatics Association.2014:1748-1754.
[8] JI X,JAMES B,DONG G.Mining minimal distinguishing subsequence patterns with gap constraints [J].Knowledge Information Systems,2007,11(3):259-286.
[9] WANG X,DUAN L,DONG G,et al.Efficient mining of density-aware distinguishing sequential patterns with gap constraints [C]∥19th International Conference of Database Systems for Advanced Applications.2014:372-387.
[10] YANG H,DUAN L,HU B,et al.Mining top-k distinguishing sequential patterns with gap constraint [J].Journal of Software,2015,6(11):2994-3009.(in Chinese) 杨皓,段磊,胡斌,等.带间隔约束的Top-k对序列模式挖掘[J].软件学报,2015,26(11):2994-3009.
[11] WANG H F,DUAN L,ZUO J,et al.Efficient mining of distinguishing sequential patterns without a predefined gap constraint [J].Journal of Computer,2016,39(10):1979-1991.(in Chinese) 王慧锋,段磊,左劼,等.免预设间隔约束的对比序列模式高效挖掘[J].计算机学报,2016,39(10):1979-1991.
[12] WU Y X,WU X D,JIANG H,et al.A heuristic algorithm for MPMGOOC [J].Journal of Computers,2011,4(8):1452-1462.(in Chinese) 武优西,吴信东,江贺,等.一种求解MPMGOOC问题的启发式算法[J].计算机学报,2011,34(8):1452-1462.
[13] WU Y,TANG Z,JIANG H,et al.Approximate Pattern Matching with Gap Constraints[J].Journal of Information Science,2016,42(5):639-658.
[14] WU Y,FU S,JIANG H,et al.Strict approximate pattern matching with general gaps[J].Applied Intelligence,2015,42(3):566-580.
[15] WU Y,WANG L,REN J,et al.Mining sequential patterns with periodic wildcard gaps[J].Applied Intelligence,2014,41(1):99-116.

No related articles found!
Full text



[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[3] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[4] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[5] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[6] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[7] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[8] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[9] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[10] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .