Pattern Matching with Arbitrary-length Wildcards
Author(s): QIANG Ji-Peng, XIE Fei, GAO Jun, HU Xue-Gang, WU Xin-Dong
Pages: 2499-2511
Year: 2014 Issue: 11
Journal: Acta Automatica Sinica
Keyword: Wildcard; pattern matching; bit-parallel; genetic sequence;
Abstract: In genetic sequences, many viruses rarely reproduce themselves, but rather appear with a slightly different form in each of the occurrences. That is, sequence fragments may be inserted or deleted in adjacent characters. How to search for these viruses from the sequences has become an important research task. The paper presents a more general problem, named pattern matching with arbitrary-length wildcards (PMAW). Here, a pattern can have many wildcard constraints where the range of the wildcards may vary between two integer bounds or from an integer lower bound to infinity. Given sequence S and pattern P with arbitrary-length wildcards, this paper aims to search for all occurrences of P in S, and locate matching positions of each occurrence, where any two occurrences can not share the same position of S. In order to solve the problem effectively, two algorithms, MOTW (Method of ocurrence then window) and MWTO (Method of window then ocurrence), are proposed based on the bit-parallel technique. The MWTO algorithm can also meet the global length constraint with a minor modification. Experimental results validate the correctness of the proposed algorithms, and show that they perform better than the existing pattern matching algorithms.
Pages: 2499-2511
Year: 2014 Issue: 11
Journal: Acta Automatica Sinica
Keyword: Wildcard; pattern matching; bit-parallel; genetic sequence;
Abstract: In genetic sequences, many viruses rarely reproduce themselves, but rather appear with a slightly different form in each of the occurrences. That is, sequence fragments may be inserted or deleted in adjacent characters. How to search for these viruses from the sequences has become an important research task. The paper presents a more general problem, named pattern matching with arbitrary-length wildcards (PMAW). Here, a pattern can have many wildcard constraints where the range of the wildcards may vary between two integer bounds or from an integer lower bound to infinity. Given sequence S and pattern P with arbitrary-length wildcards, this paper aims to search for all occurrences of P in S, and locate matching positions of each occurrence, where any two occurrences can not share the same position of S. In order to solve the problem effectively, two algorithms, MOTW (Method of ocurrence then window) and MWTO (Method of window then ocurrence), are proposed based on the bit-parallel technique. The MWTO algorithm can also meet the global length constraint with a minor modification. Experimental results validate the correctness of the proposed algorithms, and show that they perform better than the existing pattern matching algorithms.
Related Articles