skip to main content
10.5555/1109557.1109692acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

Pattern matching with address errors: rearrangement distances

Published: 22 January 2006 Publication History

Abstract

Historically, approximate pattern matching has mainly focused at coping with errors in the data, while the order of the text/pattern was assumed to be more or less correct. In this paper we consider a class of pattern matching problems where the content is assumed to be correct, while the locations may have shifted/changed. We formally define a broad class of problems of this type, capturing situations in which the pattern is obtained from the text by a sequence of rearrangements. We consider several natural rearrangement schemes, including the analogues of the l1 and l2 distances, as well as two distances based on interchanges. For these, we present efficient algorithms to solve the resulting string matching problems.

References

[1]
K. Abrahamson, Generalized string matching, SIAM J. Comp. 16 (1987), no. 6, 1039--1051.
[2]
A. Amir, A. Aumann, R. Cole, M. Lewenstein, and E. Porat, Function matching: Algorithms, applications, and a lower bound, Proc. 30th ICALP, 2003, pp. 929--942.
[3]
A. Amir, Y. Aumann, and A. Levy, Pattern matching with address errors: Renaming schemes, Manuscript.
[4]
A. Amir, R. Cole, R. Hariharan, M. Lewenstein, and E. Porat, Overlap matching, Information and Computation 181 (2003), no. 1, 57--74.
[5]
A. Amir, M. Lewenstein, and E. Porat, Faster algorithms for string matching with k mismatches., J. Algorithms 50 (2004), no. 2, 257--275.
[6]
V. Bafna and P. A. Pevzner, Sorting by transpositions, SIAM J. on Discrete Mathematics 11 (1998), 221--240.
[7]
B. S. Baker, A theory of parameterized pattern matching: algorithms and applications, Proc. 25th Annual ACM Symposium on the Theory of Computation, 1993, pp. 71--80.
[8]
P. Berman and S. Hannenhalli, Fast sorting by reversal, Proc. 8th Annual Symposium on Combinatorial Pattern Matching (CPM) (D.S. Hirschberg and E. W. Myers, eds.), LNCS, vol. 1075, Springer, 1996, pp. 168--185.
[9]
A. Carpara, Sorting by reversals is difficult, Proc. 1st Annual Intl. Conf. on Research in Computational Biology (RECOMB), ACM Press, 1997, pp. 75--83.
[10]
D. A. Christie, Sorting by block-interchanges, Information Processing Letters 60 (1996), 165--169.
[11]
R. Cole, L. A. Gottlieb, and M. Lewenstein, Dictionary matching and indexing with errors and don't cares, STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, 2004, pp. 91--100.
[12]
R. Cole and R. Hariharan, Approximate string matching: A faster simpler algorithm, Proc. 9th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1998, pp. 463--472.
[13]
Y. Dvir, Covering properties of permutation groups, Products of Conjugacy Classes in Groups (Z. Arad and M. Herzog, eds.), Lecture Notes in Mathematics 1112, 1985.
[14]
P. Ferragina and R. Grossi, Fast incremental text editing, Proc. 7th ACM-SIAM Symposium on Discrete Algorithms (1995), 531--540.
[15]
M. J. Fischer and M. S. Paterson, String matching and other products, Complexity of Computation, R. M. Karp (editor), SIAM-AMS Proceedings 7 (1974), 113--125.
[16]
Z. Galil and R. Giancarlo, Improved string matching with k mismatches, SIGACT News 17 (1986), no. 4, 52--54.
[17]
M. Gu, M. Farach, and R. Beigel, An efficient algorithm for dynamic text indexing, Proc. 5th Annual ACM-SIAM Symposium on Discrete Algorithms (1994), 697--704.
[18]
H. Karloff, Fast algorithms for approximately counting mismatches, Information Processing Letters 48 (1993), no. 2, 53--60.
[19]
G. M. Landau and U. Vishkin, Efficient string matching with k mismatches, Theoretical Computer Science 43 (1986), 239--249.
[20]
V. I. Levenshtein, Binary codes capable of correcting, deletions, insertions and reversals, Soviet Phys. Dokl. 10 (1966), 707--710.
[21]
R. Lowrance and R. A. Wagner, An extension of the string-to-string correction problem, J. of the ACM (1975), 177--183.
[22]
S. Muthukrishnan and H. Ramesh, String matching under a general matching relation, Information and Computation 122 (1995), no. 1, 140--148.
[23]
S. C. Sahinalp and U. Vishkin, Efficient approximate and dynamic matching of patterns using a labeling paradigm, Proc. 37th FOCS (1996), 320--328.
[24]
J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. of the ACM 27 (1980), 701--717.
[25]
U. Vishne, Mixing and covering in the symmetric group, Journal of Algebra 205 (1998), no. 1, 119--140.
[26]
A. C. C. Yao, Some complexity questions related to distributed computing, Proc. 11th Annual Symposium on the Theory of Computing (STOC), 1979, pp. 209--213.
[27]
R. Zippel, Probabilistic algorithms for sparse polynomials, Proc. EUROSAM, LNCS, vol. 72, Springer, 1979, pp. 216--226.

Cited By

View all
  • (2012)Cycle detection and correctionACM Transactions on Algorithms10.1145/2390176.23901899:1(1-20)Online publication date: 26-Dec-2012
  • (2012)Approximate period detection and correctionProceedings of the 19th international conference on String Processing and Information Retrieval10.1007/978-3-642-34109-0_1(1-15)Online publication date: 21-Oct-2012
  • (2011)Blocked pattern matching problem and its applications in proteomicsProceedings of the 15th Annual international conference on Research in computational molecular biology10.5555/1987587.1987614(298-319)Online publication date: 28-Mar-2011
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm
January 2006
1261 pages
ISBN:0898716055

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 22 January 2006

Check for updates

Qualifiers

  • Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2012)Cycle detection and correctionACM Transactions on Algorithms10.1145/2390176.23901899:1(1-20)Online publication date: 26-Dec-2012
  • (2012)Approximate period detection and correctionProceedings of the 19th international conference on String Processing and Information Retrieval10.1007/978-3-642-34109-0_1(1-15)Online publication date: 21-Oct-2012
  • (2011)Blocked pattern matching problem and its applications in proteomicsProceedings of the 15th Annual international conference on Research in computational molecular biology10.5555/1987587.1987614(298-319)Online publication date: 28-Mar-2011
  • (2010)String rearrangement metricsAlgorithms and Applications10.5555/2167962.2167963(1-33)Online publication date: 1-Jan-2010
  • (2010)Approximate string matching with stuck address bitsProceedings of the 17th international conference on String processing and information retrieval10.5555/1928328.1928379(395-405)Online publication date: 11-Oct-2010
  • (2010)Cycle detection and correctionProceedings of the 37th international colloquium conference on Automata, languages and programming10.5555/1880918.1880925(43-54)Online publication date: 6-Jul-2010
  • (2009)Online Approximate Matching with Non-local DistancesProceedings of the 20th Annual Symposium on Combinatorial Pattern Matching - Volume 557710.5555/3127091.3127104(142-153)Online publication date: 22-Jun-2009
  • (2009)Approximate string matching with address bit errorsTheoretical Computer Science10.1016/j.tcs.2009.09.010410:51(5334-5346)Online publication date: 1-Nov-2009
  • (2008)Indexing circular patternsProceedings of the 2nd international conference on Algorithms and computation10.5555/1787651.1787658(46-57)Online publication date: 7-Feb-2008
  • (2008)Approximate String Matching with Address Bit ErrorsProceedings of the 19th annual symposium on Combinatorial Pattern Matching10.1007/978-3-540-69068-9_13(118-129)Online publication date: 18-Jun-2008
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media