Approximate pattern matching with gap constraints. (October 2016)

• Record Type: Journal Article
• Authors: Wu, Youxi; Tang, Zhiqiang; Jiang, He; Wu, Xindong
• Is Part Of: Journal of information science. Volume 42:Number 5(2016)
• Page Start: 639
• Page End: 658
• Publication Date: 2016-10
• Subjects: Approximate pattern matching -- Gap constraints -- Length constraint -- Hamming distance -- Nettree; Information science -- Periodicals; Information science; Periodicals; 020.5
• DOI: 10.1177/0165551515603286
• Languages: English
• ISSNs: 0165-5515

Abstract

Pattern matching is a key issue in sequential pattern mining. Many researchers now focus on pattern matching with gap constraints. However, most of these studies involve exact pattern matching problems, a special case of approximate pattern matching and a more challenging task. In this study, we introduce an approximate pattern matching problem with Hamming distance. Its objective is to compute the number of approximate occurrences of pattern P with gap constraints in sequence S under similarity constraint d . We propose an efficient algorithm named Single-rOot Nettree for approximate pattern matchinG with gap constraints (SONG) based on a new non-linear data structure Single-root Nettree to effectively solve the problem. Theoretical analysis and experiments demonstrate an interesting law that the ratio M ( P, S, d )/ N ( P, S, m ) approximately follows a binomial distribution, where M ( P, S, d ) and N ( P, S, m ) are the numbers of the approximate occurrences whose distances to pattern P are d (0≤ d ≤ m ) and no more than m (the length of pattern P ), respectively. Experimental results for real biological data validate the efficiency and effectiveness of SONG.