5 - Regular expression matching

Summary

Basic concepts

We present in this chapter algorithms to search for regular expressions in texts or biological sequences. Regular expressions are often used in text retrieval or computational biology applications to represent search patterns that are more complex than a string, a set of strings, or an extended string. We begin with a formal definition of a regular expression and the language (set of strings) it represents.

DefinitionA regular expression RE is a string on the set of symbols Σ ∪ { ε, |, ·, ⋆, (,) }, which is recursively defined as the empty character ε a character α ∈ Σ and (RE₁), (RE₁ · RE₂), (RE₁ | RE₂), and (RE₁⋆), where RE₁and RE₂are regular expressions.

For instance, in this chapter we consider the regular expression (((A·T) | (G·A))·(((A·G) | ((A·A)·A))⋆)). When there is no ambiguity, we simplify our expressions by writing RE₁RE₂ instead of (RE₁ · RE₂). This way, we obtain a more readable expression, in our case (AT|GA) ((AG|AAA)⋆). It is usual to use also the precedence order “*”, “·”, “|” to remove more parentheses, but we do not do this here. The symbols “·”, “|”, “⋆” are called operators. It is customary to add an extra postfix operator “+” to mean RE+ = RE · RE⋆. We define now the language represented by a regular expression.

DefinitionThe language represented by a regular expression RE is a set of strings over Σ which is defined recursively on the structure of RE as follows:

1. • If RE is ε, then L(RE) = {ε}, the empty string.

2. • If RE is α ∈ Σ, then L(RE) = {α}, a single string of one character.

3. • If RE is of the form (RE₁), then L(RE) = L(RE₁).

4. • If RE is of the form (RE₁ · RE₂), then L(RE) = L(RE₁) · L(RE₂), where W₁ · W₂is the set of strings w such that w = w₁w₂, with w₁ ∈ W₁and w₂ ∈ W₂. The operator “·” represents the classical concatenation of strings.

5. […]