Approximate Pattern Matching With General Gaps And One-off Constraints

Pattern matching with gap constraint is one of fundamental and classical problem in computer science.It has wildly applications in many felds,such as the study of DNA sequence in biology filed,information retrieval in music filed and the hot study in large data set at present.Therefore,pattern matching is a foundamental problem in many fileds,and it has very high research value and siginificance.Any character in the sequence can be used once at most in pattern matching under one-off constraint,the general gap constraint can relieve the substring order in occurrence with strict limit.But at present,many researchers devote themselves to the problem of exact pattern matching problem.It demands that any character in the founding occurrence must be similar to the correspondent character in the pattern sequence,it is a kind of ideal model.So,we propose the problem of approximate pattern matching with general gap and one-off constraint,it is more close to reality and has higher flexibility.The computing complexity of this problem is a NP-Hard problem,which is proved theoretically in this paper.We propose a new algorithm –IM_DCNP(IMproved Dynamically Changing Node Property),which is based on an special data struct –nettree.This algotithm uses the method that updates the root path number of the nodes,it not only avoid the problem of internal repeat in the occurrence,but also impove the efficiency and quality of the algorithm.In this paper,we also conclude the time complexity of this algorithm is O(m×MaxGap×T),and the space complexity is O(m×n×MaxGap×T).Finally,we use the real sequence of DNA and representative pattern to conduct many groups of experiments,and compare with typical algorithm –SAIL-APPROX,which proved the validity and superiority of this new algorithm.