Generalized Sequence Alignment and Duality

AbstractAlthough a number of efficient algorithms for the longest common subsequence (LCS) problem have been suggested since the 1970s, there is no duality theorem for the LCS problem. In the present paper a simple duality theorem is proved for the LCS problem and for a wide class of partial orders generalizing the notion of common subsequence and sequence alignment. An algorithm for finding generalized alignment is suggested which has the classical dynamic programming approach for alignment problems as a special case. The algorithm covers both local and global alignment as well as a variety of gap functions. It is shown that the generalized LCS problem is closely associated with the minimal Hilbert basis problem. The Jeroslav-Schrijver characterization of minimal Hilbert bases gives an 0(n) estimation for the number of elementary edit operations for generalized LCS