A new approach for mining deep order-preserving submatrices

In this paper, we proposed an exact method to discover all order-preserving submatrices (OPSMs) based on frequent sequential pattern mining. Firstly, an existing algorithm calACS is adjusted to disclose all common subsequences between every two row sequences, therefore all the deep OPSMs corresponding to long patterns with few supporting sequences will not be missed. Then an improved data structure for prefix tree was used to store and traverse all common subsequences, and Apriori principle was employed to mine the frequent sequential pattern efficiently. Finally, experiments were implemented on real data set and GO analysis was applied to identify whether the patterns discovered were biologically significant. The results demonstrate the effectiveness and the efficiency of this method.