Flexible Pattern Matching with Gap-Length and One-Off Conditions

This paper focuses on pattern matching with wildcard, gap-length and one-off conditions. It is difficult to achieve optimal solutions. We propose an FNP algorithm based on Free-Node Optimum Pruning. Each Free-Node set is a set of nodes labeled by the same number which appear on different layers in a directed graph structure WON-Net. Compared on biological data and artificial data, experimental results show that (1) FNP has a significant advantage with its solutions, winning above 95% of biological data among similar algorithms. There are theorems on obtaining optimal solutions by FNP. (2)FNP demonstrates an evident advantage on running time, when |Net| is large and k is small. (|Net| denotes the number of independent substructures without losing solutions in WON-Net and k is the number of Free-Node sets.)