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. |