Approximate matching of regular expressions

DOI10.1007/BF02458834zbMath0669.68054OpenAlexW4244527929WikidataQ44121872 ScholiaQ44121872MaRDI QIDQ1119025

Eugene W. Myers, Webb Miller

Publication date: 1989

Published in: Bulletin of Mathematical Biology (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02458834

zbMATH Keywords

regular expressionssequence comparisondatabase searchesapproximate regular expression matchingedit graph model

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Genetics and epigenetics (92D10) Algorithms in computer science (68W99) Physiological, cellular and medical topics (92Cxx)

Related Items (17)

Fast and compact regular expression matching ⋮ Approximate regular expression pattern matching with concave gap penalties ⋮ Computing the edit distance of a regular language ⋮ Algorithms for approximate graph matching ⋮ Super-pattern matching ⋮ Period recovery of strings over the Hamming and edit distances ⋮ A faster algorithm for finding shortest substring matches of a regular expression ⋮ Regular expression constrained sequence alignment ⋮ Approximately matching context-free languages ⋮ A time-efficient, linar-space local similarity algorithm ⋮ Efficient optimal decomposition of a sequence into disjoint regions, each matched to some template in an inventory ⋮ Measuring rank correlation coefficients between financial time series: a GARCH-copula based sequence alignment algorithm ⋮ Identifying periodic occurrences of a template with applications to protein structure ⋮ Constrained sequence alignment ⋮ Tandem cyclic alignment ⋮ Periodic String Comparison ⋮ On computing all suboptimal alignments

Cites Work

• Unnamed Item
• Unnamed Item
• General methods of sequence comparison
• Pattern recognition in genetic sequences by mismatch density
• Sequence comparison with concave weighting functions
• Some biological sequence metrics
• The theory and computation of evolutionary distances: Pattern recognition
• A Simple Algorithm for Global Data Flow Analysis Problems
• Correcting Counter-Automaton-Recognizable Languages
• Order- n correction for regular languages
• Programming Techniques: Regular expression search algorithm

This page was built for publication: Approximate matching of regular expressions