title: A New Approach for Mining Order-Preserving Submatrices Based on All Common Subsequences.
abstract: Order-preserving submatrices (OPSMs) have been applied in many fields, such as DNA microarray data analysis, automatic recommendation systems, and target marketing systems, as an important unsupervised learning model. Unfortunately, most existing methods are heuristic algorithms which are unable to reveal OPSMs entirely in NP-complete problem. In particular, deep OPSMs, corresponding to long patterns with few supporting sequences, incur explosive computational costs and are completely pruned by most popular methods. In this paper, we propose an exact method to discover all OPSMs based on frequent sequential pattern mining. First, an existing algorithm was adjusted to disclose all common subsequence (ACS) between every two row sequences, and therefore all deep OPSMs will not be missed. Then, an improved data structure for prefix tree was used to store and traverse ACS, and Apriori principle was employed to efficiently mine the frequent sequential pattern. Finally, experiments were implemented on gene and synthetic datasets. Results demonstrated the effectiveness and efficiency of this method.
authors.affiliation: Laboratory of Quantum Engineering and Quantum Materials, School of Physics and Telecommunication Engineering, South China Normal University, Guangzhou 510006, China.
authors.forename: Yun
authors.initials: Y
authors.lastname: Xue
authors.affiliation: Laboratory of Quantum Engineering and Quantum Materials, School of Physics and Telecommunication Engineering, South China Normal University, Guangzhou 510006, China.
authors.forename: Zhengling
authors.initials: Z
authors.lastname: Liao
authors.affiliation: Laboratory of Quantum Engineering and Quantum Materials, School of Physics and Telecommunication Engineering, South China Normal University, Guangzhou 510006, China.
authors.forename: Meihang
authors.initials: M
authors.lastname: Li
authors.affiliation: Laboratory of Quantum Engineering and Quantum Materials, School of Physics and Telecommunication Engineering, South China Normal University, Guangzhou 510006, China.
authors.forename: Jie
authors.initials: J
authors.lastname: Luo
authors.affiliation: Laboratory of Quantum Engineering and Quantum Materials, School of Physics and Telecommunication Engineering, South China Normal University, Guangzhou 510006, China.
authors.forename: Qiuhua
authors.initials: Q
authors.lastname: Kuang
authors.affiliation: Laboratory of Quantum Engineering and Quantum Materials, School of Physics and Telecommunication Engineering, South China Normal University, Guangzhou 510006, China.
authors.forename: Xiaohui
authors.initials: X
authors.lastname: Hu
authors.affiliation: Laboratory of Quantum Engineering and Quantum Materials, School of Physics and Telecommunication Engineering, South China Normal University, Guangzhou 510006, China.
authors.forename: Tiechen
authors.initials: T
authors.lastname: Li
mesh_terms: D000465:Algorithms; D001331:Automation; D016000:Cluster Analysis; D019295:Computational Biology / Q000379:methods*; D057225:Data Mining / Q000379:methods*; D030541:Databases, Genetic; D020869:Gene Expression Profiling; D015966:Gene Expression Regulation, Fungal; D020411:Oligonucleotide Array Sequence Analysis; D010363:Pattern Recognition, Automated / Q000379:methods; D012441:Saccharomyces cerevisiae / Q000378:metabolism; D012984:Software