Input

The input consists of σ sequences S1,..., Sσ over alphabet Σ, and a sequence of con-straints R1,..., Rm, where each Rj is a regular expression. The goal is to find an align-ment with the highest possible score such that the constraints are satisfied. An alignment A of S1,..., Sσ is said to satisfy the constraints if in A there exist m regions with the following property. Let the ℓth region, corresponding to the ℓth constraint, be composed of consecutive columns kℓ, kℓ + 1,..., k ′ ℓ, ℓ = 1,..., m, which is also required to preceed the (ℓ + 1)st without overlapping. Then the substring of each Si corresponding to region ℓ is required to match the regular expression Rℓ. For an illustration please see Fig. 1.