From coding theory to efficient pattern matching

ABSTRACT

We consider the classic problem of pattern matching with few mismatches in the presence of promiscuously matching wildcard symbols. Given a text t of length n and a pattern p of length m with optional wildcard symbols and a bound k, our algorithm finds all the alignments for which the pattern matches the text with Hamming distance at most k and also returns the location and identity of each mismatch. The algorithm we present is deterministic and runs in Õ(kn) time, matching the best known randomised time complexity to within logarithmic factors. The solutions we develop borrow from the tool set of algebraic coding theory and provide a new framework in which to tackle approximate pattern matching problems.

REFERENCES

• 1: Karl Abrahamson, Generalized string matching, SIAM Journal on Computing, v.16 n.6, p.1039-1051, December 1, 1987 [doi>10.1137/0216067]
• 2: Tatsuya Akutsu, Approximate string matching with don't care characters, Information Processing Letters, v.55 n.5, p.235-239, Sept. 15, 1995 [doi>10.1016/0020-0190(95)00111-O]
• 3: Amihood Amir , Martin Farach, Efficient 2-dimensional approximate matching of half-rectangular figures, Information and Computation, v.118 n.1, p.1-11, April 1995 [doi>10.1006/inco.1995.1047]
• 4: Amihood Amir , Moshe Lewenstein , Ely Porat, Faster algorithms for string matching with k mismatches, Journal of Algorithms, v.50 n.2, p.257-275, February 2004 [doi>10.1016/S0196-6774(03)00097-X]
• 5: E. R. Berlekamp. Algebraic Coding Theory. McGraw-Hill, New York, 1968.
• 6: R. P. Brent, F. G. Gustavson, and D. Y. Y. Yun. Fast solution of toeplitz systems of equations and computation of padé approximants. Journal of Algorithms, 1(3):259--295, 1980.
• 7: Peter Clifford , Raphaël Clifford, Simple deterministic wildcard matching, Information Processing Letters, v.101 n.2, p.53-54, January, 2007 [doi>10.1016/j.ipl.2006.08.002]
• 8: R. Clifford, K. Efremenko, E. Porat, and A. Rothschild. k-mismatch with don't cares. In European Symposium on Algorithm (ESA '07), pages 151--162, October 2007.
• 9: R. Clifford and E. Porat. A filtering algorithm for k-mismatch with don't cares. In 14th International Symposium on String Processing and Information Retrieval (SPIRE), pages 130--136, October 2007.
• 10: Richard Cole , Ramesh Hariharan, Verifying candidate matches in sparse and wildcard matching, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509992]
• 11: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 12: M. Fischer and M. Paterson. String matching and other products. In R. Karp, editor, Proceedings of the 7th SIAM-AMS Complexity of Computation, pages 113--125, 1974.
• 13: P. Indyk, Faster Algorithms for String Matching Problems: Matching the Convolution Bound, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.166, November 08-11, 1998
• 14: Adam Kalai, Efficient pattern-matching with don't cares, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.655-656, January 06-08, 2002, San Francisco, California
• 15: Howard Karloff, Fast algorithms for approximately counting mismatches, Information Processing Letters, v.48 n.2, p.53-60, Nov. 8, 1993 [doi>10.1016/0020-0190(93)90177-B]
• 16: S. R. Kosaraju. Efficient string matching. Manuscript, 1987.
• 17: Gad M. Landau , Uzi Vishkin, Efficient string matching in the presence of errors, Proceedings of the 26th Annual Symposium on Foundations of Computer Science, p.126-136, October 21-23, 1985 [doi>10.1109/SFCS.1985.22]
• 18: G M Landau , U Vishkin, Efficient string matching with k mismatches, Theoretical Computer Science, v.43 n.2-3, p.239-249, July 1986
• 19: J. L. Massey. Shift-register synthesis and bch decoding. IEEE Trans. on Information Theory, 15:122--127, 1969.
• 20: A. Schönhage. Schnelle multiplikation von polynomen über körpern der charakteristik 2. Acta Inform., 7:395--398, 1976.
• 21: Victor Shoup, A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.14-21, July 15-17, 1991, Bonn, West Germany [doi>10.1145/120694.120697]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms