Sequence Alignment with Weighted Constraints

Given two sequences S1, S2 and a constrained sequence C, the longest common subsequence of S1, S2 with restriction to C is defined as the constrained longest common subsequence (CLCS) of S1, S2 and C. At the same time, the best alignment of S1, S2 with restriction to C is defined as the constrained pairwise sequence alignment (CPSA) of S1, S2 and C. Previous algorithms have shown that both CLCS and CPSA can be solved in O(rnm) time using similar dynamic programming formulas, where r = |C|, n = |S1| and m = |S2|. In 2004, Arslan first extended the definition of CLCS to a more flexible version, where the number of ignored constraints is allowed to a degree d and time complexity increases to O(drnm). In this paper, we extend the definition of CPSA to another version, called weighted CPSA (WCPSA), and show that WCPSA can not only be solved in O(rnm) time but also allow ignoring constraints by setting proper weights. In addition, we also show that some constraint-related problems can be immediately solved by adopting WCPSA. Key words: algorithm, longest common subsequence, sequence alignment, dynamic programming