Generalized sequence alignment and duality (Q1261853)

The problem of finding a longest common subsequence of two sequences \(s_ 1\), \(s_ 2, \dots, s_ n\) and \(t_ 1\), \(t_ 2, \dots, t_ m\) (LCS-problem) can be characterized within the theory of posets by studying a partial order on \(\{1,2, \dots, n\} \times \{1,2, \dots,m\}\) that is defined by means of a \(2 \times 2\)-matrix \(A\) over 0 and 1. By allowing arbitrary integer matrices \(A\) the authors generalize the LCS- problem to a class of problems which includes several alignment problems that are of biological interest. For this class of A-LCS-problems a duality result is proved which is related to Dilworth's theorem on longest chain and minimum cover in posets and this result is utilized to give a primal-dual-algorithm for sequence alignments. Moreover, algorithms for the A-CLS-problem based on the property of an A- LCS to be a path in a compatibility graph for a partial order are derived which generalize the classical dynamic programming approach, and it is shown that the A-CLS-problem is closely associated with the minimum Hilbert bases problem. The last part of the paper is devoted to generalized alignments. An algorithm for optimal generalized alignments is given that contains many alignment algorithms as particular cases.