Regular expression constrained sequence alignment

AbstractWe introduce regular expression constrained sequence alignment as the problem of finding the maximum alignment score between given strings S1 and S2 over all alignments such that in these alignments there exists a segment where some substring s1 of S1 is aligned to some substring s2 of S2, and both s1 and s2 match a given regular expression R, i.e. s1,s2∈L(R) where L(R) is the regular language described by R. For complexity results we assume, without loss of generality, that n=|S1|⩾|m|=|S2|. A motivation for the problem is that protein sequences can be aligned in a way that known motifs guide the alignments. We present an O(nmr) time algorithm for the regular expression constrained sequence alignment problem where r=O(t4), and t is the number of states of a nondeterministic finite automaton N that accepts L(R). We use in our algorithm a nondeterministic weighted finite automaton M that we construct from N. M has O(t2) states where the transition-weights are obtained from the given costs of edit operations, and state-weights correspond to optimum alignment scores we compute using the underlying dynamic programming solution for sequence alignment. If we are given a deterministic finite automaton D accepting L(R) with td states then our construction creates a deterministic finite automaton Md with td2 states. In this case, our algorithm takes O(td2nm) time. Using Md results in faster computation than using M when td