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 patterns, the alignment computation must consider all possible shifts and the computation complexity increases accordingly. We present an algorithm for efficient dynamic programming alignment of cyclic strings which uses a previously established channeling technique to reduce the complexity of each alignment and a new shift elimination technique to reduce the number of alignments carried out. The result is a data-dependent time complexity that varies between O(2mn) and O(mn log2 n). An experimental evaluation is provided using randomly generated sequences.