Sequence alignment with arbitrary steps

Determine the best alignment, with allowed 'steps' <S>, between two sequences

Determine the best alignment, with allowed 'steps' <S>, between two sequences, and under a given similarity function.

In the special case where S=[1 0; 0 1; 1 1] (and for appropriate similarity function), the algorithm is identical to the classical Needleman-Wunsch sequence alignment procedure.

This can equivalently be used for computing a generalized edit distance between two sequences.

The implementation is based on:

Steffen Eger, Sequence alignment with arbitrary steps and further generalizations, with applications to alignments in linguistics. Information Sciences (2013), 237: 287--304.

See also:
B. John Oommen, String Alignment With Substitution, Insertion, Deletion, Squashing, and Expansion Operations. Information Sciences (1995), 83: 89--107.