A linear time algorithm for consecutive permutation pattern matching

OPP-Miner: Order-Preserving Sequential Pattern Mining for Time Series

Traditional sequential pattern mining methods were designed for symbolic sequence. As a collection of measurements in chronological order, a time series needs to be discretized into symbolic sequences, and then users can apply sequential pattern mining methods to discover interesting patterns in time series. The discretization will not only cause the loss of some important information, which partially destroys the continuity of time series, but also ignore the order relations between time-series values. Inspired by order-preserving matching, this article explores a new method called order-preserving sequential pattern (OPP) mining, which does not need to discretize time series into symbolic sequences and represents patterns based on the order relations of time series. An inherent advantage of such representation is that the trend of a time series can be represented by the relative order of the values underneath time series. We propose an OPP-Miner algorithm to mine frequent patterns in time series with the same relative order. OPP-Miner employs the filtration and verification strategies to calculate the support and uses the pattern fusion strategy to generate candidate patterns. To compress the result set, we also study to find the maximal OPPs. Experimental results validate that OPP-Miner is not only efficient but can also discover similar subsequences in time series. In addition, case studies show that our algorithms have high utility in analyzing the COVID-19 epidemic by identifying critical trends and improve the clustering performance. The algorithms and data can be downloaded from https://github.com/wuc567/Pattern-Mining/tree/master/OPP-Miner.

An Improved Order-Preserving Pattern Matching Algorithm Using Fingerprints

Two strings of the same length are order isomorphic if their relative orders are the same. The order-preserving pattern matching problem is to find all substrings of text T that are order isomorphic to pattern P when T(|T|=n) and P(|P|=m) are given. An O(mn+nqlogq+q!)-time algorithm using the O(m+q!) space for the order-preserving pattern matching problem has been proposed utilizing fingerprints of q-grams based on the factorial number system and the bad character heuristic. In this paper, we propose an O(mn+2q)-time algorithm using the O(m+2q) space for the order-preserving pattern matching problem, but utilizing fingerprints of q-grams converted to binary numbers. A comparative experiment using three types of time series data demonstrates that the proposed algorithm is faster than existing algorithms because it reduces the number of order isomorphism tests.

POPBic: Pathway-Based Order Preserving Biclustering Algorithm Towards the Analysis of Gene Expression Data

To understand the underlying biological mechanisms of gene expression data, it is important to discover the groups of genes that have similar expression patterns under certain subsets of conditions. Biclustering algorithms have been effective in analyzing large-scale gene expression data. Recently, traditional biclustering has been improved by introducing biological knowledge along with the expression data during the biclustering process. In this paper, we propose the Pathway-based Order Preserving Biclustering (POPBic) algorithm by incorporating Kyoto Encyclopedia of Genes and Genomes (KEGG) based on the hypothesis that two genes sharing similar pathways are likely to be similar. The basic principle of the POPBic approach is to apply the concept of Longest Common Subsequence between a pair of genes which have a high number of common pathways. The algorithm identifies the expression patterns from data using two major steps: (i) selection of significant seed genes and (ii) extraction of biclusters. We performe exhaustive experimentation with the POPBic algorithm using synthetic dataset to evaluate the bicluster model, finding its robustness in the presence of noise and identifying overlapping biclusters. We demonstrate that POPBic is able to discover biologically significant biclusters for four cancer microarray gene expression datasets. POPBic has been found to perform consistently well in comparison to its closest competitors.