NetNMSP: Nonoverlapping maximal sequential pattern mining
- 10 January 2022
- journal article
- research article
- Published by Springer Nature in Applied Intelligence
- Vol. 52 (9) , 9861-9884
Abstract
Nonoverlapping sequential pattern mining, as a kind of repetitive sequential pattern mining with gap constraints, can find more valuable patterns. Traditional algorithms focused on finding all frequent patterns and found lots of redundant short patterns. However, it not only reduces the mining efficiency, but also increases the difficulty in obtaining the demand information. To reduce the frequent patterns and retain its expression ability, this paper focuses on the Nonoverlapping Maximal Sequential Pattern (NMSP) mining which refers to finding frequent patterns whose super-patterns are infrequent. In this paper, we propose an effective mining algorithm, Nettree for NMSP mining (NetNMSP), which has three key steps: calculating the support, generating the candidate patterns, and determining NMSPs. To efficiently calculate the support, NetNMSP employs the backtracking strategy to obtain a nonoverlapping occurrence from the leftmost leaf to its root with the leftmost parent node method in a Nettree. To reduce the candidate patterns, NetNMSP generates candidate patterns by the pattern join strategy. Furthermore, to determine NMSPs, NetNMSP adopts the screening method. Experiments on biological sequence datasets verify that not only does NetNMSP outperform the state-of-the-arts algorithms, but also NMSP mining has better compression performance than closed pattern mining. On sales datasets, we validate that our algorithm guarantees the best scalability on large scale datasets. Moreover, we mine NMSPs and frequent patterns in SARS-CoV-1, SARS-CoV-2 and MERS-CoV. The results show that the three viruses are similar in the short patterns but different in the long patterns. More importantly, NMSP mining is easier to find the differences between the virus sequences.Keywords
This publication has 70 references indexed in Scilit:
- Efficient discovery of contrast subspaces for object explanation and characterizationKnowledge and Information Systems, 2015
- Strict approximate pattern matching with general gapsApplied Intelligence, 2014
- Sliding window based weighted maximal frequent pattern mining over data streamsExpert Systems with Applications, 2014
- Mining sequential patterns with periodic wildcard gapsApplied Intelligence, 2014
- Mining maximal frequent patterns by considering weight conditions over data streamsKnowledge-Based Systems, 2014
- Mining high utility itemsets by dynamically pruning the tree structureApplied Intelligence, 2013
- Isolation of a Novel Coronavirus from a Man with Pneumonia in Saudi ArabiaNew England Journal of Medicine, 2012
- Efficient Mining of Gap-Constrained Subsequences and Its Various ApplicationsACM Transactions on Knowledge Discovery From Data, 2012
- Mining periodic patterns with gap requirement from sequencesACM Transactions on Knowledge Discovery From Data, 2007
- Analysis of multimerization of the SARS coronavirus nucleocapsid proteinBiochemical and Biophysical Research Communications, 2004