Approximate matching of regular expressions (Q1119025)

The object of this paper is to present a new algorithm for approximate regular expression matching, which is best suited for biosequence database query. The algorithm possesses several major advantages when compared with similar algorithms found in the literature. The paper includes background information on optimal alignment of sequences, regular expressions, finite automata and edit graphs. The algorithm is carefully developed and space and time estimates are given. Furthermore, two interesting extensions of the algorithm are outlined. It must be pointed out that the writing is concise with a maximum of information nicely packed and the subject matter is presented at a level that presumes familiarity with the theory of regular expressions and some software practice. In conclusion, this is a very practical paper that provides a valuable reference material for practitioners in molecular biology, as well ass professionals with an interest in sequence comparison (e.g. for text editors).