EFFICIENT DYNAMIC-PROGRAMMING ALIGNMENT OF CYCLIC STRINGS BY SHIFT ELIMINATION

Optimal alignment of two strings of length m and n is computed in time O(mn) by dynamic programming. When the strings represent cyclic patte rns, the alignment computation must consider all possible shifts and t he computation complexity increases accordingly. We present an algorit hm for efficient dynamic programming alignment of cyclic strings which uses a previously established channeling technique to reduce the comp lexity of each alignment and a new shift elimination technique to redu ce the number of alignments carried out. The result is a data-dependen t time complexity that varies between O(2mn) and O(mn log(2) n). An ex perimental evaluation is provided using randomly generated sequences. Copyright (C) 1996 Pattern Recognition Society.